Paper 2011/066

Deniable Encryption with Negligible Detection Probability: An Interactive Construction

Markus Duermuth and David Mandell Freeman


Deniable encryption, introduced in 1997 by Canetti, Dwork, Naor, and Ostrovsky, guarantees that the sender or the receiver of a secret message is able to "fake" the message encrypted in a specific ciphertext in the presence of a coercing adversary, without the adversary detecting that he was not given the real message. To date, constructions are only known either for weakened variants with separate "honest" and "dishonest" encryption algorithms, or for single-algorithm schemes with non-negligible detection probability. We propose a sender-deniable public key encryption system with a single encryption algorithm. We describe a generic interactive construction based on a public key bit encryption scheme that has certain properties, and we give two examples of encryption schemes with these properties, one based on the quadratic residuosity assumption and the other on trapdoor permutations. Subsequent to the publication of this work in EUROCRYPT 2011, it was shown by Peikert and Waters that, contrary to our initial claim, the proposed scheme does not have negligible detection probability. In this updated version we describe the attack of Peikert and Waters and the error in our original proof. We include the previous version of the paper with the construction and the (incorrect) security theorem.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Eurocrypt 2011
Deniable encryptionelectronic votingmulti-party computation.
Contact author(s)
dfreeman @ cs stanford edu
2011-05-19: last of 7 revisions
2011-02-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Markus Duermuth and David Mandell Freeman},
      title = {Deniable Encryption with Negligible Detection Probability: An Interactive Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2011/066},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.