How to Use Indistinguishability Obfuscation: Deniable Encryption, and More
Amit Sahai, Brent R. Waters · SIAM Journal on Computing · 2021
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 et al. 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 preplanning 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, noninteractive zero knowledge arguments and injective trapdoor functions. These results suggest the possibility of indistinguishability obfuscation becoming a “central hub” for cryptography.