Advantages and possible usages of encryption schemes with probabilistic decryption

Question

We can define deterministic and probabilistic encryption;

• Deterministic $c = E(k,m)$, and
  • Examples are textbook RSA, block ciphers in ECB mode.
  • Deterministic encryption fails to achieve CPA security.
  • Deterministic encryption is insecure and we don't want to use/advise to use ( there are bad exceptions for this like SIV mode doesn't have CPA security if you keep the nonce fixed don't ever do that ((see note 3)), however, AES-GCM-SIV is a non-misuse resistant scheme that prevents the IV-reuse problem of the AES-GCM )
• Probabilistic $c \stackrel{R}{\leftarrow} E(k,m)$
  • Public schemes like Elgamal, RSA-OAEP, Pailler, and private schemes like CBC, CTR, CGM, SIV, etc.

In the case of deterministic, there is one ciphertext that decrypts to the message and in the case of probabilistic, there are many to be expected.

From the correctness requirement, we want

• for deterministic case $m = D(k,E(k,m))$
• for probabilistic case $c \stackrel{R}{\leftarrow} E(k,m)$, $m' = D(k,c)$ with probability 1.

The probabilistic encryption is preferable since it can provide semantic security or its equivalent and easy to use version is the indistinguishability.

Now, what if set the definition for probabilistic decryption to more than :$$\Pr[D(k,E(k,(m))=m] = 1 - negl(k)$$

instead, making it:

$$\Pr[D(k,E(k,(m))=m] = p$$

An example of this is the Rabin cryptosystem (see note 2) where $p = 1/4$ since we end up with four possible $m$. It is suggested to add some auxiliary data to plaintext to resolve. Note that Rabin cryptosystem is not randomized encryption where an IV/nonce is usually needed to achieve that. The decryption still produces randomized decryption.

• Are there any other examples of randomized decryption schemes other than the half randomized Rabin Cryptosystem?

• Is there any advantage or usage of randomized decryption schemes?

---

Notes:

1. This is asked as a fundamental question for clarification of the probabilistic decryption which is simply discarded in the textbooks.

2. Actually, Rabin has not defined an encryption scheme on their seminal paper. They defined the first secure signature scheme and hashing is a part of it. The Wikipedia article is misleading about this.

3. One should never use the AES-GCM-SIV with fixes nonces, one should use unique/random nonces and AES-GCM-SIV and it doesn't fail like AES-GCM if the nonce repeats under the same key.

Answer 1

Since when decrypting we always want to get the correct message back, there's no reason why we would want to make this ambiguous. It would have no security advantage (if the adversary can guess with any non-negligible probability, you have already lost, so ambiguous decryption can't make that harder). Thus, unlike probabilistic encryption, which is needed for security, probabilistic decryption is an undesired property that sometimes arises when trying to construct schemes. For example, with the naive Rabin, it just happens to be a property of the number theory used. The additional work required to make Rabin a trapdoor permutation is necessary to make it useful.

Thus, the only reason why randomized decryption (with a probability of error) exists is when this is what some constructions unfortunately give us. (This can be viewed in some sense as an advantage - if we weren't able to allow decryption errors, we wouldn't be able to build these schemes, some of them having advantages.) There are some examples of this: NTRU and the Ajtai scheme based on lattices. As a result, there has been some theoretical work on removing errors from encryption schemes that have them. Most notably, I recommend reading the paper Immunizing Encryption Schemes from Decryption Errors by Dwork, Naor and Reingold.

Answer 2

Prof. Lindell provides a nice explanation for this fundamental question and gave a nice paper to read about. The paper's conclusion section starts with an indication of probabilistic decryption.

We have shown how to eliminate decryption errors in encryption schemes (and even handle nonnegligible success probability of the adversary). It is interesting to note that sometimes such ambiguity is actually desirable. This is the case with deniable encryption , where the goal is, in order to protect the privacy of the conversation, to allow a sender to claim that the plaintext corresponding to a given ciphertext is different than the one actually sent.

Deniable Encryption

Wikipedia: Deniable encryption allows its users to decrypt the ciphertext to produce a different (innocuous but plausible) plaintext and plausibly claim that it is what they encrypted. The holder of the ciphertext will not be able to differentiate between the true plaintext, and the bogus-claim plaintext.

The article actually base on this xkcd 538;

Canetti et. al looked for the answer of the below question and provide schemes with polynomial deniability.

• If the attacker has the power to approach Alice, can Alice generate fake random choices that will look alike an encryption of different cleartext so that the real cleartext will be safe?

Interestingly One-time-Pad provide deniable encryption. Let $c = m \oplus k$ is the message sent then when asked you can provide a different $k'$ such that another meaningfull message $m$ satisfies $k' = c \oplus m'$. Note that this example is not exactly probabilistic decryption since the key is not changed. The other examples in the article use random value to achive.