Further Improvements in AES Execution over TFHE

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

doi:10.62056/ahmp-4tw9

Further Improvements in AES Execution over TFHE

Authors

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

Sonia Belaïd

CryptoExperts, Paris, France
sonia dot belaid at cryptoexperts dot com

Nicolas Bon

CryptoExperts, Paris, France
DIENS, Ecole normale supérieure, PSL University, CNRS, Inria, Paris, France
nicolas dot bon at cryptoexperts dot com

Aymen Boudguiga

Université Paris-Saclay, CEA LIST, Palaiseau, France
aymen dot boudguiga at cea dot fr

Renaud Sirdey

Université Paris-Saclay, CEA LIST, Palaiseau, France
renaud dot sirdey at cea dot fr

Daphné Trama

Université Paris-Saclay, CEA LIST, Palaiseau, France
daphne dot trama at cea dot fr

Nicolas Ye

Université Paris-Saclay, CEA LIST, Palaiseau, France
nicolas dot ye at cea dot fr

Keywords: AES FHE Transciphering TFHE

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, 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 “Hippogryph”, which consistently combines the (byte-oriented) LUT-based approach with a generalization of the (boolean-oriented) $p$-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.

References

[AMT22]

T. Ashur, M. Mahzoun, and D. Toprakhisar. Chaghri - A FHE-Friendly Block Cipher. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 139–150, New York, NY, USA. 2022. Association for Computing Machinery. DOI: 10.1145/3548606.3559364

Google Scholar ePrint

[ARS⁺15]

Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 430–454. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_17

Google Scholar ePrint

[BBB⁺25]

Jules Baudrin, Sonia Belaïd, Nicolas Bon, Christina Boura, Anne Canteaut, Gaëtan Leurent, Pascal Paillier, Léo Perrin, Matthieu Rivain, Yann Rotella, and Samuel Tap. Transistor: a TFHE-friendly Stream Cipher. Cryptology ePrint Archive, Paper 2025/282. 2025.

Google Scholar ePrint

[BCG⁺12]

Julia Borghoff, Anne Canteaut, Tim Güneysu, Elif Bilge Kavun, Miroslav Knezevic, Lars R. Knudsen, Gregor Leander, Ventzislav Nikov, Christof Paar, Christian Rechberger, Peter Rombouts, Søren S. Thomsen, and Tolga Yalçin. PRINCE - A Low-Latency Block Cipher for Pervasive Computing Applications - Extended Abstract. In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings, volume 7658 of Lecture Notes in Computer Science, pages 208–225. 2012. Springer. DOI: 10.1007/978-3-642-34961-4_14

Google Scholar ePrint

[BGV12]

Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012, pages 309–325, Cambridge, MA, USA. 2012. ACM. DOI: 10.1145/2090236.2090262

Google Scholar ePrint

[BJK⁺16]

C. Beierle, J. Jean, S. Kölbl, G. Leander, A. Moradi, Thomas Peyrin, Y. Sasaki, P. Sasdrich, and S. M. Sim. The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, volume 9815 of Lecture Notes in Computer Science, pages 123–153. 2016. Springer.

Google Scholar ePrint

[BKL⁺07]

Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, and C. Vikkelsoe. PRESENT: An Ultra-Lightweight Block Cipher. In Pascal Paillier and Ingrid Verbauwhede, editors, Cryptographic Hardware and Embedded Systems - CHES 2007, 9th International Workshop, Vienna, Austria, September 10-13, 2007, Proceedings, volume 4727 of Lecture Notes in Computer Science, pages 450–466. 2007. Springer. DOI: 10.1007/978-3-540-74735-2_31

Google Scholar ePrint

[BOS23]

Thibault Balenbois, Jean-Baptiste Orfila, and Nigel P. Smart. Trivial Transciphering With Trivium and TFHE. In Michael Brenner, Anamaria Costache, and Kurt Rohloff, editors, Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Copenhagen, Denmark, 26 November 2023, pages 69–78. 2023. ACM. DOI: 10.1145/3605759.3625255

Google Scholar ePrint

[BP10]

J. Boyar and R. Peralta. A New Combinational Logic Minimization Technique with Applications to Cryptology. In Paola Festa, editor, Experimental Algorithms, 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings, volume 6049 of Lecture Notes in Computer Science, pages 178–189. 2010. Springer. DOI: 10.1007/978-3-642-13193-6_16

