Deniable Encryption from simple primitives

Question

Is there a deniable encryption scheme $M = E(p_1,k_1,p_2,k_2,...,p_n,k_n), p_j = D(M,k_j)$ of $n$ plaintexts $p_1,p_2,...,p_n$ and $n$ keys $k_1,k_2,...,k_n$, such that we can fix $D$ to be a known algorithm such as AES (without preprossessing $M$) and such that $|M| \ll \sum_{i=1}^n {|p_i|}$ (since this leaks information about how many false plaintexts there are to a party suspicious their adversary may be using deniable encryption)?

Let me expound a little bit on the motivation for these constraints. Let's say that a soldier of country A were captured and country B wanted said soldier to aid them in deciphering the data on his military issued laptop. Country B is not going to allow the soldier to operate the decryption himself. They are going to take an image of his hard drive and ask which algorithm and key he used. The soldier had better reply with a standard algorithm (not known to be deniable). In addition we would expect every bit of the ciphertext is required to decrypt the plaintext, or else country B may begin to suspect deniable encryption.

This last constraint (pertaining to the ciphertext size) seems information theoretically impossible. So let me ask my question in a less rigorous way:
Most deniable encryption systems seem to me to be heuristic engineering solutions. Out of purely academic interest: What scholarly work has been done on deniable encryption that meets the motivation for my formulation?

Answer 1

Deniable encryption is a topic that has been worked on for a while, but recently (in the last year or two), I have seen many more papers.

I haven't kept up with the area but can make a few comments:

• The schemes are typically built with public key primitives instead of symmetric key ones (the distinguishing feature not being the symmetry of the keys, rather the use of a clean mathematical structure instead of non-linear block cipher design)
• Most schemes encrypt the message bit-by-bit. This means you only have to embed two possible plaintexts (0 and 1) and it is easy to open a message to any possible message.

Scheme based on Elgamal

