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 '20 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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