Document Open Access Logo

Factoring and Pairings Are Not Necessary for IO: Circular-Secure LWE Suffices

Authors Zvika Brakerski, Nico Döttling, Sanjam Garg, Giulio Malavolta

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.28.pdf
  • Filesize: 0.77 MB
  • 20 pages

Document Identifiers

Author Details

Zvika Brakerski
  • Weizmann Institute of Science, Rehovot, Israel
Nico Döttling
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Sanjam Garg
  • University of California, Berkeley, CA, USA
  • NTT Research, Sunnyvale, CA, USA
Giulio Malavolta
  • Max Planck Institute for Security and Privacy, Bochum, Germany

Funding

  • Brakerski, Zvika: Supported by the Israel Science Foundation (Grant No. 3426/21), and by the European Union Horizon 2020 Research and Innovation Program via ERC Project REACT (Grant 756482) and via Project PROMETHEUS (Grant 780701).
  • Döttling, Nico: Supported by the Helmholtz Association within the project "Trustworthy Federated Data Analytics” (TFDA) (funding number ZT-I- OO1 4).
  • Garg, Sanjam: Supported in part by DARPA under Agreement No. HR00112020026, AFOSR Award FA9550-19-1-0200, NSF CNS Award 1936826, and research grants by the Sloan Foundation, and Visa Inc. Any opinions, findings and conclusions or recommendations ex- pressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.
  • Malavolta, Giulio: The work described in this paper has been partially supported by the German Federal Ministry of Education and Research BMBF (grant 16K15K042, project 6GEM).

Cite AsGet BibTex

Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Factoring and Pairings Are Not Necessary for IO: Circular-Secure LWE Suffices. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.28

Abstract

We construct indistinguishability obfuscation (iO) solely under circular-security properties of encryption schemes based on the Learning with Errors (LWE) problem. Circular-security assumptions were used before to construct (non-leveled) fully-homomorphic encryption (FHE), but our assumption is stronger and requires circular randomness-leakage-resilience. In contrast with prior works, this assumption can be conjectured to be post-quantum secure; yielding the first provably secure iO construction that is (plausibly) post-quantum secure. Our work follows the high-level outline of the recent work of Gay and Pass [STOC 2021], who showed a way to remove the heuristic step from the homomorphic-encryption based iO approach of Brakerski, Döttling, Garg, and Malavolta [EUROCRYPT 2020]. They thus obtain a construction proved secure under circular security assumption of natural homomorphic encryption schemes - specifically, they use homomorphic encryption schemes based on LWE and DCR, respectively. In this work we show how to remove the DCR assumption and remain with a scheme based on the circular security of LWE alone. Along the way we relax some of the requirements in the Gay-Pass blueprint and thus obtain a scheme that is secure under a different assumption. Specifically, we do not require security in the presence of a key-cycle, but rather only in the presence of a key-randomness cycle. An additional contribution of our work is to point out a problem in one of the building blocks used by many iO candidates, including all existing provable post-quantum candidates. Namely, in the transformation from exponentially-efficient iO (XiO) from Lin, Pass, Seth and Telang [PKC 2016]. We show why their transformation inherently falls short of achieving the desired goal, and then rectify this situation by showing that shallow XiO (i.e. one where the obfuscator is depth-bounded) does translate to iO using LWE.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
Keywords
  • Cryptography
  • Obfuscation

Metrics

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

Related Versions

