Fully Composable Homomorphic Encryption
Authors
Daniele Micciancio
Daniele Micciancio
UC San Diego, La Jolla, USA
daniele at cs dot ucsd dot edu
daniele at cs dot ucsd dot edu
Abstract
The traditional definition of fully homomorphic encryption (FHE) is not composable, i.e., it does not guarantee that evaluating two (or more) homomorphic computations in a sequence produces correct results. We formally define and investigate a stronger notion of homomorphic encryption which we call "fully composable homomorphic encryption", or "composable FHE". The definition is both simple and powerful: it does not directly involve the evaluation of multiple functions, and yet it supports the arbitrary composition of homomorphic evaluations. On the technical side, we compare the new definition with other definitions proposed in the past, proving both implications and separations, and show how the "bootstrapping" technique of (Gentry, STOC 2009) can be formalized as a method to transform a (non-composable, circular secure) homomorphic encryption scheme into a fully composable one. We use this formalization of bootstrapping to formulate a number of conjectures and open problems.
References
[ABMP24]
Andreea Alexandru, Ahmad Al Badawi, Daniele Micciancio, and Yuriy Polyakov. Application-Aware Approximate Homomorphic Encryption: Configuring FHE for Practical Use. IACR Cryptol. ePrint Arch., 2024.
[ACPS09]
Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. In Shai Halevi, editor, Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings, volume 5677 of Lecture Notes in Computer Science, pages 595-618. 2009. Springer. DOI: 10.1007/978-3-642-03356-8_35
[AGHV25]
Adi Akavia, Craig Gentry, Shai Halevi, and Margarita Vald. Achievable CCA2 Relaxation for Homomorphic Encryption. J. Cryptol., 38(1):5, 2025. DOI: 10.1007/S00145-024-09526-1
[AP16]
Navid Alamati and Chris Peikert. Three's Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE. 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, Proceedings, Part II, volume 9815 of Lecture Notes in Computer Science, pages 659-680. 2016. Springer. DOI: 10.1007/978-3-662-53008-5_23
[AV21]
Adi Akavia and Margarita Vald. On the Privacy of Protocols based on CPA-Secure Homomorphic Encryption. IACR Cryptol. ePrint Arch., 2021.
[BG10]
Zvika Brakerski and Shafi Goldwasser. Circular and Leakage Resilient Public-Key Encryption under Subgroup Indistinguishability - (or: Quadratic Residuosity Strikes Back). In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 1–20. 2010. Springer. DOI: 10.1007/978-3-642-14623-7_1
[BGK11]
Zvika Brakerski, Shafi Goldwasser, and Yael Tauman Kalai. Black-Box Circular-Secure Encryption beyond Affine Functions. In Yuval Ishai, editor, Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings, volume 6597 of Lecture Notes in Computer Science, pages 201–218. 2011. Springer. DOI: 10.1007/978-3-642-19571-6_13
[BGV14]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Trans. Comput. Theory, 6(3):13:1–13:36, 2014. DOI: 10.1145/2633600
[BHHO08]
Dan Boneh, Shai Halevi, Michael Hamburg, and Rafail Ostrovsky. Circular-Secure Encryption from Decision Diffie-Hellman. In David A. Wagner, editor, Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008. Proceedings, volume 5157 of Lecture Notes in Computer Science, pages 108–125. 2008. Springer. DOI: 10.1007/978-3-540-85174-5_7
[Bra12]
Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 868-886. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_50
[Bra19]
Zvika Brakerski. Fundamentals of fully homomorphic encryption. In Oded Goldreich, editor, Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pages 543-563. ACM 2019. DOI: 10.1145/3335741.3335762
[BV14]
Zvika Brakerski and Vinod Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. SIAM J. Comput., 43(2):831-871, 2014. Preliminary version in FOCS 2011. DOI: 10.1137/120868669
[CGGI20]
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: Fast Fully Homomorphic Encryption Over the Torus. J. Cryptol., 33(1):34–91, 2020. DOI: 10.1007/s00145-019-09319-x
[CHI+21]
Megan Chen, Carmit Hazay, Yuval Ishai, Yuriy Kashnikov, Daniele Micciancio, Tarik Riviere, Abhi Shelat, Muthuramakrishnan Venkitasubramaniam, and Ruihan Wang. Diogenes: Lightweight Scalable RSA Modulus Generation with a Dishonest Majority. In 42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021, pages 590-607. 2021. IEEE. DOI: 10.1109/SP40001.2021.00025
[CLTV15]
Ran Canetti, Huijia Lin, Stefano Tessaro, and Vinod Vaikuntanathan. Obfuscation of Probabilistic Circuits and Applications. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II, volume 9015 of Lecture Notes in Computer Science, pages 468–497. 2015. Springer. DOI: 10.1007/978-3-662-46497-7_19
[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
[DS16]
Léo Ducas and Damien Stehlé. Sanitization of FHE 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 294-310. 2016. Springer. DOI: 10.1007/978-3-662-49890-3_12
[Gen09a]
Craig Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, USA, 2009.
[Gen09b]
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
[GHV10]
Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. i-Hop Homomorphic Encryption and Rerandomizable Yao Circuits. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 155-172. 2010. Springer. DOI: 10.1007/978-3-642-14623-7_9
[GKW17a]
Rishab Goyal, Venkata Koppula, and Brent Waters. Separating IND-CPA and Circular Security for Unbounded Length Key Cycles. In Serge Fehr, editor, Public-Key Cryptography - PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, March 28-31, 2017, Proceedings, Part I, volume 10174 of Lecture Notes in Computer Science, pages 232-246. 2017. Springer. DOI: 10.1007/978-3-662-54365-8_10
[GKW17b]
Rishab Goyal, Venkata Koppula, and Brent Waters. Separating Semantic and Circular Security for Symmetric-Key Bit Encryption from the Learning with Errors Assumption. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II, volume 10211 of Lecture Notes in Computer Science, pages 528-557. 2017. DOI: 10.1007/978-3-319-56614-6_18
[GM84]
Shafi Goldwasser and Silvio Micali. Probabilistic Encryption. J. Comput. Syst. Sci., 28(2):270–299, 1984. DOI: 10.1016/0022-0000(84)90070-9
[Hal17]
Shai Halevi. Homomorphic Encryption. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pages 219-276. Springer International Publishing 2017. DOI: 10.1007/978-3-319-57048-8_5
[HK17]
Mohammad Hajiabadi and Bruce M. Kapron. Toward Fine-Grained Blackbox Separations Between Semantic and Circular-Security Notions. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II, volume 10211 of Lecture Notes in Computer Science, pages 561-591. 2017. DOI: 10.1007/978-3-319-56614-6_19
[HNP+03]
Nick Howgrave-Graham, Phong Q. Nguyen, David Pointcheval, John Proos, Joseph H. Silverman, Ari Singer, and William Whyte. The Impact of Decryption Failures on the Security of NTRU Encryption. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, pages 226–246. 2003. Springer. DOI: 10.1007/978-3-540-45146-4_14
[KM20]
Fuyuki Kitagawa and Takahiro Matsuda. Circular Security Is Complete for KDM Security. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part I, volume 12491 of Lecture Notes in Computer Science, pages 253-285. 2020. Springer. DOI: 10.1007/978-3-030-64837-4_9
[KRW15]
Venkata Koppula, Kim Ramchen, and Brent Waters. Separations in Circular Security for Arbitrary Length Key Cycles. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II, volume 9015 of Lecture Notes in Computer Science, pages 378–400. 2015. Springer. DOI: 10.1007/978-3-662-46497-7_15
[KW16]
Venkata Koppula and Brent Waters. Circular Security Separations for Arbitrary Length Cycles from LWE. 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, Proceedings, Part II, volume 9815 of Lecture Notes in Computer Science, pages 681-700. 2016. Springer. DOI: 10.1007/978-3-662-53008-5_24
[LM21]
Baiyu Li and Daniele Micciancio. On the Security of Homomorphic Encryption on Approximate Numbers. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, volume 12696 of Lecture Notes in Computer Science, pages 648-677. 2021. Springer. DOI: 10.1007/978-3-030-77870-5_23
[LMK+23]
Yongwoo Lee, Daniele Micciancio, Andrey Kim, Rakyong Choi, Maxim Deryabin, Jieun Eom, and Donghoon Yoo. Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III, volume 14006 of Lecture Notes in Computer Science, pages 227-256. 2023. Springer. DOI: 10.1007/978-3-031-30620-4_8
[Mic22a]
Daniele Micciancio. Fully Homomorphic Encryption 10 years later: definitions and open problems. Presentation at Simons Institute. May 2022.
[Mic22b]
Daniele Micciancio. Fully Homomorphic Encryption: Definitional issues and open problems. Presentation at FHE.org. May 2022.
[MP21]
Daniele Micciancio and Yuriy Polyakov. Bootstrapping in FHEW-like Cryptosystems. In WAHC '21: Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Virtual Event, Korea, 15 November 2021, pages 17–28. 2021. WAHC@ACM. DOI: 10.1145/3474366.3486924
[MV24]
Daniele Micciancio and Vinod Vaikuntanathan. SoK: Learning with Errors, Circular Security, and Fully Homomorphic Encryption. In Qiang Tang and Vanessa Teague, editors, Public-Key Cryptography - PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, Sydney, NSW, Australia, April 15-17, 2024, Proceedings, Part IV, volume 14604 of Lecture Notes in Computer Science, pages 291-321. 2024. Springer. DOI: 10.1007/978-3-031-57728-4_10
[MW18]
Daniele Micciancio and Michael Walter. On the Bit Security of Cryptographic Primitives. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I, volume 10820 of Lecture Notes in Computer Science, pages 3-28. 2018. Springer. DOI: 10.1007/978-3-319-78381-9_1
PDF
History
Submitted: 2024-10-03
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Daniele Micciancio, Fully Composable Homomorphic Encryption. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ak5wl86bm.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.