Indistinguishability obfuscation

Abstract

At least since the initial public proposal of public-key cryptography based on computational hardness conjectures (Diffie and Hellman, 1976), cryptographers have contemplated the possibility of a “one-way compiler” that translates computer programs into “incomprehensible” but equivalent forms. And yet, the search for such a “one-way compiler” remained elusive for decades. We examine a formalization of this concept with the notion of indistinguishability obfuscation ($i\mathcal{O}$). Roughly speaking, $i\mathcal{O}$ requires that the compiled versions of any two equivalent programs (with the same size and running time) be indistinguishable to any efficient adversary. Finally, we show how to construct $i\mathcal{O}$ in such a way that we can prove the security of our $i\mathcal{O}$ scheme based on well-studied computational hardness conjectures in cryptography.