Paper 2013/454

How to Use Indistinguishability Obfuscation: Deniable Encryption, and More

Amit Sahai and Brent Waters

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. STOC 2014
Contact author(s)
bwaters @ cs utexas edu
History
2014-02-17: last of 2 revisions
2013-07-23: received
See all versions
Short URL
https://ia.cr/2013/454
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/454,
      author = {Amit Sahai and Brent Waters},
      title = {How to Use Indistinguishability Obfuscation: Deniable Encryption, and More},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/454},
      year = {2013},
      url = {https://eprint.iacr.org/2013/454}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.