Best-Possible Obfuscation, Witness Encryption, and Functional Encryption for Circuits
Amit Sahai
Abstract:
In this talk, we consider 3 long-standing open problems: The first is software obfuscation for general circuits, where the goal is to transform a circuit into another circuit that preserves functionality, but hides as much information about ``how the circuit works'' as possible. While broad impossibility results for strong definitions of obfuscation are known, a notion called (efficient) Indistinguishability Obfuscation, a.k.a. Best-Possible Obfuscation, was not known to be either possible or impossible for general circuits. The second problem is Witness Encryption for NP-complete languages such as Circuit Satisfiability, where a party wishes to encrypt a secret message associated with an arbitrary instance of Circuit Satisfiability. Only a party that knows a witness to the instance should be able to decrypt the secret message. The final problem is Functional Encryption for general circuits, where a user an encrypt a secret input x in a ciphertext c, and a user that has a secret key corresponding to a circuit C can only obtain the value C(x) when it decrypts the ciphertext c. (We consider the standard notion of function encryption, where the adversary can obtain an arbitrary number of secret keys.)
We present constructions for Best-Possible Obfuscation, Witness Encryption, and Functional Encryption for all polynomial-size circuits. At the heart of our technique is a construction of Best-Possible Obfuscation for NC1 using ``algebraic puzzles'' built upon a matrix representation of branching programs. We then show how to use Best-Possible Obfuscation for NC1, along with Fully Homomorphic Encryption and Non-Interactive Zero-Knowledge schemes, to construct Best-Possible Obfuscation for all circuits, Witness Encryption for all NP statements, and Functional Encryption supporting all circuits. (Note that Attribute-Based Encryption for circuits follows as a special case of Functional Encryption.)
This talk is based on joint works with Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, and Brent Waters.