{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:57:47Z","timestamp":1780675067332,"version":"3.54.1"},"reference-count":37,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T00:00:00Z","timestamp":1736812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,3,11]]},"abstract":"<jats:p> Making the most of TFHE advanced capabilities such as programmable or circuit bootstrapping and their generalizations for manipulating data larger than the native plaintext domain of the scheme is a very active line of research. In this context, AES is a particularly interesting benchmark, as an example of a nontrivial algorithm which has eluded \u201cpractical\u201d FHE execution performances for years, as well as the fact that it will most likely be selected by NIST as a flagship reference in its upcoming call on threshold (homomorphic) cryptography. Since 2023, the algorithm has thus been the subject of a renewed attention from the FHE community and has served as a playground to test advanced operators following the LUT-based, p-encodings or several variants of circuit bootstrapping, each time leading to further timing improvements. Still, AES is also interesting as a benchmark because of the tension between boolean- and byte-oriented operations within the algorithm. In this paper, we resolve this tension by proposing a new approach, coined \u201cHippogryph\u201d, which consistently combines the (byte-oriented) LUT-based approach with a generalization of the (boolean-oriented) <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>p<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math>-encodings one to get the best of both worlds. In doing so, we obtain the best timings so far, getting a single-core execution of the algorithm over TFHE from 46 down to 32 seconds and approaching the <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mn>1<\/mml:mn>\n              <\/mml:mrow>\n            <\/mml:math> second barrier with only a mild amount of parallelism. We should also stress that all the timings reported in this paper are consistently obtained on the same machine which is often not the case in previous studies. Lastly, we emphasize that the techniques we develop are applicable beyond just AES since the boolean-byte tension is a recurrent issue when running algorithms over TFHE. <\/jats:p>","DOI":"10.62056\/ahmp-4tw9","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T21:23:17Z","timestamp":1744147397000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":7,"title":["Further Improvements in AES Execution over TFHE"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9437-6425","authenticated-orcid":false,"given":"Sonia","family":"Bela\u00efd","sequence":"first","affiliation":[{"name":"CryptoExperts","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-3777-3018","authenticated-orcid":false,"given":"Nicolas","family":"Bon","sequence":"additional","affiliation":[{"name":"CryptoExperts","place":["Paris, France"]},{"name":"DIENS, Ecole normale sup\u00e9rieure, PSL University, CNRS, Inria","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6717-8848","authenticated-orcid":false,"given":"Aymen","family":"Boudguiga","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CEA LIST","place":["Palaiseau, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4720-9269","authenticated-orcid":false,"given":"Renaud","family":"Sirdey","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CEA LIST","place":["Palaiseau, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0548-8825","authenticated-orcid":false,"given":"Daphn\u00e9","family":"Trama","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CEA LIST","place":["Palaiseau, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Ye","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CEA LIST","place":["Palaiseau, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,4,8]]},"reference":[{"key":"ref1:ITCS:BraGenVai12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/2090236.2090262","article-title":"(Leveled) fully homomorphic encryption without\n  bootstrapping","author":"Zvika Brakerski","year":"2012"},{"key":"ref2:AC:CKKS17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-319-70694-8_15","article-title":"Homomorphic Encryption for Arithmetic of Approximate\n  Numbers","volume":"10624","author":"Jung Hee Cheon","year":"2017"},{"key":"ref3:AC:CGGI16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-53887-6_1","article-title":"Faster Fully Homomorphic Encryption: Bootstrapping in Less\n  Than 0.1 Seconds","volume":"10031","author":"Ilaria Chillotti","year":"2016"},{"key":"ref4:JC:CGGI20","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/s00145-019-09319-x","article-title":"TFHE: Fast Fully Homomorphic Encryption Over the Torus","volume":"33","author":"Ilaria Chillotti","year":"2020","journal-title":"Journal of Cryptology"},{"key":"ref5:gentry_BGV","first-page":"99","article-title":"Homomorphic Evaluation of the AES Circuit","author":"Craig Gentry","year":"2012","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref6:EPRINT:HalSho20","volume-title":"Design and implementation of HElib: a homomorphic\n  encryption library","author":"Shai Halevi","year":"2020"},{"key":"ref7:lowMC","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/978-3-662-46800-5_17","article-title":"Ciphers for MPC and FHE","volume":"9056","author":"Martin R. Albrecht","year":"2015"},{"key":"ref8:PRINCE","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-642-34961-4_14","article-title":"PRINCE - A Low-Latency Block Cipher for Pervasive\n  Computing Applications - Extended Abstract","volume":"7658","author":"Julia Borghoff","year":"2012"},{"key":"ref9:Chaghri","series-title":"CCS '22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/3548606.3559364","article-title":"Chaghri - A FHE-Friendly Block Cipher","author":"T. Ashur","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450394505"},{"key":"ref10:Elisabeth","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-031-22969-5_2","article-title":"Towards Case-Optimized Hybrid Homomorphic Encryption -\n  Featuring the Elisabeth Stream Cipher","volume":"13793","author":"Orel Cosseron","year":"2022"},{"key":"ref11:pasta","doi-asserted-by":"publisher","first-page":"30","DOI":"10.46586\/TCHES.V2023.I3.30-73","article-title":"Pasta: A Case for Hybrid Homomorphic Encryption","volume":"2023","author":"Christoph Dobraunig","year":"2023","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref12:kreyvium","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-662-52993-5_16","article-title":"Stream Ciphers: A Practical Solution for Efficient\n  Homomorphic-Ciphertext Compression","volume":"9783","author":"Anne Canteaut","year":"2016"},{"key":"ref13:transistor","volume-title":"Transistor: a TFHE-friendly Stream Cipher","author":"Jules Baudrin","year":"2025"},{"key":"ref14:call_nist","volume-title":"The NIST Threshold Call","author":"National Institute of Standards","year":"2025"},{"key":"ref15:DBLP:conf\/wahc\/TramaCBS23","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1145\/3605759.3625260","article-title":"A Homomorphic AES Evaluation in Less than 30 Seconds by\n  Means of TFHE","author":"D. Trama","year":"2023"},{"key":"ref16:Guimaraes_Borin_Aranha_2021","doi-asserted-by":"publisher","first-page":"229","DOI":"10.46586\/TCHES.V2021.I2.229-253","article-title":"Revisiting the functional bootstrap in TFHE","volume":"2021","author":"Antonio Guimar\u00e3es","year":"2021","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref17:DBLP:journals\/tches\/BonPR24","doi-asserted-by":"publisher","first-page":"302","DOI":"10.46586\/TCHES.V2024.I3.302-341","article-title":"Optimized Homomorphic Evaluation of Boolean Functions","volume":"2024","author":"N. Bon","year":"2024","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref18:fregata","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/978-3-031-49187-0_20","article-title":"Fregata: Faster Homomorphic Evaluation of AES via TFHE","author":"B. Wei","year":"2023"},{"key":"ref19:thunderbird","doi-asserted-by":"publisher","first-page":"530","DOI":"10.46586\/TCHES.V2024.I3.530-573","article-title":"Thunderbird: Efficient Homomorphic Evaluation of Symmetric\n  Ciphers in 3GPP by combining two modes of TFHE","volume":"2024","author":"B. Wei","year":"2024","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref20:kreyvium-2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1145\/3605759.3625255","article-title":"Trivial Transciphering With Trivium and TFHE","author":"Thibault Balenbois","year":"2023"},{"key":"ref21:AC:CGGI17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/978-3-319-70694-8_14","article-title":"Faster Packed Homomorphic Operations and Efficient Circuit\n  Bootstrapping for TFHE","volume":"10624","author":"Ilaria Chillotti","year":"2017"},{"key":"ref22:DucMic15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-662-46800-5_24","article-title":"FHEW: Bootstrapping Homomorphic Encryption in Less Than a\n  Second","volume":"9056","author":"L\u00e9o Ducas","year":"2015"},{"key":"ref23:Gentry09","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1145\/1536414.1536440","article-title":"Fully homomorphic encryption using ideal lattices","author":"Craig Gentry","year":"2009"},{"key":"ref24:AlBadawi23","volume-title":"Demystifying Bootstrapping in Fully Homomorphic Encryption","author":"A. Al Badawi","year":"2023"},{"key":"ref25:rijndael","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04722-4","volume-title":"The Design of Rijndael: AES - The Advanced Encryption\n  Standard (Information Security and Cryptography)","author":"J. Daemen","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540425802"},{"key":"ref26:carpov_mvb","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-030-12612-4_6","article-title":"New Techniques for Multi-value Input Homomorphic Evaluation\n  and Applications","author":"S. Carpov","year":"2019"},{"key":"ref27:DBLP:journals\/iacr\/Maximov19","first-page":"833","article-title":"AES MixColumn with 92 XOR gates","author":"A. Maximov","year":"2019","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref28:boyar","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-642-13193-6_16","article-title":"A New Combinational Logic Minimization Technique with\n  Applications to Cryptology","volume":"6049","author":"J. Boyar","year":"2010"},{"key":"ref29:pbsManyLUT","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1007\/978-3-030-92078-4_23","article-title":"Improved Programmable Bootstrapping with Larger Precision\n  and Efficient Arithmetic Circuits for TFHE","volume":"13092","author":"Ilaria Chillotti","year":"2021"},{"key":"ref30:TFHEpp","volume-title":"TFHEpp: pure C++ implementation of TFHE cryptosystem","author":"K. Matsuoka","year":"2020"},{"key":"ref31:TFHE-rs","volume-title":"TFHE-rs: A Pure Rust Implementation of the TFHE Scheme for\n  Boolean and Integer Arithmetics Over Encrypted Data","author":"Zama","year":"2022"},{"key":"ref32:CPAD","first-page":"1533","article-title":"On the Security of Homomorphic Encryption on Approximate\n  Numbers","author":"Baiyu Li","year":"2020","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref33:CPADatt1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-68382-4_1","article-title":"On the Practical CPA\\({}^{\\mbox{D}}\\) Security of \"exact\"\n  and Threshold FHE Schemes and Libraries","volume":"14922","author":"Marina Checri","year":"2024"},{"key":"ref34:CPADatt2","first-page":"127","article-title":"Attacks Against the INDCPA-D Security of Exact FHE\n  Schemes","author":"Jung Hee Cheon","year":"2024","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref35:skinny","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-662-53008-5_5","article-title":"The SKINNY Family of Block Ciphers and Its Low-Latency\n  Variant MANTIS","volume":"9815","author":"C. Beierle","year":"2016"},{"key":"ref36:present","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/978-3-540-74735-2_31","article-title":"PRESENT: An Ultra-Lightweight Block Cipher","volume":"4727","author":"Andrey Bogdanov","year":"2007"},{"key":"ref37:d8fp","first-page":"1201","article-title":"Designing a General-Purpose 8-bit (T)FHE Processor\n  Abstraction","author":"Daphn\u00e9 Trama","year":"2025","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T21:25:40Z","timestamp":1744147540000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/1\/39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,8]]},"references-count":37,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,8]]}},"URL":"https:\/\/doi.org\/10.62056\/ahmp-4tw9","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,8]]},"assertion":[{"value":"2025-01-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-1-65"}}