Paper 2014/309

Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption

Craig Gentry, Allison Lewko, Amit Sahai, and Brent Waters


We revisit the question of constructing secure general-purpose indistinguishability obfuscation (iO), with a security reduction based on explicit computational assumptions over multi- linear maps. Previous to our work, such reductions were only known to exist based on meta- assumptions and/or ad-hoc assumptions: In the original constructive work of Garg et al. (FOCS 2013), the underlying explicit computational assumption encapsulated an exponential family of assumptions for each pair of circuits to be obfuscated. In the more recent work of Pass et al. (Crypto 2014), the underlying assumption is a meta-assumption that also encapsulates an exponential family of assumptions, and this meta-assumption is invoked in a manner that captures the specific pair of circuits to be obfuscated. The assumptions underlying both these works substantially capture (either explicitly or implicitly) the actual structure of the obfuscation mechanism itself. In our work, we provide the first construction of general-purpose indistinguishability obfuscation proven secure via a reduction to a natural computational assumption over multilinear maps, namely, the Multilinear Subgroup Elimination Assumption. This assumption does not depend on the circuits to be obfuscated (except for its size), and does not correspond to the underlying structure of our obfuscator. The technical heart of our paper is our reduction, which gives a new way to argue about the security of indistinguishability obfuscation.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
amitsahai @ gmail com
2014-11-08: revised
2014-04-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Craig Gentry and Allison Lewko and Amit Sahai and Brent Waters},
      title = {Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2014/309},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.