FHE-based MPC; Fully Homomorphic Encryption; Related Key Attacks; Transciphering; Ciphertexts; FHE-based multi-party computation; Fully homomorphic encryption; Homomorphic-encryptions; Multi-party computation protocols; Multiparty computation; Related key attacks; Related keys; Software; Signal Processing; Computer Networks and Communications
Abstract :
[en] Transciphering (or Hybrid-Homomorphic Encryption, HHE) is an es-tablished technique for avoiding ciphertext expansion in HE applications, saving communication and storage resources. Recently, it has also been shown to be a funda-mental component in the practical construction of HE-based multi-party computation (MPC) protocols, being used both for input data and intermediary results (Smart, IMACC 2023). In these protocols, however, ciphers are used with keys that are jointly generated by multiple (possibly malicious) parties, which may require additional security assumptions that have been so far overlooked in the HHE literature. In this paper, we formalize this issue as a security against related-key attacks (RKA) problem and provide efficient solutions for it. We start by presenting an efficient method for homomorphically evaluating Mixed-Filter-Permutator (MFP) ciphers in leveled mode, enabling speedups of up to thousands of times compared to previous literature. For the multi-party scenario, we focus specifically on the Margrethe cipher (Hoffmann et al., INDOCRYPT 2023). We show that, contrary to other commonly used HHE ciphers (e.g. FLIP), Margrethe is out-of-the-box secure for any protocols that allow malicious parties to learn up to two related key streams, enabling security for the vast majority of static MPC protocols. For other cases, we quantify the loss of security based on the number of related key streams (which often depends on the number of malicious parties and specific protocol). Performance-wise, our implementation of Margrethe takes just 3.9 ms to transcipher 4-bit messages, being significantly faster than the state of the art in terms of latency.
Disciplines :
Computer science
Author, co-author :
Aranha, Diego F.; Aarhus University, Aarhus, Denmark
Guimarães, Antonio; IMDEA Software Institute, Madrid, Spain
Hoffmann, Clément; NTT Social Informatics Laboratories, Tokyo, Japan
MEAUX, Pierrick ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron
External co-authors :
yes
Language :
English
Title :
Secure and efficient transciphering for FHE-based MPC
Publication date :
05 June 2025
Journal title :
IACR Transactions on Cryptographic Hardware and Embedded Systems
This work was mostly conducted while the author was working in UCLouvain, Louvain-la-Neuve, Belgium Pierrick M\u00E9aux was supported by the ERC Advanced Grant no. 787390. This work has been funded in part by the ERC Advanced Grant number 101096871. This work is also supported by the Smart Networks and Services Joint Undertaking (SNS JU) under the European Union\u2019s Horizon Europe research and innovation programme in the scope of the CONFIDENTIAL6G project under Grant Agreement 101096435. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Commission. Neither the European Union nor the European Commission can be held responsible for them.
[AJLA+12] Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty Computation with Low Com-munication, Computation and Interaction via Threshold FHE. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EU-ROCRYPT 2012, Lecture Notes in Computer Science, pages 483–501, Berlin, Heidelberg, 2012. Springer.
[BCKS24] Youngjin Bae, Jung Hee Cheon, Jaehyung Kim, and Damien Stehlé. Boot-strapping Bits with CKKS. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, pages 94–123, Cham, 2024. Springer Nature Switzerland.
[BCL09] Lilya Budaghyan, Claude Carlet, and Gregor Leander. Constructing new apn functions from known ones. Finite Fields and Their Applications, 15(2):150– 159, 2009.
[BD94] Thomas. Beth and Cunsheng. Ding. On almost perfect nonlinear permutations. In Tor Helleseth, editor, Advances in Cryptology — EUROCRYPT ’93, pages 65–76, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg.
[BED+22] Javad Bahrami, Mohammad Ebrahimabadi, Jean-Luc Danger, Sylvain Guilley, and Naghmeh Karimi. Leakage power analysis in different s-box masking protection schemes. In Cristiana Bolchini, Ingrid Verbauwhede, and Ioana Vatajelu, editors, 2022 Design, Automation & Test in Europe Conference & Exhibition, DATE 2022, Antwerp, Belgium, March 14-23, 2022, pages 1263–1268. IEEE, 2022.
[BKSS25] Youngjin Bae, Jaehyung Kim, Damien Stehlé, and Elias Suvanto. Bootstrap-ping Small Integers With CKKS. In Kai-Min Chung and Yu Sasaki, editors, Advances in Cryptology – ASIACRYPT 2024, pages 330–360, Singapore, 2025. Springer Nature.
[BM13] Subhadeep Banik and Subhamoy Maitra. A differential fault attack on mickey 2.0. In Guido Bertoni and Jean-Sébastien Coron, editors, Cryptographic Hardware and Embedded Systems-CHES 2013, pages 215–232, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[BMS12] Subhadeep Banik, Subhamoy Maitra, and Santanu Sarkar. A differential fault attack on the grain family of stream ciphers. In Emmanuel Prouff and Patrick Schaumont, editors, Cryptographic Hardware and Embedded Systems – CHES 2012, pages 122–139, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
[BOS23] Thibault Balenbois, Jean-Baptiste Orfila, and Nigel P. Smart. Trivial transci-phering 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. ACM, 2023.
[BS85] László Babai and Vera T. Sós. Sidon sets in groups and induced subgraphs of cayley graphs. European Journal of Combinatorics, 6(2):101–114, 1985.
[Car21] Claude Carlet. Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, 2021.
[Car22] Claude Carlet. On apn functions whose graphs are maximal sidon sets. In LATIN 2022: Theoretical Informatics: 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings, page 243–254, Berlin, Heidelberg, 2022. Springer-Verlag.
[CCF+18] 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. Journal of Cryptology, 31(3):885–916, July 2018.
[CCH+24] Mingyu Cho, Woohyuk Chung, Jincheol Ha, Jooyoung Lee, Eun-Gyeol Oh, and Mincheol Son. Frast: TFHE-friendly Cipher Based on Random S-boxes, 2024. Publication info: Preprint.
[CCS19] Hao Chen, Ilaria Chillotti, and Yongsoo Song. Multi-key homomorphic encryption from TFHE. In ASIACRYPT (2), volume 11922 of Lecture Notes in Computer Science, pages 446–472. Springer, 2019.
[CDPP22] Kelong Cong, Debajyoti Das, Jeongeun Park, and Hilder V. L. Pereira. Sort-inghat: Efficient private decision tree evaluation via homomorphic encryption and transciphering. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pages 563–577. ACM, 2022.
[CDSU23] Gaëtan Cassiers, Henri Devillez, François-Xavier Standaert, and Balazs Ud-varhelyi. Efficient regression-based linear discriminant analysis for side-channel security evaluations: Towards analytical attacks against 32-bit implementa-tions. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023, Issue 3:270–293, 2023.
[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, Advances in Cryptology-ASIACRYPT 2016-22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer Science, pages 3–33, 2016.
[CGGI17] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster Packed Homomorphic Operations and Efficient Circuit Bootstrap-ping for TFHE. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, pages 377–408, Cham, 2017. Springer International Publishing.
[CHK+21] Jihoon Cho, Jincheol Ha, Seongkwang Kim, ByeongHak Lee, Joohee Lee, Jooyoung Lee, Dukjae Moon, and Hyojin Yoon. Transciphering framework for approximate homomorphic encryption. In Mehdi Tibouchi and Huax-iong 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 640–669. Springer, 2021.
[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. Springer, 2022.
[CM03] Nicolas T Courtois and Willi Meier. Algebraic attacks on stream ciphers with linear feedback. In Advances in Cryptology—EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003 Proceedings 22, pages 345–359. Springer, 2003.
[CMR17] Claude Carlet, Pierrick Méaux, and Yann Rotella. Boolean functions with restricted input and their robustness; application to the FLIP cipher. IACR Trans. Symmetric Cryptol., 2017(3), 2017.
[Cou03] Nicolas T Courtois. Fast algebraic attacks on stream ciphers with linear feed-back. In Advances in Cryptology-CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings 23, pages 176–194. Springer, 2003.
[CP08] Christophe De Cannière and Bart Preneel. Trivium. LNCS, New Stream Cipher Designs-The eSTREAM Finalists, page 244–266, 2008.
[CT18] Benoît Cogliati and Titouan Tanguy. Multi-user security bound for filter permutators in the random oracle model. Designs, Codes and Cryptography, 09 2018.
[DDK+23] Morten Dahl, Daniel Demmler, Sarah El Kazdadi, Arthur Meyre, Jean-Baptiste Orfila, Dragos Rotaru, Nigel P. Smart, Samuel Tap, and Michael Wal-ter. Noah’s ark: Efficient threshold-fhe using noise flooding. In WAHC@CCS, pages 35–46. ACM, 2023.
[DEG+18] Christoph Dobraunig, Maria Eichlseder, Lorenzo Grassi, Virginie Lallemand, Gregor Leander, Eik List, Florian Mendel, and Christian Rechberger. Rasta: A cipher with low anddepth and few ands per bit. In CRYPTO 2018, pages 662–692, 2018.
[DLR16] Sébastien Duval, Virginie Lallemand, and Yann Rotella. Cryptanalysis of the FLIP family of stream ciphers. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology-CRYPTO 2016-36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Pro-ceedings, Part I, volume 9814 of Lecture Notes in Computer Science, pages 457–475. Springer, 2016.
[GAH+23] Lorenzo Grassi, Irati Manterola Ayala, Martha Norberg Hovd, Morten Øy-garden, Håvard Raddum, and Qingju Wang. Cryptanalysis of symmetric primitives over rings and a key recovery attack on rubato. In Helena Hand-schuh and Anna Lysyanskaya, editors, Advances in Cryptology-CRYPTO 2023-43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part III, volume 14083 of Lecture Notes in Computer Science, pages 305–339. Springer, 2023.
[GBA24] Antonio Guimarães, Edson Borin, and Diego F. Aranha. MOSFHET: Optimized Software for FHE over the Torus. Journal of Cryptographic Engineering, July 2024.
[GGM24] François Gérard, Agnese Gini, and Pierrick Méaux. Toolip: How to find new instances of filip cipher with smaller key size and new filters. In Serge Vaudenay and Christophe Petit, editors, Progress in Cryptology-AFRICACRYPT 2024-15th International Conference on Cryptology in Africa, Douala, Cameroon, July 10-12, 2024, Proceedings, volume 14861 of Lecture Notes in Computer Science, pages 21–45. Springer, 2024.
[GHBJR23] Henri Gilbert, Rachelle Heim Boissier, Jérémy Jean, and Jean-René Reinhard. Cryptanalysis of elisabeth-4. In International Conference on the Theory and Application of Cryptology and Information Security, pages 256–284. Springer, 2023.
[HMS23] Clément Hoffmann, Pierrick Méaux, and François-Xavier Standaert. The patching landscape of elisabeth-4 and the mixed filter permutator paradigm. In Anupam Chattopadhyay, Shivam Bhasin, Stjepan Picek, and Chester Rebeiro, editors, Progress in Cryptology-INDOCRYPT 2023-24th International Conference on Cryptology in India, Goa, India, December 10-13, 2023, Proceedings, Part I, volume 14459 of Lecture Notes in Computer Science, pages 134–156. Springer, 2023.
[HR08] Michal Hojsík and Bohuslav Rudolf. Differential fault analysis of trivium. In Kaisa Nyberg, editor, Fast Software Encryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10-13, 2008, Revised Selected Papers, volume 5086 of Lecture Notes in Computer Science, pages 158–172. Springer, 2008.
[HS04] Jonathan J. Hoch and Adi Shamir. Fault analysis of stream ciphers. In Marc Joye and Jean-Jacques Quisquater, editors, Cryptographic Hardware and Embedded Systems-CHES 2004, pages 240–253, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.
[MCJS19] Pierrick Méaux, Claude Carlet, Anthony Journault, and François-Xavier Standaert. Improved filter permutators for efficient FHE: better instances and implementations. In Feng Hao, Sushmita Ruj, and Sourav Sen Gupta, editors, Progress in Cryptology-INDOCRYPT, volume 11898 of LNCS, pages 68–91. Springer, 2019.
[Méa22] Pierrick Méaux. On the algebraic immunity of direct sum constructions. Discret. Appl. Math., 320:223–234, 2022.
[MJSC16] Pierrick Méaux, Anthony Journault, François-Xavier Standaert, and Claude Carlet. Towards stream ciphers for efficient FHE with low-noise ciphertexts. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology-EUROCRYPT 2016-35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, volume 9665 of Lecture Notes in Computer Science, pages 311–343. Springer, 2016.
[MPP23] Pierrick Méaux, Jeongeun Park, and Hilder V. L. Pereira. Towards Practical Transciphering for FHE with Setup Independent of the Plaintext Space, 2023. Publication info: Published elsewhere. Communications in Cryptology.
[MR24] Pierrick Méaux and Dibyendu Roy. Theoretical differential fault attacks on flip and filip. Cryptography and Communications, pages 1936–2455, 2024.
[MSS17] S. Maitra, A. Siddhanti, and S. Sarkar. A differential fault attack on plantlet. IEEE Transactions on Computers, 66(10):1804–1808, 2017.
[NK93] Kaisa Nyberg and Lars Ramkilde Knudsen. Provable security against differential cryptanalysis. In Ernest F. Brickell, editor, Advances in Cryptology — CRYPTO’ 92, pages 566–574, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg.
[NLV11] Michael Naehrig, Kristin E. Lauter, and Vinod Vaikuntanathan. Can homomorphic encryption be practical? In CCSW, pages 113–124. ACM, 2011.
[Nyb94] Kaisa Nyberg. Differentially uniform mappings for cryptography. In Tor Helleseth, editor, Advances in Cryptology — EUROCRYPT ’93, pages 55–64, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg.
[RBM20] Dibyendu Roy, Bhagwan Bathe, and Subhamoy Maitra. Differential fault attack on kreyvium flip. IEEE Transactions on Computers, 2020.
[RKMR23] R Radheshwar, Meenakshi Kansal, Pierrick Méaux, and Dibyendu Roy. Differential fault attack on rasta and filip-dsm. IEEE Transactions on Computers, 72(8):2418–2425, 2023.
[Sma23] Nigel P. Smart. Practical and efficient fhe-based MPC. In IMACC, volume 14421 of Lecture Notes in Computer Science, pages 263–283. Springer, 2023.
[SSMC17] Akhilesh Siddhanti, Santanu Sarkar, Subhamoy Maitra, and Anupam Chat-topadhyay. Differential fault attack on grain v1, ACORN v3 and lizard. In Sk Subidh Ali, Jean-Luc Danger, and Thomas Eisenbarth, editors, Security, Privacy, and Applied Cryptography Engineering-7th International Confer-ence, SPACE 2017, Goa, India, December 13-17, 2017, Proceedings, volume 10662 of Lecture Notes in Computer Science, pages 247–263. Springer, 2017.
[WLW+24] Benqiang Wei, Xianhui Lu, Ruida Wang, Kun Liu, Zhihao Li, and Kunpeng Wang. Thunderbird: Efficient Homomorphic Evaluation of Symmetric Ciphers in 3GPP by combining two modes of TFHE. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(3):530–573, July 2024. Number: 3.
[WWL+24] Ruida Wang, Yundi Wen, Zhihao Li, Xianhui Lu, Benqiang Wei, Kun Liu, and Kunpeng Wang. Circuit Bootstrapping: Faster and Smaller. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, pages 342–372, Cham, 2024. Springer Nature Switzerland.
