Ciphers providing Deniable encryption?

Question

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.

Answer 1

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]

Answer 2

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.