# What is the more accurate way of stating the correctness of a PK encryption scheme?

Is it more accurate to state that a public key encryption scheme is correct if for all $$m \in M$$ and $$(pk, sk) \in \operatorname{Gen}(1^k)$$

a. $$\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m))=m\;$$ or,

b. $$\Pr[\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m))=m] = 1 - \operatorname{negl}(k)\;$$ or,

c. does it depend on the scheme or some other factor?

• I'd say that (1) shows correctness. But that's more about programmatic correctness than anything else. It doesn't show necessarily that the scheme is secure - particularly it doesn't show that you cannot decrypt in any other way. Dec 29, 2020 at 23:40

Deciding among a or b is a matter of choice of definition of public-key encryption. Clearly a is desirable, and b is a fallback in order to allow some interesting cryptosystems. The definition is chosen according to the cryptosystem studied, as in c.

As pointed by poncho in comment, in b as it stands, the meaning is that for all keys and messages, there's negligible probability that decryption does not yield the original message. The encryption algorithm is re-expressed as a deterministic algorithm with an extra input $$r$$ for the random allowing to achieve CPA security, and it's really meant that $$\Pr[\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m, r))=m]\quad=\quad1 - \operatorname{negl}(k)$$ where the probability is computed over all inputs $$r$$ randomizing the encryption. Such tolerance for rare failures is necessary for some cryptosystems, e.g. those based on Hidden Field Equations.

There is at least one other popular alternative to b: we can require that all except vanishingly few keys allow certain encryption and decryption of all messages $$m\in M$$. We thus compute the probability that there exists a message $$m$$ and random input $$r$$ making encryption/decryption fail over the set of keys produced by $$\operatorname{Gen}(1^k)$$ (or even more precisely, over the set of random inputs to that algorithm re-expressed as a deterministic one with random input $$r$$). That's the definition of public-key encryption given by Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography 2nd edition. Their rationale is allowing RSA with a probabilistic prime test. They explicitly choose to ignore the exceptions.

Update: in IMC 3rd edition, that changed slightly. The probability is computed over the randomness of $$\operatorname{Gen}$$ and $$\operatorname{Enc}$$. I think it will stick as the standard definition of public-key encryption.

Yet other cryptosystems are correct with a only, e.g. RSA with proven primes, or ECIES when working with families of curves and generators of proven order.

• Actually, for $b$, what is generally meant is that the encryption is randomized; hence, it really is $\Pr[\operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m, r))=m] = 1 - \operatorname{negl}(k)\;$ which we insist holds for any valid $sk, pk$ pair, and any message $m$ (and which $r$ is the only random variable) Dec 30, 2020 at 3:54
• @poncho: thanks for showing me the light!
– fgrieu
Dec 30, 2020 at 8:13