Consider a situation in which the transmission of encrypted messages is intercepted by an adversary who can later ask the sender to reveal the random choices (and also the shared key, if one exists) used in generating the ciphertext, thereby revealing the cleartext. An encryption scheme is {\sf deniable} if the sender can generate `fake random choices' that will make the ciphertext `look like' an encryption of a different cleartext, thus keeping the real cleartext private. Analogous requirements can be formulated with respect to attacking the receiver and with respect to attacking both parties.
In addition to being interesting by itself, deniable encryption has several applications. It can be incorporated in current protocols for incoercible (``receipt-free'') voting, in a way that eliminates the need for physically secure communication channels. It also underlies recent protocols for general incoercible multiparty computation (with no physical security assumptions). Deniable encryption also provides a simplified and elegant construction of an {\em adaptively secure} multiparty protocol.
In this paper we introduce and define deniable encryption. We also propose constructions of deniable encryption schemes. Our constructions, while demonstrating that deniability is obtainable in principle, achieve only a limited level of deniability. Whether they can be improved is an interesting open problem.
Joint work with Cynthia Dwork, Moni Naor and Rafi Ostrovsky.