Skip to main content

Secure Obfuscation in a Weak Multilinear Map Model

Author(s): Garg, Sanjam; Miles, Eric; Mukherjee, Pratyay; Sahai, Amit; Srinivasan, Akshayaram; et al

To refer to this page use:
Abstract: All known candidate indistinguishability obfuscation (iO) schemes rely on candidate multilinear maps. Until recently, the strongest proofs of security available for iO candidates were in a generic model that only allows “honest” use of the multilinear map. Most notably, in this model the zero-test procedure only reveals whether an encoded element is 0, and nothing more. However, this model is inadequate: there have been several attacks on multilinear maps that exploit extra information revealed by the zero-test procedure. In particular, Miles, Sahai and Zhandry (Crypto’16) recently gave a polynomial-time attack on several iO candidates when instantiated with the multilinear maps of Garg, Gentry, and Halevi (Eurocrypt’13), and also proposed a new “weak multilinear map model” that captures all known polynomial-time attacks on GGH13. In this work, we give a new iO candidate which can be seen as a small modification or generalization of the original candidate of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS’13). We prove its security in the weak multilinear map model, thus giving the first iO candidate that is provably secure against all known polynomial-time attacks on GGH13. The proof of security relies on a new assumption about the hardness of computing annihilating polynomials, and we show that this assumption is implied by the existence of pseudorandom functions in NC 1 .
Publication Date: 2016
Citation: Garg, Sanjam, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, and Mark Zhandry. "Secure Obfuscation in a Weak Multilinear Map Model." In Theory of Cryptography Conference (2016): pp. 241-268. doi:10.1007/978-3-662-53644-5_10
DOI: 10.1007/978-3-662-53644-5_10
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 241 - 268
Type of Material: Conference Article
Journal/Proceeding Title: Theory of Cryptography Conference
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.