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: ia.cr/2016/588 Discussion forum: Show discussion | Start new discussion