# Advantages and possible usages of encryption schemes with probabilistic decryption

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)$$

$$\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.

• Is Rabin really an example of 'randomized decryption'? In randomized encryption, there is a random input that affects which ciphertext is generated; I would naively expect that, in a randomized decryption process, the decryption process also takes a random input (and which you'd get the correct plaintext with high probability). Rabin doesn't follow that paradigm. – poncho Dec 30 '20 at 15:27
• "Deterministic encryption is insecure and we don't want to use/advice to use." No, that's not always true. Deterministic AEADs can be secure, with the caveat that identical messages yield identical ciphertexts. EG repeated nonces in AES-GCM-SIV or fully deterministic stuff like DAENCE. You still get NM-CCA2 security, and the only "break" of IND-CPA/CCA/CCA2 is in the case of identical whole messages (not blocks like with ECB). – SAI Peregrinus Dec 30 '20 at 15:29
• @poncho that is the closest that I know. It still has a probabilistic result need to be resolved. An actual scheme needs a random for encryption as you noted. – kelalaka Dec 30 '20 at 15:35
• SIV with constant nonce is deterministic. It's unique per message, but still deterministic. It violates IND-CPA security, since the attacker can distinguish when a message has been repeated. – SAI Peregrinus Dec 30 '20 at 15:41
• @kelalaka AES-GCM-SIV (or SIV in general) should not be presented as deterministic. It should be used with unique/random nonces. The point is that it doesn't fail if the nonce repeats. This shouldn't be confused with "go ahead and use it deterministically". I don't agree with that approach. – Yehuda Lindell Dec 31 '20 at 11:13

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.

• Are there any protocols that need the advantage of randomized decryption? – kelalaka Dec 30 '20 at 15:52
• @kelalaka What do you mean by protocols? – Yehuda Lindell Dec 30 '20 at 15:54
• In the general sense of the Cryptographic protocols. I think the article you linked gave one example as deniable encryption that I've seen after a quick simminning. – kelalaka Dec 30 '20 at 15:56
• I thought those algorithms were simply randomized by default, so it's permissible to have a probabilistic decryption algorithm. For perfect correctness, decryption randomness doesn't matter. For overwhelming correctness, decryption randomness can be removed using a PRF. Another example of probabilistic decryption in the literature is IBE => CCA PKE, in which IBE KeyGen (possibly probabilistic) is invoked during PKE Dec. – Gee Law Dec 31 '20 at 7:32
• @GeeLaw add another anwer? – kelalaka Dec 31 '20 at 14:11

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.

• The imperfect correctness of deniable encryption is inherent and usually does not originate from a probabilistic decryption algorithm. For example, the source of incorrectness is (randomness of) encryption algorithm in [Sahai-Waters 13]. – Gee Law Dec 31 '20 at 7:41
• @GeeLaw should we say something like controlled randomness. Since we can have a limited meaningful message set that we can give one of the random values to achieve deniability. – kelalaka Dec 31 '20 at 14:09