Paper 2016/588

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

Eric Miles, 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.