Further Improvements in AES Execution over TFHE: Towards Breaking the 1 sec Barrier

Sonia Belaïd; Nicolas Bon; Aymen Boudguiga; Renaud Sirdey; Daphné Trama; Nicolas Ye

Paper 2025/075

Further Improvements in AES Execution over TFHE: Towards Breaking the 1 sec Barrier

Sonia Belaïd, CryptoExperts, Paris, France

Nicolas Bon, CryptoExperts, Paris, France, DIENS, Ecole normale supérieure, PSL University, CNRS, Inria, Paris, France

Aymen Boudguiga, Université Paris-Saclay, CEA LIST, Palaiseau, France

Renaud Sirdey, Université Paris-Saclay, CEA LIST, Palaiseau, France

Daphné Trama, Université Paris-Saclay, CEA LIST, Palaiseau, France

Nicolas Ye, Université Paris-Saclay, CEA LIST, Palaiseau, France

Abstract

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 "practical" 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, -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 "Hippogryph", which consistently combines the (byte-oriented) LUT-based approach with a generalization of the (boolean-oriented) -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 1 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.

Note: Final version accepted in CiC Edit Acknowledgements

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published by the IACR in CIC 2025
Keywords: FHE AES transciphering
Contact author(s): sonia belaid @ cryptoexperts com
nicolas bon @ cryptoexperts com
aymen boudguiga @ cea fr
renaud sirdey @ cea fr
daphne trama @ cea fr
nicolas ye @ cea fr
History: 2025-03-27: last of 4 revisions; 2025-01-17: received; See all versions
Short URL: https://ia.cr/2025/075
License: CC BY

BibTeX

@misc{cryptoeprint:2025/075,
      author = {Sonia Belaïd and Nicolas Bon and Aymen Boudguiga and Renaud Sirdey and Daphné Trama and Nicolas Ye},
      title = {Further Improvements in {AES} Execution over {TFHE}: Towards Breaking the 1 sec Barrier},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/075},
      year = {2025},
      url = {https://eprint.iacr.org/2025/075}
}