Google Scholar ePrint

[BP23]

A. Al Badawi and Y. Polyakov. Demystifying Bootstrapping in Fully Homomorphic Encryption. Cryptology ePrint Archive, Paper 2023/149. 2023.

Google Scholar ePrint

[BPR24]

N. Bon, D. Pointcheval, and M. Rivain. Optimized Homomorphic Evaluation of Boolean Functions. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2024(3):302–341, 2024. DOI: 10.46586/TCHES.V2024.I3.302-341

Google Scholar ePrint

[CCF⁺16]

Anne Canteaut, Sergiu Carpov, Caroline Fontaine, Tancrède Lepoint, María Naya-Plasencia, Pascal Paillier, and Renaud Sirdey. Stream Ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression. In Thomas Peyrin, editor, Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers, volume 9783 of Lecture Notes in Computer Science, pages 313–333. 2016. Springer. DOI: 10.1007/978-3-662-52993-5_16

Google Scholar ePrint

[CCP⁺24]

Jung Hee Cheon, Hyeongmin Choe, Alain Passelègue, Damien Stehlé, and Elias Suvanto. Attacks Against the INDCPA-D Security of Exact FHE Schemes. IACR Cryptol. ePrint Arch., 2024.

Google Scholar ePrint

[CGGI16]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In Jung Hee Cheon and Tsuyoshi Takagi, editors, ASIACRYPT 2016, Part I, volume 10031 of LNCS, pages 3–33, Hanoi, Vietnam. 2016. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-662-53887-6_1

Google Scholar ePrint

[CGGI17]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, pages 377–408, Hong Kong, China. 2017. Springer, Cham, Switzerland. DOI: 10.1007/978-3-319-70694-8_14

Google Scholar ePrint

[CGGI20]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: Fast Fully Homomorphic Encryption Over the Torus. Journal of Cryptology, 33(1):34–91, January 2020. DOI: 10.1007/s00145-019-09319-x

Google Scholar ePrint

[CHMS22]

Orel Cosseron, Clément Hoffmann, Pierrick Méaux, and François-Xavier Standaert. Towards Case-Optimized Hybrid Homomorphic Encryption - Featuring the Elisabeth Stream Cipher. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part III, volume 13793 of Lecture Notes in Computer Science, pages 32–67. 2022. Springer. DOI: 10.1007/978-3-031-22969-5_2

Google Scholar ePrint

[CIM19]

S. Carpov, M. Izabachène, and V. Mollimard. New Techniques for Multi-value Input Homomorphic Evaluation and Applications. In Topics in Cryptology – CT-RSA 2019: The Cryptographers' Track at the RSA Conference 2019, San Francisco, CA, USA, March 4–8, 2019, Proceedings, pages 106–126. 2019. DOI: 10.1007/978-3-030-12612-4_6

Google Scholar ePrint

[CKKS17]

Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, pages 409–437, Hong Kong, China. 2017. Springer, Cham, Switzerland. DOI: 10.1007/978-3-319-70694-8_15

Google Scholar ePrint

[CLOT21]

Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part III, volume 13092 of Lecture Notes in Computer Science, pages 670–699. 2021. Springer. DOI: 10.1007/978-3-030-92078-4_23

Google Scholar ePrint

[CSBB24]

Marina Checri, Renaud Sirdey, Aymen Boudguiga, and Jean-Paul Bultel. On the Practical CPA${}^{\mbox{D}}$ Security of "exact" and Threshold FHE Schemes and Libraries. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part III, volume 14922 of Lecture Notes in Computer Science, pages 3–33. 2024. Springer. DOI: 10.1007/978-3-031-68382-4_1

Google Scholar ePrint

[DGH⁺23]

Christoph Dobraunig, Lorenzo Grassi, Lukas Helminger, Christian Rechberger, Markus Schofnegger, and Roman Walch. Pasta: A Case for Hybrid Homomorphic Encryption. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(3):30–73, 2023. DOI: 10.46586/TCHES.V2023.I3.30-73

Google Scholar ePrint

[DM15]

Léo Ducas and Daniele Micciancio. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 617–640. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_24

Google Scholar ePrint

[DR02]

J. Daemen and V. Rijmen. The Design of Rijndael: AES - The Advanced Encryption Standard (Information Security and Cryptography). Springer, 1 edition. 2002.

