Document Open Access Logo

Bootstrapping Homomorphic Encryption via Functional Encryption

Authors Nir Bitansky, Tomer Solomon

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.17.pdf
  • Filesize: 0.79 MB
  • 23 pages

Document Identifiers

Author Details

Nir Bitansky
  • Tel Aviv University, Israel
Tomer Solomon
  • Tel Aviv University, Israel

Funding

This work was supported in part by the European Research Council (ERC) under the European Union’s Horizon Europe research and innovation programme (grant agreement No. 101042417, acronym SPP) and by ISF grant 2137/19.

Cite As Get BibTex

Nir Bitansky and Tomer Solomon. Bootstrapping Homomorphic Encryption via Functional Encryption. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.17

Abstract

Homomorphic encryption is a central object in modern cryptography, with far-reaching applications. Constructions supporting homomorphic evaluation of arbitrary Boolean circuits have been known for over a decade, based on standard lattice assumptions. However, these constructions are leveled, meaning that they only support circuits up to some a-priori bounded depth. These leveled constructions can be bootstrapped into fully homomorphic ones, but this requires additional circular security assumptions, which are construction-dependent, and where reductions to standard lattice assumptions are no longer known. Alternative constructions are known based on indistinguishability obfuscation, which has been recently constructed under standard assumptions. However, this alternative requires subexponential hardness of the underlying primitives.
We prove a new bootstrapping theorem based on functional encryption, which is known based on standard polynomial hardness assumptions. As a result we obtain the first fully homomorphic encryption scheme that avoids both circular security assumptions and super-polynomial hardness assumptions. The construction is secure against uniform adversaries, and can be made non-uniformly secure assuming a generalization of the time-hierarchy theorem, which follows for example from non-uniform ETH.
At the heart of the construction is a new proof technique based on cryptographic puzzles and decomposable obfuscation. Unlike most cryptographic reductions, our security reduction does not fully treat the adversary as a black box, but rather makes explicit use of its running time (or circuit size).

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
Keywords
  • Fully Homomorphic Encryption
  • Polynomial Assumptions
  • Cryptographic Puzzles

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Thomas Agrikola, Geoffroy Couteau, and Dennis Hofheinz. The usefulness of sparsifiable inputs: How to avoid subexponential io. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, Public-Key Cryptography - PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part I, volume 12110 of Lecture Notes in Computer Science, pages 187-219. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45374-9_7.
  2. Joël Alwen, Manuel Barbosa, Pooya Farshim, Rosario Gennaro, S. Dov Gordon, Stefano Tessaro, and David A. Wilson. On the relationship between functional encryption, obfuscation, and fully homomorphic encryption. In Martijn Stam, editor, Cryptography and Coding - 14th IMA International Conference, IMACC 2013, Oxford, UK, December 17-19, 2013. Proceedings, volume 8308 of Lecture Notes in Computer Science, pages 65-84. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-45239-0_5.
  3. Prabhanjan Ananth and Alex Lombardi. Succinct garbling schemes from functional encryption through a local simulation paradigm. In Amos Beimel and Stefan Dziembowski, editors, Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part II, volume 11240 of Lecture Notes in Computer Science, pages 455-472. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-03810-6_17.
  4. Boaz Barak. A probabilistic-time hierarchy theorem for "slightly non-uniform" algorithms. In Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings, pages 194-208, 2002. Google Scholar
  5. Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, and Sidharth Telang. Succinct randomized encodings and their applications. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 439-448. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746574.
  6. Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, and Brent Waters. Time-lock puzzles from randomized encodings. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 345-356. ACM, 2016. URL: https://doi.org/10.1145/2840728.2840745.
  7. Nir Bitansky and Vinod Vaikuntanathan. Indistinguishability obfuscation from functional encryption. J. ACM, 65(6):39:1-39:37, 2018. URL: https://doi.org/10.1145/3234511.
  8. Dan Boneh and Brent Waters. Constrained pseudorandom functions and their applications. In Kazue Sako and Palash Sarkar, editors, Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part II, volume 8270 of Lecture Notes in Computer Science, pages 280-300. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-42045-0_15.
  9. Elette Boyle, Shafi Goldwasser, and Ioana Ivan. Functional signatures and pseudorandom functions. In Hugo Krawczyk, editor, Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings, volume 8383 of Lecture Notes in Computer Science, pages 501-519. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-54631-0_29.
  10. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 309-325. ACM, 2012. URL: https://doi.org/10.1145/2090236.2090262.
  11. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 97-106. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.12.
  12. Ran Canetti, Justin Holmgren, Abhishek Jain, and Vinod Vaikuntanathan. Succinct garbling and indistinguishability obfuscation for RAM programs. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 429-437. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746621.
  13. 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. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-46497-7_19.
  14. Sanjam Garg, Omkant Pandey, and Akshayaram Srinivasan. Revisiting the cryptographic hardness of finding a nash equilibrium. 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 579-604. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53008-5_20.
  15. Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan, and Mark Zhandry. Breaking the sub-exponential barrier in obfustopia. 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 III, volume 10212 of Lecture Notes in Computer Science, pages 156-181, 2017. URL: https://doi.org/10.1007/978-3-319-56617-7_6.
  16. Sanjam Garg and Akshayaram Srinivasan. A simple construction of io for turing machines. In Amos Beimel and Stefan Dziembowski, editors, Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part II, volume 11240 of Lecture Notes in Computer Science, pages 425-454. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-03810-6_16.
  17. 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. ACM, 2009. URL: https://doi.org/10.1145/1536414.1536440.
  18. Craig Gentry, Allison Bishop Lewko, Amit Sahai, and Brent Waters. Indistinguishability obfuscation from the multilinear subgroup elimination assumption. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 151-170. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.19.
  19. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 75-92. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40041-4_5.
  20. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792-807, 1986. URL: http://dblp.uni-trier.de/db/journals/jacm/jacm33.html#GoldreichGM86.
  21. Juris Hartmanis and Richard Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285-306, 1965. Google Scholar
  22. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Frank Thomson Leighton and Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 220-229. ACM, 1997. URL: https://doi.org/10.1145/258533.258590.
  23. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 60-73. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451093.
  24. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from LPN over dollarbackslashmathbb F_pdollar, dlin, and prgs in nc^0. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part I, volume 13275 of Lecture Notes in Computer Science, pages 670-699. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-06944-4_23.
  25. Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. Delegatable pseudorandom functions and applications. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS'13, Berlin, Germany, November 4-8, 2013, pages 669-684. ACM, 2013. URL: https://doi.org/10.1145/2508859.2516668.
  26. Fuyuki Kitagawa, Ryo Nishimaki, Keisuke Tanaka, and Takashi Yamakawa. Adaptively secure and succinct functional encryption: Improving security and efficiency, simultaneously. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part III, volume 11694 of Lecture Notes in Computer Science, pages 521-551. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-26954-8_17.
  27. Venkata Koppula, Allison Bishop Lewko, and Brent Waters. Indistinguishability obfuscation for turing machines with unbounded memory. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 419-428. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746614.
  28. Qipeng Liu and Mark Zhandry. Decomposable obfuscation: A framework for building applications of obfuscation from polynomial hardness. J. Cryptol., 34(3):35, 2021. URL: https://doi.org/10.1007/s00145-021-09400-4.
  29. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  30. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 84-93. ACM, 2005. URL: https://doi.org/10.1145/1060590.1060603.
  31. Ronald L. Rivest, Adi Shamir, and David A. Wagner. Time-lock puzzles and timed-release crypto. Technical report, MIT, 1996. Google Scholar
  32. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 475-484. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591825.
  33. Mark Zhandry. The magic of elfs. 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 I, volume 9814 of Lecture Notes in Computer Science, pages 479-508. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53018-4_18.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact