# Ciphers providing Deniable encryption?

I stumbled on the concept of Deniable encryption on Wikipedia, with the following scenario:

Deniable encryption allows the sender of an encrypted message to deny sending that message. This requires a trusted third party. A possible scenario works like this:

1. Bob suspects his wife Alice is engaged in adultery. That being the case, Alice wants to communicate with her secret lover Carl. She creates two keys, one intended to be kept secret, the other intended to be sacrificed. She passes the secret key (or both) to Carl.
2. Alice constructs an innocuous message M1 for Carl (intended to be revealed to Bob in case of discovery) and an incriminating love letter M2 to Carl. She constructs a cipher-text C out of both messages M1, M2 and emails it to Carl.
3. Carl uses his key to decrypt M2 (and possibly M1, in order to read the fake message, too).
4. Bob finds out about the email to Carl, becomes suspicious and forces Alice to decrypt the message.
5. Alice uses the sacrificial key and reveals the innocuous message M1 to Bob. Since Bob does not know about the other key, he might assume there is no message M2.

I would like to have examples of ciphers providing this property. The Wikipedia page only gives softwares like filesystems.

• One method that is well known is: Take an OTP1 and obtain the cipertext C = M1 xor OTP1. Compute OPT2 = C xor M2. Now one has M1 = C xor OPT1 and M2 = C xor OTP2. OTP1 and OTP2 are the keys required. – Mok-Kong Shen Mar 2 '16 at 17:54
• For the case of public key cryptography, the only construction I know is only of theoretical interest (absolutely not implementable, whatever the computer you have), but is theoretically a valid solution. It uses a very advanced concept from asymmetric crypto, which is called indistinguishability obfuscation. Roughly, this is a tool that allows you to convert a program into a functionally equivalent program, but for which looking at the source code provide (mathematically) no more information than just sending it inputs and looking at the ouptuts. If you want more details, just ask. – Geoffroy Couteau Apr 1 '16 at 12:40

Here's a relatively complete list of the papers on deniable encryption (plus papers containing a lower bound against some type of deniable encryption):

1. Deniable Encryption by Canetti/Dwork/Naor/Ostrovsky [CRYPTO 1997]
2. Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case by Nielsen [CRYPTO 2002]
3. Lower and Upper Bounds for Deniable Public-Key Encryption by Bendlin/Nielsen/Nordholt/Orlandi [ASIACRYPT 2011]
4. Bi-Deniable Public-Key Encryption by O'Neill/Peikert/Waters [CRYPTO 2011]
5. On the (Black-Box) Impossibility of Sender-Deniable Public Key Encryption by Dachman-Soled [PKC 2014]
6. How to Use Indistinguishability Obfuscation: Deniable Encryption, and More by Sahai/Waters [STOC 2014]
7. Deniable Functional Encryption by De Caro/Iovino/O'Neill [PKC 2016]
8. Deniable Attribute Based Encryption for Branching Programs from LWE by Apon/Fan/Liu [TCC 2016-B]
• In terms of which construction of deniable encryption are potentially implementable... It's possible that CDNO97 and OPW11 are /relatively/ practical.. SW14, AFL16 are certainly 'for theory only.' DeCIO16 has schemes that are 'for theory only;' however, their bilinear map based construction is probably right on the border in between implementable and not implementable, were I to guess.. – Daniel Apon Aug 30 '16 at 23:40

There are good reasons why this is hard to do by cryptography alone. Note that I am not saying the file-based systems are good solutions, I don't know enough about them.

Symmetric Cryptography:

Pairs of messages required to decrypt to different plaintexts under different key pairs introduce an equivalence relation on keys and weaken the cipher. Even assuming your "message pairs" were short enough to fit in a single block, finding two chosen blocks which encrypt to the same ciphertext under some pair of distinct keys is in some sense equivalent to the birthday problem, requiring on average something like $2^{k/2}$ encryptions, thus prohibitive for $k=128.$

This analysis completely ignores the issue of key generation/storage/destruction, as part of a real communications session, as well as modes of operations, with regard to messages longer than a blocklength.

Asymmetric Cryptography:

There is some literature on deniable signatures. Homomorphic properties of some cryptosystems can help, but again there are real issues with deploying such systems.