Google Scholar ePrint

[GBA21]

Antonio Guimarães, Edson Borin, and Diego F. Aranha. Revisiting the functional bootstrap in TFHE. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2021(2):229–253, 2021. DOI: 10.46586/TCHES.V2021.I2.229-253

Google Scholar ePrint

[Gen09]

Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 169–178. 2009. ACM. DOI: 10.1145/1536414.1536440

Google Scholar ePrint

[GHS12]

Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic Evaluation of the AES Circuit. IACR Cryptol. ePrint Arch., 2012.

Google Scholar ePrint

[HS20]

Shai Halevi and Victor Shoup. Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Report 2020/1481. 2020.

Google Scholar ePrint

[LM20]

Baiyu Li and Daniele Micciancio. On the Security of Homomorphic Encryption on Approximate Numbers. IACR Cryptol. ePrint Arch., 2020.

Google Scholar ePrint

[Mat20]

K. Matsuoka. TFHEpp: pure C++ implementation of TFHE cryptosystem. https://github.com/virtualsecureplatform/TFHEpp. 2020.

Google Scholar ePrint

[Max19]

A. Maximov. AES MixColumn with 92 XOR gates. IACR Cryptol. ePrint Arch., 2019.

Google Scholar ePrint

[oST25]

National Institute of Standards and Technology. The NIST Threshold Call. 2025.

Google Scholar ePrint

[TCBS23]

D. Trama, P.-E. Clet, A. Boudguiga, and R. Sirdey. A Homomorphic AES Evaluation in Less than 30 Seconds by Means of TFHE. In Michael Brenner, Anamaria Costache, and Kurt Rohloff, editors, Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Copenhagen, Denmark, 26 November 2023, pages 79–90. 2023. ACM. DOI: 10.1145/3605759.3625260

Google Scholar ePrint

[TCBS25]

Daphné Trama, Pierre-Emmanuel Clet, Aymen Boudguiga, and Renaud Sirdey. Designing a General-Purpose 8-bit (T)FHE Processor Abstraction. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2025.

Google Scholar ePrint

[WLW⁺24]

B. Wei, X. Lu, R. Wang, K. Liu, Z. Li, and K. Wang. Thunderbird: Efficient Homomorphic Evaluation of Symmetric Ciphers in 3GPP by combining two modes of TFHE. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2024(3):530–573, 2024. DOI: 10.46586/TCHES.V2024.I3.530-573

Google Scholar ePrint

[WWL⁺23]

B. Wei, R. Wang, Z. Li, Q. Liu, and X. Lu. Fregata: Faster Homomorphic Evaluation of AES via TFHE. In Information Security: 26th International Conference, ISC 2023, Groningen, The Netherlands, November 15–17, 2023, Proceedings, pages 392–412, Berlin, Heidelberg. 2023. Springer-Verlag. DOI: 10.1007/978-3-031-49187-0_20

Google Scholar ePrint

[Zam22]

Zama. TFHE-rs: A Pure Rust Implementation of the TFHE Scheme for Boolean and Integer Arithmetics Over Encrypted Data. https://github.com/zama-ai/tfhe-rs. 2022.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ahmp-4tw9

History

Submitted: 2025-01-14
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Sonia Belaïd, Nicolas Bon, Aymen Boudguiga, Renaud Sirdey, Daphné Trama, and Nicolas Ye, Further Improvements in AES Execution over TFHE. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ahmp-4tw9.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/ahmp-4tw9,
         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}},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/ahmp-4tw9},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Sonia Belaïd
AU  - Nicolas Bon
AU  - Aymen Boudguiga
AU  - Renaud Sirdey
AU  - Daphné Trama
AU  - Nicolas Ye
PY  - 2025
TI  - Further Improvements in AES Execution over TFHE
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/ahmp-4tw9
UR  - https://doi.org/10.62056/ahmp-4tw9
AB  - <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 “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, 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 “Hippogryph”, which consistently combines the (byte-oriented) LUT-based approach with a generalization of the (boolean-oriented) $p$-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. </p>
ER  -

Sonia Belaïd, Nicolas Bon, Aymen Boudguiga, Renaud Sirdey, Daphné Trama, and Nicolas Ye, Further Improvements in AES Execution over TFHE. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ahmp-4tw9.