If a probabilistic encryption algorithm is used, how does decryption return the correct message?

Question

Given a key $k$ and a plaintext $p$, a deterministic encryption algorithm will return a ciphertext $c_1$. In a second trial, I run the same key and plaintext $p$ through the encryption algorithm and get ciphertext $c_2$ from the first trial. $c_1$ and $c_2$ are equivalent, so running the decryption algorithm on $c_1$ and $c_2$ both return $p$.

However, if a probabilistic encryption is used instead to encrypt $p$, the algorithm will run twice and return two different ciphertexts $c_1$ and $c_2$.

How does $Dec(c_1) = p$ and $Dec(c_2) = p$?? If $c_1$ and $c_2$ are different, should decryption return different results?

Answer 1

In a probabilistic encryption scheme, for every plaintext there is more than one possible ciphertext.

Here's an example—with lots of details not related to your question omitted, so don't take these scissors and try running with this at home!

The recipient knows the secret ~256-bit number $r$ of times that a base point $B$ must be added to itself to yield a public point $R = B + B + \cdots + B = [r]B$ on some standard elliptic curve, say Curve25519. (There's a shortcut to computing $[r]B$ so you only have to do a few thousand arithmetic operations and not a mindbogglingly unimaginable number.)

To conceal a message $m$ using the public point $R$, the sender:

1. picks a secret ~256-bit number $s$ uniformly at random;
2. adds $B$ to itself $s$ times to obtain $S = [s]B$;
3. adds $R$ to itself $s$ times to obtain $[s]R$;
4. computes $k = H([s]R)$, a secret key;
5. computes $c = \operatorname{crypto\_secretbox\_xsalsa20poly1305}(k, 0, m)$, the authenticated ciphertext under the symmetric key $k$ and nonce 0; and
6. transmits $(S, c)$ to the recipient.

The recipient, on receipt of $(S, c)$, then:

1. computes $[r]S = [r\cdot s]B = [s\cdot r]B = [s]R$;
2. computes $k = H([r]S) = H([s]R)$, the same secret key as the sender derived;
3. computes $m = \operatorname{crypto\_secretbox\_xsalsa20poly1305\_open}(k, 0, c)$, or rejects if forged.

There are roughly $2^{256}$ possible sender secrets $s$ that could be used to encrypt the message, and they all work for any message $m$, so in this cryptosystem, for any message $m$ there are about $2^{256}$ distinct ciphertexts that have $m$ as the corresponding plaintext.

This is not simply an artificial example. To meet the standard notion of security for public-key encryption, indistinguishability under adaptive chosen-ciphertext attack, there must be many ciphertexts for any given plaintext, randomly chosen by the sender. Otherwise, an adversary without knowledge of the private decryption key can easily tell whether a challenge ciphertext conceals one of two (or three, or $n$) possible plaintexts by encrypting the candidate plaintexts and comparing the resulting ciphertexts to the challenge. This implies that the minimum number of distinct ciphertexts for each plaintext must be around $2^{192}$ to give confidence in security against multi-target attacks.

There are also probabilistic symmetric ciphers, like AES-CBC with randomly chosen IVs affixed to the ciphertext, or crypto_secretbox_xsalsa20poly1305 with randomly chosen nonces affixed to the ciphertext. In this case, the randomization serves to prevent the same message content at different times from leading to the same ciphertext and enabling an adversary to recognize repeated messages.

Randomization per se is not always necessary in the symmetric setting: it is sufficient to deterministically keep state for crypto_secretbox_xsalsa20poly1305 and transmit each successive message with a count of the number of messages sent so far, for instance. But in some cases like AES-CBC it is obligatory—though of course you could use a secret pseudorandom function of the message sequence number, such as $\operatorname{AES}_k(\mathit{seqno})$, to choose the AES-CBC IV.

Answer 2

Because probabilistic encryption produces ciphertexts that are longer than the plaintext, and this additional length contains information that allows for deterministic recovery of the plaintext. Your argument has the form of a reductio, but you haven't spotted that the assumption you're actually refuting is that the ciphertext is the same length as the plaintext.

Note that one detail here that's easy to get confused over is the precise scope of the terms ciphertext and initial value ("IV"). Often these are treated as separate strings, but definitions of probabilistic encryption "hide" the IV generation and transmission as an internal detail of the encryption algorithm and ciphertexts. For example, when you formulate it as probabilistic encryption terms, CBC mode:

1. Doesn't take an IV as an argument, rather it internally generates an random IV;
2. Doesn't return a ciphertext equal in length to the padded plaintext, but one additional block longer, such that the first block is the IV.

So under these definitions, CBC can be modeled as probabilistic encryption because:

1. The encryption operation chooses a random IV that gets incorporated as a prefix into the ciphertext and on which the rest of the ciphertext depends;
2. Decryption can recover the original plaintext because the ciphertext encompasses the random IV that's required to reconstruct the random choices made in the invocation of the encryption operation.