Indistinguishability Obfuscation from Well-Studied Assumptions

Type Thesis

Rate 0.0 /5

Details

Files

Reviews

Download

Summary

Can we efficiently compile a computer program P into another one say \tilde{P}, which has the same functionality as P on every input, but otherwise is as unintelligible as possible? This question was asked in 1976 by the Turing award winning work of Diffie-Hellman (STOC 1976). Such a compiler is called as Obfuscation. It is not hard to see that such a notion will find lots of application so much so that today it is one of the most versatile primitives in cryptography. The work of Barak et. al. (Crypto 2001) and Goldwasser and Rothblum (TCC 2007) established that in order to construct an obfuscation scheme which provides best possible unintelligibility guarantees, it suffices to construct what is called as an Indistinguishibility Obfuscation (iO) scheme. An iO scheme is an obfuscation scheme that only hides implementation differences. Such a scheme guarantees that for every two programs P_0,P_1 of the same description size, same running time having the same input output behavior, but otherwise having different internal details iO(P_0) is indistinguishabile to iO(P_1). Unfortunately, up until now it was not clear if such a primitive can even exist. All the known constructions were heuristic, based on newly stated assumptions, and most of the times subject to cycles of attacks and fixes. In this thesis, we present the first feasibility result of an obfuscation scheme by constructing an obfuscation scheme from well-studied cryptographic assumptions. We prove: