### 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.

##### Metadata
Available format(s)
Publication info
Preprint.
Keywords
obfuscationmultilinear mapsannihilating polynomials
Contact author(s)
enmiles @ gmail com
History
2016-06-06: received
Short URL
https://ia.cr/2016/588
License

CC BY

BibTeX

@misc{cryptoeprint:2016/588,
author = {Eric Miles and Amit Sahai and Mark Zhandry},
title = {Secure obfuscation in a weak multilinear map model: A simple construction secure against all known attacks},
howpublished = {Cryptology ePrint Archive, Paper 2016/588},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/588}},
url = {https://eprint.iacr.org/2016/588}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.