Why probabilistic syntax for encryption schemes?

Question

In Foundations of Cryptography II, Goldreich, the basic mechanism of encryption schemes is written as follows:

Definition 5.1.1 (encryption scheme): An encryption scheme is a triple, $(G,E,D)$, of probabilistic polynomial-time algorithms satisfying the following two conditions:

1. On input $1^n$, algorithm $G$ (called the key-generator) outputs a pair of bit strings.

2. For every pair $(e,d)$ in the range of $G(1^n)$, and for every $\alpha\in\{0,1\}^*$, algorithms $E$ (encryption) and $D$ (decryption) satisfy

   Pr$[D(d,E(e,\alpha)) = \alpha] = 1$

where the probability is taken over the internal coin tosses of algorithms $E$ and $D$.

I repeated this definition in my own work without too much thought for why the definition was given in probabilistic terms. It was posed to me that it is unnecessary, as written here, for probability to be included and that one could just as well write the consistency equation as $D(d,E(e,\alpha)) = \alpha$.

I read later in the book that this definition may have the probability bound relaxed to allow for some negligible chance that decryption is not possible, and that this may be necessary for certain public-key encryption schemes.

My question is whether this definition is better, tighter or more complete than one that does not consider the probability of the decryption succeeding? Why is the mechanism of encryption formulated in this way?

Answer 1

Why is the mechanism of encryption formulated in this way?

Writing $D(d,E(e,\alpha)) = \alpha$ would imply that $E(e, \alpha)$ is a unique value, and it generally is not in practice (as most encryption schemes are, in fact, nondeterministic; that is, there are a number of ciphertexts that correspond to any specific plaintext).

The text as written $\text{Pr}[D(d,E(e,\alpha)) = \alpha] = 1$ accounts of the fact that $E(e, \alpha)$ can take on a number of different values (with some probability distribution), and so matches reality (while respecting the formalism).

I read later in the book that this definition may have the probability bound relaxed to allow for some negligible chance that decryption is not possible, and that this may be necessary for certain public-key encryption schemes.

Yes, it comes up in most lattice-based public key encryption schemes and in some code-based public key encryption schemes. I have personally never heard of a symmetric system that had the possibility of a decryption failure; that is, where the decryption of the correctly encrypted (and unmodified) ciphertext would not result in the original plaintext.

Answer 2

The provision for the encryption algorithm $E$ to be probabilistic is, as poncho already notes, necessary to allow for probabilistic encryption. The notation $\mathrm{Pr}[D(d,E(e,\alpha)) = \alpha] = 1$, as poncho adds as well, communicates that $E(e, \alpha)$ does not denote a deterministic value, as your proposed alternative $D(d,E(e,\alpha)) = \alpha$ could be misinterpreted to imply.

So the part of the definition that I think remains slightly confusing is this (my boldface):

where the probability is taken over the internal coin tosses of algorithms $E$ and $D$.

...because it allows for not just $E$ to have randomized outputs, but for $D$ to do so as well. But from the requirement that $\mathrm{Pr}[D(d,E(e,\alpha)) = \alpha] = 1$ it has to follow that $D$ must compute a deterministic function, because that condition would be false if $D$ had even a negligible chance of producing some other output than $\alpha$.

So any for any scheme satisfying this definition, there must exist a deterministic polynomial time algorithm $D'$ such that you could substitute it in for $D$. And indeed that seems to render redundant the definition's allowance for $D$ to be probabilistic. If I had to guess, I'd say that the author really wanted this definition to be as symmetrical as possible with the later one you mention that relaxes the decryption success probability.

Answer 3

One might note that it is indeed possible to state perfect correctness for encryption without using probabilities. Just not quite in the way you did.

Perfect correctness can be defined as:

A public key encryption scheme is perfectly correct, iff for all security parameters $n\in \mathbb{N}$, all key-pairs $(e,d)\gets G(1^n)$, all messages $\alpha\in\{0,1\}^*$, all ciphertexts $c\gets E(e,\alpha)$ and all $\alpha'\gets D(d,c)$ it holds that $\alpha'=\alpha$.

This definition is equivalent to the one stated in the question. The difference is that this definition all quantifies over the internal coin tosses of $D$ and $E$. For perfect correctness, the result is the same because the number of possible coin toss results is necessarily finite for any algorithm running in finite time.

Whether one prefers one definition over the other depends on context. As noted in other answers, the Goldreich definition generalizes nicely for non-perfect correctness whereas this one does not.