Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits

Oded's comments

I must admit that I was very skeptic of the possible applicability of the notion of indistinguishable obfuscation, and viewed it more as an obfuscation-related thing that is not ruled out by the paper On the (Im)possibility of Obfuscating Programs. Thus, I find the result that appears as the third step in the abstract very interesting.

I am also wish to highlight the fact that the second step uses leveled FHE (rather than pure ones), which means avoiding circular-security assumptions. Lastly, it is nice to see (yet again) results (i.e., Steps 2 and 3) that capitalized on cryptographic techniques (i.e., "two-key encryption" and simulation-sound NIZK) that were developed for very different purposes.

Regarding the applicability of indistinguishable obfuscation, see also the follow-up works How to Use Indistinguishability Obfuscation: Deniable Encryption, and More (by Sahai and Waters) and Replacing a Random Oracle: Full Domain Hash From Indistinguishability Obfuscation (by Hohenberger, Sahai, and Waters).

The original abstract

In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits C_0 and C_1 of similar size, the obfuscations of C_0 and C_1 should be computationally indistinguishable. In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.

We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps:

1. We describe a candidate construction for indistinguishability obfuscation for NC1 circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles.
2. We show how to use indistinguishability obfuscation for NC1 together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits.
3. Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

See Report 2013/451 of the Cryptology ePrint Archive.