Candidate Inditinguishability Obfuscation and Functional Encryption for All Circuits
joint work with Sanjam Garg, Craig Gentry, Shai Halevi, Amit Sahai, Brent Waters

Motivation: Program obfuscation aims to make a computer program unintelligible while preserving its functionality. This allows hiding secret in software, which can be very useful in many settings. For example, a company that has developed a proprietary algorithm can include in its product an obfuscation of the algorithm, which will both allow executing the computation of the algorithm and obtaining the result, but at the same time will hide the mechanics of the algorithm. Obfuscation can also be used for secure distribution of software patches in way where the code of the patch is obfuscated and does not directly point to the vulnerabilities that are being fixed. Using obfuscation we can convert a symmetric key encryption scheme such as AES into a public key encryption by obfuscating the encryption algorithm of the symmetric key primitive with hardcodes secret key in it.

Obfuscation is also very useful tool for the contruction of many new cryptographic primitives. A prominent example is functional encryption for all circuits. Functional encryption allows to generate decryption keys associated with particular functions, which instead of decrypting a ciphertext output only the evaluation of their functions on the encrypted message. Such functionality has very strong access control properties, which can be very useful in numerous scenarios. For example, we can encrypt the information of a driving license and then generate keys that output just a check whether the age of over twenty-one, or output the category of the driving licence, or its expiration date.

Results: Our first result is a candidate construction of an indistinguishability obfuscator iO for all polynomial-size, log-depth circuits (i.e. NC1). The security of our construction relies on a new algebraic hardness assumption. We provide evidence for the plausibility of our assumption by proving it to be true in a specific generic model that seems to capture most natural attacks on this type of construction. Using indistinguishability obfuscator for NC1 together with any (leveled) fully homomorphic encryption (FHE) scheme with decryption in NC1 , we show how to obtain an indistinguishability obfuscator for all polynomial-size circuits.

Using indistinguishability obfuscator for polynomial-size circuits, together with injective one-way functions, public-key encryption, and a novel variant of simulation-sound non-interactive zero knowledge proofs, we show how to obtain functional encryption schemes supporting all polynomial-size circuits. Our construction achieves selective indistinguishability security, which can be amplified to full indistinguishability security using complexity leveraging. Finally, we also obtain meaningful simulation-based security for functional encryption for all circuits. Our construction furthermore achieves succinct ciphertexts: The size of the ciphertexts in our scheme does not depend on potential secret key circuit sizes or even depth.

Indistinguishability Obfuscation has already numerous applications :

  • Functional Encryption for All Circuits [GGHRSW13]
  • Secure Multiparty Computation with Minimal Communication [GGHR14]
  • Extensions to Turing Machines: FE, Obfuscation for Turing Machines [BCP13, ABGSZ13]
  • Outsourced computation: (Compact) Reusable Garbled RAM [GHRW14]
  • Extensions to RAMs: FE and Obfuscation [GHRW14]
  • Broadcast Encryption and Traitor Tracing [BZ13,ABGSZ13]
  • Deniable Encryption [SW13]
  • Multi-input Functional Encryption [GGGJKLSSZ14]
  • Functional Encryption for Randomized Functions [GJKS13]
  • Non-Interactive Multiparty Key Exchange [BZ13, ABGSZ13]
  • Removing random oracles: Full-Domain Hash [HSW13]
  • Separation results for circular security [KRW13,MO13]
  • Functional Witness Encryption [BCP13]
  • Secret Sharing for NP (any monotone function) [KNY14]
  •   Resources:
  • Paper FOCS 2013