References

  1. Shweta Agrawal. Indistinguishability obfuscation without multilinear maps: New methods for bootstrapping and instantiation. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019, Part I, volume 11476 of Lecture Notes in Computer Science, pages 191-225, Darmstadt, Germany, May 19-23 2019. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-17653-2_7.
  2. Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. Indistinguishability obfuscation without multilinear maps: New paradigms via low degree weak pseudorandomness and security amplification. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019, Part III, volume 11694 of Lecture Notes in Computer Science, pages 284-332, Santa Barbara, CA, USA, August 18-22 2019. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-26954-8_10.
  3. Prabhanjan Ananth and Amit Sahai. Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology - EUROCRYPT 2017, Part I, volume 10210 of Lecture Notes in Computer Science, pages 152-181, Paris, France, April 30 - May 4 2017. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-56620-7_6.
  4. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 1-18, Santa Barbara, CA, USA, August 19-23 2001. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/3-540-44647-8_1.
  5. James Bartusek, Jiaxin Guan, Fermi Ma, and Mark Zhandry. Return of GGH15: Provable security against zeroizing attacks. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018: 16th Theory of Cryptography Conference, Part II, volume 11240 of Lecture Notes in Computer Science, pages 544-574, Panaji, India, November 11-14 2018. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-03810-6_20.
  6. Dan Boneh and Mark Zhandry. Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science, pages 480-499, Santa Barbara, CA, USA, August 17-21 2014. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-44371-2_27.
  7. Florian Bourse, Rafaël del Pino, Michele Minelli, and Hoeteck Wee. FHE circuit privacy almost for free. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 62-89, Santa Barbara, CA, USA, August 14-18 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-53008-5_3.
  8. Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Leveraging linear decryption: Rate-1 fully-homomorphic encryption and time-lock puzzles. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019: 17th Theory of Cryptography Conference, Part II, volume 11892 of Lecture Notes in Computer Science, pages 407-437, Nuremberg, Germany, December 1-5 2019. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-36033-7_16.
  9. Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Candidate iO from homomorphic encryption schemes. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, pages 79-109, Zagreb, Croatia, May 10-14 2020. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-45721-1_4.
  10. Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Factoring and pairings are not necessary for io: Circular-secure lwe suffices. Cryptology ePrint Archive, Report 2020/1024, 2020. URL: https://ia.cr/2020/1024.
  11. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In Rafail Ostrovsky, editor, 52nd Annual Symposium on Foundations of Computer Science, pages 97-106, Palm Springs, CA, USA, October 22-25 2011. IEEE Computer Society Press. URL: https://doi.org/10.1109/FOCS.2011.12.
  12. Yilei Chen, Craig Gentry, and Shai Halevi. Cryptanalyses of candidate branching program obfuscators. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology - EUROCRYPT 2017, Part III, volume 10212 of Lecture Notes in Computer Science, pages 278-307, Paris, France, April 30 - May 4 2017. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-56617-7_10.
  13. Yilei Chen, Vinod Vaikuntanathan, and Hoeteck Wee. GGH15 beyond permutation branching programs: Proofs, attacks, and candidates. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018, Part II, volume 10992 of Lecture Notes in Computer Science, pages 577-607, Santa Barbara, CA, USA, August 19-23 2018. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-96881-0_20.
  14. Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien Stehlé. Cryptanalysis of the multilinear map over the integers. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015, Part I, volume 9056 of Lecture Notes in Computer Science, pages 3-12, Sofia, Bulgaria, April 26-30 2015. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-46800-5_1.
  15. Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical multilinear maps over the integers. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 476-493, Santa Barbara, CA, USA, August 18-22 2013. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-642-40041-4_26.
  16. Ivan Damgård and Mats Jurik. A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In Kwangjo Kim, editor, PKC 2001: 4th International Workshop on Theory and Practice in Public Key Cryptography, volume 1992 of Lecture Notes in Computer Science, pages 119-136, Cheju Island, South Korea, February 13-15 2001. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/3-540-44586-2_9.
  17. Nico Döttling, Sanjam Garg, Divya Gupta, Peihan Miao, and Pratyay Mukherjee. Obfuscation from low noise multilinear maps. In Debrup Chakraborty and Tetsu Iwata, editors, Progress in Cryptology - INDOCRYPT 2018: 19th International Conference in Cryptology in India, volume 11356 of Lecture Notes in Computer Science, pages 329-352, New Delhi, India, December 9-12 2018. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-05378-9_18.
  18. Léo Ducas and Damien Stehlé. Sanitization of FHE ciphertexts. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016, Part I, volume 9665 of Lecture Notes in Computer Science, pages 294-310, Vienna, Austria, May 8-12 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-49890-3_12.
  19. Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 1-17, Athens, Greece, May 26-30 2013. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-642-38348-9_1.
  20. Sanjam Garg, Craig Gentry, Shai Halevi, and Mariana Raykova. Two-round secure MPC from indistinguishability obfuscation. In Yehuda Lindell, editor, TCC 2014: 11th Theory of Cryptography Conference, volume 8349 of Lecture Notes in Computer Science, pages 74-94, San Diego, CA, USA, February 24-26 2014. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-642-54242-8_4.
  21. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In 54th Annual Symposium on Foundations of Computer Science, pages 40-49, Berkeley, CA, USA, October 26-29 2013. IEEE Computer Society Press. URL: https://doi.org/10.1109/FOCS.2013.13.
  22. Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, and Mark Zhandry. Secure obfuscation in a weak multilinear map model. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B: 14th Theory of Cryptography Conference, Part II, volume 9986 of Lecture Notes in Computer Science, pages 241-268, Beijing, China, October 31 - November 3 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-53644-5_10.
  23. Romain Gay and Rafael Pass. Indistinguishability obfuscation from circular security. Cryptology ePrint Archive, Report 2020/1010, 2020. Google Scholar
  24. Craig Gentry, Sergey Gorbunov, and Shai Halevi. Graph-induced multilinear maps from lattices. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015: 12th Theory of Cryptography Conference, Part II, volume 9015 of Lecture Notes in Computer Science, pages 498-527, Warsaw, Poland, March 23-25 2015. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-46497-7_20.
  25. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing, pages 197-206, Victoria, BC, Canada, May 17-20 2008. ACM Press. URL: https://doi.org/10.1145/1374376.1374407.
  26. 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, Part I, volume 8042 of Lecture Notes in Computer Science, pages 75-92, Santa Barbara, CA, USA, August 18-22 2013. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-642-40041-4_5.
  27. Shafi Goldwasser and Guy N. Rothblum. On best-possible obfuscation. In Salil P. Vadhan, editor, TCC 2007: 4th Theory of Cryptography Conference, volume 4392 of Lecture Notes in Computer Science, pages 194-213, Amsterdam, The Netherlands, February 21-24 2007. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-540-70936-7_11.
  28. Satoshi Hada. Zero-knowledge and code obfuscation. In Tatsuaki Okamoto, editor, Advances in Cryptology - ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science, pages 443-457, Kyoto, Japan, December 3-7 2000. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/3-540-44448-3_34.
  29. Sam Hopkins, Aayush Jain, and Huijia Lin. Counterexamples to new circular security assumptions underlying io, 2021. Google Scholar
  30. Yupu Hu and Huiwen Jia. Cryptanalysis of GGH map. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016, Part I, volume 9665 of Lecture Notes in Computer Science, pages 537-565, Vienna, Austria, May 8-12 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-49890-3_21.
  31. Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. How to leverage hardness of constant-degree expanding polynomials overa ℝ to build i𝒪. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019, Part I, volume 11476 of Lecture Notes in Computer Science, pages 251-281, Darmstadt, Germany, May 19-23 2019. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-17653-2_9.
  32. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. Cryptology ePrint Archive, Report 2020/1003, 2020. Google Scholar
  33. Huijia Lin. Indistinguishability obfuscation from constant-degree graded encoding schemes. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016, Part I, volume 9665 of Lecture Notes in Computer Science, pages 28-57, Vienna, Austria, May 8-12 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-49890-3_2.
  34. Huijia Lin. Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017, Part I, volume 10401 of Lecture Notes in Computer Science, pages 599-629, Santa Barbara, CA, USA, August 20-24 2017. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-63688-7_20.
  35. Huijia Lin, Rafael Pass, Karn Seth, and Sidharth Telang. Indistinguishability obfuscation with non-trivial efficiency. In Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang, editors, PKC 2016: 19th International Conference on Theory and Practice of Public Key Cryptography, Part II, volume 9615 of Lecture Notes in Computer Science, pages 447-462, Taipei, Taiwan, March 6-9 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-49387-8_17.
  36. Huijia Lin and Stefano Tessaro. Indistinguishability obfuscation from trilinear maps and block-wise local PRGs. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017, Part I, volume 10401 of Lecture Notes in Computer Science, pages 630-660, Santa Barbara, CA, USA, August 20-24 2017. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-63688-7_21.
  37. Huijia Lin and Vinod Vaikuntanathan. Indistinguishability obfuscation from DDH-like assumptions on constant-degree graded encodings. In Irit Dinur, editor, 57th Annual Symposium on Foundations of Computer Science, pages 11-20, New Brunswick, NJ, USA, October 9-11 2016. IEEE Computer Society Press. URL: https://doi.org/10.1109/FOCS.2016.11.
  38. Fermi Ma and Mark Zhandry. The MMap strikes back: Obfuscation and new multilinear maps immune to CLT13 zeroizing attacks. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018: 16th Theory of Cryptography Conference, Part II, volume 11240 of Lecture Notes in Computer Science, pages 513-543, Panaji, India, November 11-14 2018. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-03810-6_19.
  39. Eric Miles, Amit Sahai, and Mark Zhandry. Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 629-658, Santa Barbara, CA, USA, August 14-18 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-53008-5_22.
  40. Rafail Ostrovsky, Anat Paskin-Cherniavsky, and Beni Paskin-Cherniavsky. Maliciously circuit-private FHE. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science, pages 536-553, Santa Barbara, CA, USA, August 17-21 2014. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-44371-2_30.
  41. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In David B. Shmoys, editor, 46th Annual ACM Symposium on Theory of Computing, pages 475-484, New York, NY, USA, May 31 - June 3 2014. ACM Press. URL: https://doi.org/10.1145/2591796.2591825.
  42. Hoeteck Wee and Daniel Wichs. Candidate obfuscation via oblivious lwe sampling. Cryptology ePrint Archive, Report 2020/1042, 2020. Google Scholar
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 Imprint Privacy Contact