Paper 2015/167

Post-Zeroizing Obfuscation: The case of Evasive Circuits

Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, and Mark Zhandry

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 present a construction for the special case of evasive functions. We show that our obfuscator survives all known attacks on the underlying multilinear maps, by proving that no 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 are now known to be false. To prove security, we introduce a new technique for analyzing polynomials over multilinear map encodings. 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 postzeroizing security. We also believe the technique is of independent interest, as it yields efficiency improvements for existing schemes.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Obfuscationzeroizing attacksevasive functions
Contact author(s)
enmiles @ cs ucla edu
History
2015-07-14: last of 3 revisions
2015-02-27: received
See all versions
Short URL
https://ia.cr/2015/167
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/167,
      author = {Saikrishna Badrinarayanan and Eric Miles and Amit Sahai and Mark Zhandry},
      title = {Post-Zeroizing Obfuscation: The case of Evasive Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2015/167},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/167}},
      url = {https://eprint.iacr.org/2015/167}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.