How to use indistinguishability obfuscation: deniable encryption, and more

By Amit Sahai, Brent Waters. IACR Cryptology ePrint Archive, 2014

716 citations recorded by the source corpus.

We introduce a new technique, that we call punctured programs, to apply indistinguishability obfuscation towards cryptographic problems. We use this technique to carry out a systematic study of the applicability of indistinguishability obfuscation to a variety of cryptographic goals. Along the way, we resolve the 16-year-old open question of Deniable Encryption, posed by Canetti, Dwork, Naor, and Ostrovsky in 1997: In deniable encryption, a sender who is forced to reveal to an adversary both her message and the randomness she used for encrypting it should be able to convincingly provide "fake" randomness that can explain any alternative message that she would like to pretend that she sent. We resolve this question by giving the first construction of deniable encryption that does not require any pre-planning by the party that must later issue a denial. In addition, we show the generality of our punctured programs technique by also constructing a variety of core cryptographic objects from indistinguishability obfuscation and one-way functions (or close variants). In particular we obtain: public key encryption, short "hash-and-sign" selectively secure signatures, chosen-ciphertext secure public key encryption, non-interactive zero knowledge proofs (NIZKs), injective trapdoor functions, and oblivious transfer. These results suggest the possibility of indistinguishability obfuscation becoming a "central hub" for cryptography.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/78b06e159b0428c9afe0d2e7fd7c3523ba73176a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Dan Boneh
2. Amit Sahai
3. Yuval Ishai
4. Brent Waters
5. Elette Boyle
6. Niv Gilboa
7. Ran Canetti
8. Yehuda Lindell

In Computer Vision and Pattern Recognition

1. Amit Sahai
2. Dan Boneh
3. Brent Waters
4. Mark Zhandry
5. Elette Boyle
6. Ran Canetti
7. Alon Rosen
8. Andrej Bogdanov

Citations in the corpus

• Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation (2014, methodology): “In subsequent work, Sahai and Waters [69] showed that indistinguishability obfuscation is a powerful cryptographic primitive: it can be used to build public-key encryption from pseudorandom functions, selectively-secure short signatures, deniable encryption, and much more.”
• Pseudorandom Functions: Three Decades Later (2017, background): “Sahai and Waters [129] show how to build public-key encryption from any puncturable function family using an indistinguishability obfuscator.”
• Function Secret Sharing (2015, background): “We remark that (sub-exponentially) secure public-key encryption (PKE) is implied by (sub-exponentially) secure indistinguishability obfuscation together with (sub-exponentially) secure one-way functions [43].”
• CrowdBC: A Blockchain-Based Decentralized Framework for Crowdsourcing (2019, neutral): “ability obfuscation [49], homomorphic encryption [50].”
• Can We Access a Database Both Locally and Privately? (2017, neutral): “Unlike the simpler case of encryption [SW14], here we cannot instantiate the construction using indistinguishability obfuscation (iO).”
• Theory of Cryptography (2014, background): “have found uses for many cryptographic applications [15, 18, 17], its hard to quantify what security is obtained by directly obfuscating a function with an IO obfuscator since for most classes of functions we do not know what “as much as possible” is.”
• Multi-Input Functional Encryption (2014, neutral): “Our result is obtained by first achieving selective security, where the adversary must begin by declaring the challenge vectors, using indistinguishability obfuscation and one-way functions (leveraging the results of [20]).”