Document Open Access Logo

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Authors Daniel Apon, Nico Döttling, Sanjam Garg, Pratyay Mukherjee

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.38.pdf
  • Filesize: 0.62 MB
  • 16 pages

Document Identifiers

Author Details

Daniel Apon
Nico Döttling
Sanjam Garg
Pratyay Mukherjee

Cite As Get BibTex

Daniel Apon, Nico Döttling, Sanjam Garg, and Pratyay Mukherjee. Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.38

Abstract

Annihilation attacks, introduced in the work of Miles, Sahai, and Zhandry (CRYPTO 2016), are a class of polynomial-time attacks against several candidate indistinguishability obfuscation (IO) schemes, built from Garg, Gentry, and Halevi (EUROCRYPT 2013) multilinear maps. In this work, we provide a general efficiently-testable property for two single-input branching programs, called partial inequivalence, which we show is sufficient for our variant of annihilation attacks on several obfuscation constructions based on GGH13 multilinear maps.
	
We give examples of pairs of natural NC1 circuits, which - when processed via Barrington's Theorem - yield pairs of branching programs that are partially inequivalent.  As a consequence we are also able to show examples of "bootstrapping circuits,'' (albeit somewhat artificially crafted) used to obtain obfuscations for all circuits (given an obfuscator for NC1 circuits), in certain settings also yield partially inequivalent branching programs. Prior to our work, no attacks on any obfuscation constructions for these settings were known.

Subject Classification

Keywords
  • Obfuscation
  • Multilinear Maps
  • Cryptanalysis.

Metrics

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

References

  1. Martin R. Albrecht, Shi Bai, and Léo Ducas. A subfield lattice attack on overstretched NTRU assumptions - cryptanalysis of some FHE and graded encoding schemes. pages 153-178, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53018-4_6.
  2. Prabhanjan Ananth, Aayush Jain, Moni Naor, Amit Sahai, and Eylon Yogev. Universal constructions and robust combiners for indistinguishability obfuscation and witness encryption. pages 491-520, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53008-5_17.
  3. Prabhanjan Vijendra Ananth, Divya Gupta, Yuval Ishai, and Amit Sahai. Optimizing obfuscation: Avoiding Barrington’s theorem. pages 646-658, 2014. Google Scholar
  4. Daniel Apon, Nico Döttling, Sanjam Garg, and Pratyay Mukherjee. Cryptanalysis of indistinguishability obfuscations of circuits over ggh13. Cryptology ePrint Archive, Report 2016/1003, 2016. URL: http://eprint.iacr.org/2016/1003.
  5. Benny Applebaum. Bootstrapping obfuscators via fast pseudorandom functions. pages 162-172, 2014. URL: http://dx.doi.org/10.1007/978-3-662-45608-8_9.
  6. Benny Applebaum and Zvika Brakerski. Obfuscating circuits via composite-order graded encoding. pages 528-556, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46497-7_21.
  7. Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, and Mark Zhandry. Post-zeroizing obfuscation: New mathematical tools, and the case of evasive circuits. 2016. Google Scholar
  8. Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai. Protecting obfuscation against algebraic attacks. pages 221-238, 2014. URL: http://dx.doi.org/10.1007/978-3-642-55220-5_13.
  9. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. pages 1-18, 2001. Google Scholar
  10. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in nc¹. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 1-5, 1986. URL: http://dx.doi.org/10.1145/12130.12131.
  11. Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, and Sidharth Telang. Succinct randomized encodings and their applications. pages 439-448, 2015. Google Scholar
  12. Zvika Brakerski and Guy N. Rothblum. Virtual black-box obfuscation for all circuits via generic graded encoding. pages 1-25, 2014. URL: http://dx.doi.org/10.1007/978-3-642-54242-8_1.
  13. Yilei Chen, Craig Gentry, and Shai Halevi. Cryptanalyses of candidate branching program obfuscators. Cryptology ePrint Archive, Report 2016/998, To appear in EUROCRYPT 2017, 2016. URL: http://eprint.iacr.org/2016/998.
  14. Yilei Chen, Craig Gentry, and Shai Halevi. Cryptanalyses of candidate branching program obfuscators. Personal Communication, 2016. Google Scholar
  15. Jung Hee Cheon, Pierre-Alain Fouque, Changmin Lee, Brice Minaud, and Hansol Ryu. Cryptanalysis of the new CLT multilinear map over the integers. pages 509-536, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49890-3_20.
  16. Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien Stehlé. Cryptanalysis of the multilinear map over the integers. pages 3-12, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46800-5_1.
  17. Jung Hee Cheon, Jinhyuck Jeong, and Changmin Lee. An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low level encoding of zero. IACR Cryptology ePrint Archive, 2016:139, 2016. Report 2016/139. URL: http://eprint.iacr.org/2016/139.
  18. Jean-Sébastien Coron, Craig Gentry, Shai Halevi, Tancrède Lepoint, Hemanta K. Maji, Eric Miles, Mariana Raykova, Amit Sahai, and Mehdi Tibouchi. Zeroizing without low-level zeroes: New MMAP attacks and their limitations. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, volume 9215 of Lecture Notes in Computer Science, pages 247-266. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47989-6_12.
  19. Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint, and Mehdi Tibouchi. Cryptanalysis of GGH15 multilinear maps. pages 607-628, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53008-5_21.
  20. Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint, and Mehdi Tibouchi. Zeroizing attacks on indistinguishability obfuscation over CLT13. Cryptology ePrint Archive, Report 2016/1011, To appear in PKC 2017, 2016. URL: http://eprint.iacr.org/2016/1011.
  21. Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical multilinear maps over the integers. pages 476-493, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40041-4_26.
  22. Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering short generators of principal ideals in cyclotomic rings. pages 559-585, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49896-5_20.
  23. Nico Döttling, Sanjam Garg, Divya Gupta, Peihan Miao, and Pratyay Mukherjee. Obfuscation from low noise multilinear maps. Cryptology ePrint Archive, Report 2016/599, 2016. URL: http://eprint.iacr.org/2016/599.
  24. Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. pages 1-17, 2013. URL: http://dx.doi.org/10.1007/978-3-642-38348-9_1.
  25. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. pages 40-49, 2013. Google Scholar
  26. Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, and Mark Zhandry. Secure obfuscation in a weak multilinear map model. In TCC 2016-B, 2016. Google Scholar
  27. Craig Gentry, Sergey Gorbunov, and Shai Halevi. Graph-induced multilinear maps from lattices. pages 498-527, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46497-7_20.
  28. Vipul Goyal, Yuval Ishai, Amit Sahai, Ramarathnam Venkatesan, and Akshay Wadia. Founding cryptography on tamper-proof hardware tokens. pages 308-326, 2010. Google Scholar
  29. Yupu Hu and Huiwen Jia. Cryptanalysis of GGH map. pages 537-565, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49890-3_21.
  30. N. Kayal. The complexity of the annihilating polynomial. In Computational Complexity, 2009. CCC'09. 24th Annual IEEE Conference on, pages 184-193, July 2009. URL: http://dx.doi.org/10.1109/CCC.2009.37.
  31. Eric Miles, Amit Sahai, and Mor Weiss. Protecting obfuscation against arithmetic attacks. Cryptology ePrint Archive, Report 2014/878, 2014. URL: http://eprint.iacr.org/2014/878.
  32. Eric Miles, Amit Sahai, and Mark Zhandry. Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. pages 629-658, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53008-5_22.
  33. Rafael Pass, Karn Seth, and Sidharth Telang. Indistinguishability obfuscation from semantically-secure multilinear encodings. pages 500-517, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44371-2_28.
  34. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. pages 475-484, 2014. Google Scholar
  35. W. A. Stein et al. Sage Mathematics Software (Version 7.3). The Sage Development Team, 2016. http://www.sagemath.org. 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 About DROPS Imprint Privacy Contact