Cryptology ePrint Archive: Report 2016/817

Secure Obfuscation in a Weak Multilinear Map Model

Sanjam Garg and Eric Miles and Pratyay Mukherjee and Amit Sahai and Akshayaram Srinivasan 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, 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 $\text{NC}^1$.

Category / Keywords:

Original Publication (in the same form): IACR-TCC B--2016

Date: received 23 Aug 2016, last revised 26 Aug 2016

Contact author: sanjamg at berkeley edu, enmiles@gmail com, pratyay85@berkeley edu, amitsahai@gmail com, akshayaram@berkeley edu, mzhandry@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160826:075409 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]