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

Question

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?

Answer 1

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 2^nd edition. Their rationale is allowing RSA with a probabilistic prime test. They explicitly choose to ignore the exceptions.

Update: in IMC 3^rd 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.