Cryptology ePrint Archive: Report 2016/588

Secure obfuscation in a weak multilinear map model: A simple construction secure against all known attacks

Eric Miles and Amit Sahai and Mark Zhandry

Abstract: All known candidate indistinguishibility 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, the authors [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.

Subsequent to those attacks, Garg, Mukherjee, and Srinivasan [ePrint’16] gave a beautiful new candidate iO construction, using a new variant of the GGH13 multilinear map candidate, and proved its security in the weak multilinear map model assuming an explicit PRF in NC^1.

In this work, we give a simpler candidate iO construction, which can be seen as a small modification or generalization of the original iO candidate of Garg, Gentry, Halevi, Raykova, Sahai, and Waters [FOCS’13], and we prove its security in the weak multilinear map model. Our work has a number of benefits over that of GMS16.

• Our construction and analysis are simpler. In particular, the proof of our security theorem is 4 pages, versus 15 pages in GMS16.

• We do not require any change to the original GGH13 multilinear map candidate.

• We prove the security of our candidate under a more general assumption. One way that our assumption can be true is if there exists a PRF in NC^1.

• GMS16 required an explicit PRF in NC^1 to be "hard-wired" into their obfuscation candidate. In contrast, our scheme does not require any such hard-wiring. In fact, roughly speaking, our obfuscation candidate will depend only on the minimal size of such a PRF, and not on any other details of the PRF.

Category / Keywords: obfuscation, multilinear maps, annihilating polynomials

Date: received 4 Jun 2016

Contact author: enmiles at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160606:150423 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]