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

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.

Asked by user18298 (43,073 )
Dec 30, 2020 at 13:16