You are looking at a specific version 20140430:211113 of this paper. See the latest version.

Paper 2014/309

Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption

Craig Gentry and Allison Lewko and Amit Sahai and Brent Waters

Abstract

We revisit the question of constructing secure general-purpose indistinguishability obfusca- tion (iO), with a security reduction based on explicit computational assumptions. Previous to our work, such reductions were only known to exist based on instance-dependent 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 assump- tions for each pair of circuits to be obfuscated. In the more recent work of Pass et al. (ePrint 2013), 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 spe- cific 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 obfus- cation proven secure via a reduction to an instance-independent computational assumption over multilinear maps, namely, the Multilinear Subgroup Elimination Assumption. Our 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
obfuscation
Contact author(s)
amitsahai @ gmail com
History
2014-11-08: revised
2014-04-30: received
See all versions
Short URL
https://ia.cr/2014/309
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.