There is only one scheme that I know that comes close to fitting your scenario. It is from this paper (sorry, couldn't find a non-gated version) and is based on Elgamal.

Properties

• The scheme only allows opening to two possible messages however this should be sufficient for your motivating example.
• Instead of recovering the different messages using, simply, different keys, it uses two different decryption algorithms. Using the standard Elgamal decryption will give you one message (the fake one) and using a special decryption algorithm will give you the real message. Schemes like these are sometimes called multi-distributional instead of fully-deniable. (Aside: To me, this is reminiscent of steganography: hiding a secret message in innocuous looking data).
• This is a plan ahead scheme meaning you have to know what fake message you want to open the ciphertext up to ahead of time
• The scheme is receiver-deniable, meaning the receiver of the message (the person performing decrypt) can deny the true plaintext value. For reasons we will see, the sender cannot.
• Despite being based on Elgamal, the scheme is actually symmetric key; the consequences we will see.

Construction

Recall normal Elgamal, where Alice sends a message to Bob. Bob has a secret key $x$ and a public key $y=g^x$ (for some generator $g$). To encrypt message $m$, Alice chooses a random value $r$ and computes $\langle c_1, c_2 \rangle = \langle g^r, my^r \rangle$. To decrypt, Bob uses secret key $x$ to compute $c_{1}^{-x}c_2$.

Let's generalize slightly: replace in the ciphertext $g^r$ with some arbitrary value $a$ and $y^r$ with some value b. Then the ciphertext is $\langle a, mb\rangle$. There are lots of a values of $a$ and $b$ that will decrypt to $m$, not just $g^r$ and $y^r$. In fact, any $a$ and $b$ such that $b=a^x$ will work. In this scheme, Bob gives Alice his secret key $x$ (see fine-print below).

Once Alice has $x$, it is simple. She can, for example (my example, not from the paper), set $a=\mathrm{AES}_k(m)$, using an additional shared secret key $k$ (only used for decrypting the true value), and then compute $b=a^x$. For fake message $\hat{m}$, Alice sends $\langle a, \hat{m}b\rangle$. If Bob wants the real message, he decrypts $c_1$ with AES. If he wants to deny, he claims it is an Elgamal ciphertext and decrypts as normal, with $x$, and gets $\hat{m}$.

In the paper, they set $a=g^km$ and $b=y^km^x$. Here, instead of $k$ being a shared secret, there is a shared secret $s$ and $k=\mathcal{H}(s||\hat{m})$. I don't fully appreciate why the construction needs to be this complicated (comments welcome). To decrypt, Bob, uses $x$ and standard Elgamal decryption to recover $\hat{m}$. With $\hat{m}$ and $s$, he computes $k$ and then computes $g^{-k}c_1$ to recover $m$.

Fine-print

• Because Alice is given Bob's secret key, this means it is no longer a public key encryption scheme. This has consequences: If Charlie also wants to send messages (standard or deniable) to Bob, Bob either has to use a different key pair (which is odd for what is ostensibly a true public key) or Alice can read all the messages.
• If Bob is coerced, he can deny that anything more than standard Elgamal is going on. However, if Alice is coerced, they will ask her what message $m$ and randomness $r$ she used to create the ciphertext. Because she didn't create a standard Elgamal ciphertext, she cannot answer for $r$ or compute a suitable one without solving a discrete log.
• Finally, it may be odd for something like disk encryption or file encryption to use Elgamal on the data itself. Usually you'd use it to encrypt an AES key, and then use AES to encrypt the actual data.

Answer 2

I am assuming that AES decryption with a common chaining mode (e.g. CBC) is used. For an encrypted text (any sequence of bytes of the right length), any key will yield some kind of "decrypted text". For deniable encryption, the following must be met:

• There must be no integrity check, or the alternate keys must match it (so the encryption format should have no MAC and must not be anAuthenticated Encryption scheme; also, padding may act as a crude integrity check).
• The alternate plaintexts must "make sense".

You will not get that with arbitrary plaintexts $p_i$, except in some degenerate cases: for instance, the secret message fits on three bytes (that's enough for a "yes" or a "no") and random padding is specified, in which case you can generate random keys which yield a decryption beginning with either "yes" or "no" (one random key in 16777216 will yield a "yes"). On a general basis (for a long message), this is not workable: for a given plaintext $p$ of length $z$ bits, and a ciphertext $c$ of corresponding length, chances that there exists a 128-bit key such that decryption of $c$ with that key yields $z$ are not higher than $2^{128-z}$. Even if you get so lucky that such a key exists, finding it (or even proving, non-constructively, that it exists) would amount to what is essentially breaking AES, which is supposed to be hard.

If you can alter your plaintexts (all of them, the "right one" and the fakes) then you may have some limited success in some situations. First, define your encryption system to work over a limited alphabet of, say, 64 signs, such that all signs are "valid" (that's enough for letters, digits, space, and one punctuation sign), and specify an encoding of 6 bits per sign (that's relatively unusual, but not weird since it saves space over a more mundane ASCII/UTF-8 encoding of 8 bits or more per character). Use AES in CTR mode. Choose a random IV, and two random keys $k_1$ and $k_2$; the AES in CTR mode then produces two pseudorandom streams $r_1$ and $r_2$. Then, you can try to build a pair of messages $p_1$ and $p_2$ (the right one and the fake) such that decrypting with $k_1$ yields $p_1$, and with $k_2$ you get $p_2$: this is equivalent to having $p_2 = p_1 \oplus (r_1 \oplus r_2)$. In plain words: when you choose a character for $p_1$, this forces the value of the corresponding character in $p_2$. Building $p_1$ and $p_2$ which both "make sense" looks like an interesting crosswords-like puzzle, difficult but not infeasible. You can also choose new keys $k_1$ and $k_2$ if you meet an impossibility. Automating that with a computer would be challenging, though.