Paper 2016/390

Obfuscation without the Vulnerabilities of Multilinear Maps

Sanjam Garg, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
ObfuscationMultilinear Map
Contact author(s)
pratyay85 @ gmail com
History
2016-11-15: last of 4 revisions
2016-04-19: received
See all versions
Short URL
https://ia.cr/2016/390
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/390,
      author = {Sanjam Garg and Pratyay Mukherjee and Akshayaram Srinivasan},
      title = {Obfuscation without the Vulnerabilities of Multilinear Maps},
      howpublished = {Cryptology ePrint Archive, Paper 2016/390},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/390}},
      url = {https://eprint.iacr.org/2016/390}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.