UC San Diego

Indistinguishability obfuscation is an extraordinarily versatile primitive, leading many to search for candidate constructions. Of these candidates, many rely on “bootstrapping” techniques that transform an obfuscator for a small class of circuits into an obfuscator for larger class of circuits. While this technique can be achieved in several manners, examining each shows drawbacks in utility ranging from strong assumptions to exponential loss in security. We specifically examine the construction by Applebaum [1] and the construction by Canetti et al. [11], two very similar constructions, to explain why each is different and if the differences are warranted. We prove that the Applebaum construction is not valid under the indistinguishability obfuscation definition, demonstrating an important difference with the Canetti et al. construction. Additionally, we examine the Garg et al. construction [14] in how it relates to the other constructions.