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.
Category / Keywords: public-key cryptography / Deniable encryption, electronic voting, multi-party computation. Publication Info: Eurocrypt 2011 Date: received 4 Feb 2011, last revised 18 May 2011 Contact author: dfreeman at cs stanford edu Available format(s): PDF | BibTeX Citation Note: Version: 20110519:053711 (All versions of this report) Short URL: ia.cr/2011/066