Cryptology ePrint Archive: Report 2016/390

Obfuscation without the Vulnerabilities of Multilinear Maps

Sanjam Garg and Pratyay Mukherjee and Akshayaram Srinivasan

Abstract: Indistinguishability obfuscation is a central primitive in cryptography. Security of existing multilinear maps constructions on which current obfuscation candidates are based is poorly understood. In a few words, multilinear maps allow for checking if an arbitrary bounded degree polynomial on hidden values evaluates to zero or not. All known attacks on multilinear maps depend on the information revealed on computations that result in encodings of zero. This includes the recent annihilation attacks of Miles, Sahai and Zhandry [EPRINT 2016/147] on obfuscation candidates as a special case.

Building on a modification of the Garg, Gentry and Halevi [EUROCRYPT 2013] multilinear maps (GGH for short), we present a new obfuscation candidate that is resilient to these vulnerabilities. Specifically, in our construction the results of all computations yielding a zero provably hide all the secret system parameters. This is the first obfuscation candidate that weakens the security needed from the zero-test.

Formally, we prove security of our construction in a weakening of the idealized graded encoding model that accounts for all known vulnerabilities on GGH maps.

Category / Keywords: public-key cryptography / Obfuscation, Multilinear Map

Date: received 18 Apr 2016, last revised 15 Nov 2016

Contact author: pratyay85 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20161115:201609 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]