Paper 2013/631

Protecting Obfuscation Against Algebraic Attacks

Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai

Abstract

Recently, Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013) constructed a general-purpose obfuscating compiler for NC1 circuits. We describe a simplified variant of this compiler, and prove that it is a virtual black box obfuscator in a generic multilinear map model. This improves on Brakerski and Rothblum (eprint 2013) who gave such a result under a strengthening of the Exponential Time Hypothesis. We remove this assumption, and thus resolve an open question of Garg et al. As shown by Garg et al., a compiler for NC1 circuits can be bootstrapped to a compiler for all polynomial-sized circuits under the learning with errors (LWE) hardness assumption. Our result shows that there is a candidate obfuscator that cannot be broken by algebraic attacks, hence reducing the task of creating secure obfuscators in the plain model to obtaining sufficiently strong security guarantees on candidate instantiations of multilinear maps.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in EUROCRYPT 2014
Keywords
ObfuscationMultilinear Maps
Contact author(s)
omerpa @ gmail com
History
2014-05-13: last of 3 revisions
2013-10-01: received
See all versions
Short URL
https://ia.cr/2013/631
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/631,
      author = {Boaz Barak and Sanjam Garg and Yael Tauman Kalai and Omer Paneth and Amit Sahai},
      title = {Protecting Obfuscation Against Algebraic Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/631},
      year = {2013},
      url = {https://eprint.iacr.org/2013/631}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.