|
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]
|