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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Dec 29, 2020 at 23:40

1 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 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.

  • 3
    $\begingroup$ 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) $\endgroup$
    – poncho
    Dec 30, 2020 at 3:54
  • $\begingroup$ @poncho: thanks for showing me the light! $\endgroup$
    – fgrieu
    Dec 30, 2020 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.