Indistinguishability obfuscation (Q6198645)

Summary: At least since the initial public proposal of public-key cryptography based on computational hardness conjectures [\textit{W. Diffie} and \textit{M. E. Hellman}, IEEE Trans. Inf. Theory 22, 644--654 (1976; Zbl 0435.94018)], 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. For the entire collection see [Zbl 07816360].