Secure obfuscation in a weak multilinear map model

Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

54 Scopus citations

Abstract

All known candidate indistinguishability 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 NC1.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 14th International Conference, TCC 2016-B, Proceedings
EditorsAdam Smith, Martin Hirt
PublisherSpringer Verlag
Pages241-268
Number of pages28
ISBN (Print)9783662536438
DOIs
StatePublished - 2016
Event14th International Conference on Theory of Cryptography, TCC 2016-B - Beijing, China
Duration: Oct 31 2016Nov 3 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9986 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th International Conference on Theory of Cryptography, TCC 2016-B
Country/TerritoryChina
CityBeijing
Period10/31/1611/3/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Secure obfuscation in a weak multilinear map model'. Together they form a unique fingerprint.

Cite this