Monday, February 29, 2016
10:00 AM in Rice 314
Advisor & Chair:Mohammad Mahmoody
Attending Faculty: David Evans, Gabriel Robins, abhi shelat.
Title:On the Power of Algebraic Tools in Code Obfuscation
Obfuscating programs to make them “unintelligible” while preserving their functionality is one of the most sought after holy grails in cryptography due to its numerous applications. The celebrated work of Barak et al. [BGI+01] was the first to launch a formal study of this notion in its various forms. Virtual Black-Box (VBB) obfuscation is a strong form of obfuscation in which the obfuscated code does not reveal any secret bit about the obfuscated program unless that information could already be obtained through a black-box access to the program. The same work [BGI+01] also defined a weaker notion of obfuscation, called indistinguishability obfuscation (iO). The security of iO only requires that the obfuscation of two equivalent and same-size circuits C1, C2 be computationally indistinguishable to efficient adversaries.
In this proposal, studying the complexity of obfuscation plays the central role. We already know that VBB obfuscation is impossible in general, but that shall not stop us from exploring the possibility of VBB in some idealized models or achieving VBB for a special class of functions. The question of whether VBB obfuscation is possible in some appealing and natural idealized models is one of the fundamental questions in cryptography. There are lots of interesting idealized models such as TDP, generic group model of Shoup [Sho97] (GGM) and GEM [BGK+14]. One can ask the same questions about IO as well. In this proposal the main focus is to study the existence of VBB obfuscation and IO in some of these idealized models.