Post-zeroizing obfuscation: New mathematical tools, and the case of evasive circuits

Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations

Abstract

Recent devastating attacks by Cheon et al. [Eurocrypt’15] and others have highlighted significant gaps in our intuition about security in candidate multilinear map schemes, and in candidate obfuscators that use them. The new attacks, and some that were previously known, are typically called “zeroizing” attacks because they all crucially rely on the ability of the adversary to create encodings of 0. In this work, we initiate the study of post-zeroizing obfuscation, and we obtain a key new mathematical tool to analyze security in a postzeroizing world. Our new mathematical tool allows for analyzing polynomials constructed by the adversary when given encodings of randomized matrices arising from a general matrix branching program. This technique shows that the types of encodings an adversary can create are much more restricted than was previously known, and is a crucial step toward achieving post-zeroizing security. We also believe the technique is of independent interest, as it yields efficiency improvements for existing schemes –efficiency improvements that have already found application in other settings. Finally, we show how to apply our new mathematical tool to the special case of evasive functions. We show that our obfuscator survives all known attacks on the underlying multilinear maps, by proving that no top-level encodings of 0 can be created by a generic-model adversary. Previous obfuscators (for both evasive and general functions) were either analyzed in a less-conservative “pre-zeroizing” model that does not capture recent attacks, or were proved secure relative to assumptions that no longer have any plausible instantiation due to zeroizing attacks.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsMarc Fischlin, Jean-Sebastien Coron
PublisherSpringer Verlag
Pages764-791
Number of pages28
ISBN (Print)9783662498958
DOIs
StatePublished - Jan 1 2016
Event35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016 - Vienna, Austria
Duration: May 8 2016May 12 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9666
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016
CountryAustria
CityVienna
Period5/8/165/12/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Post-zeroizing obfuscation: New mathematical tools, and the case of evasive circuits'. Together they form a unique fingerprint.

  • Cite this

    Badrinarayanan, S., Miles, E., Sahai, A., & Zhandry, M. (2016). Post-zeroizing obfuscation: New mathematical tools, and the case of evasive circuits. In M. Fischlin, & J-S. Coron (Eds.), Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 764-791). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9666). Springer Verlag. https://doi.org/10.1007/978-3-662-49896-5_27