Motivation of Adversarial Indistinguishability Experiment

Question

I had a question about the motivation behind this definition provided in Katz and Lindell's cryptography book. I copied the paragraph in question along with the definition of the experiment.

Perfect (adversarial) indistinguishability. We conclude this section by presenting another equivalent definition of perfect secrecy. This definition is based on an experiment involving an adversary passively observing a ciphertext and then trying to guess which of two possible messages was encrypted.

In the text, this is supposed to be an experiment where the adversary is passively observing a ciphertext and then trying to guess. My question is that in this game, it seems as if the adversary is choosing the two messages. Isn't this not simply an eavesdropping adversary, but rather one that can choose the messages being encrypted? I tried reading more about this, but I couldn't find anything regarding motivation behind this particular definition.

Rather than letting the adversary choose two messages, why not consider for any two arbitrary messages from the message space, sending an encryption of one of them to the adversary along with the two messages? More formally stated:

$$\forall (m_0, m_1) \in M^2,\; [m_0, m_1, E(m_0)] \approx_c [m_0, m_1, E(m_1)]$$

In this way, the adversary does not have a choice in what was encrypted, which seems more in line with the original definition.

Thank you in advance for the help.

Answer 1

My question is that in this game, it seems as if the adversary is choosing the two messages. Isn't this not simply an eavesdropping adversary, but rather one that can choose the messages being encrypted?

Yes, the adversary gets to choose the two plaintexts. There are a few ways to think about why this is appropriate.

It is very realistic to assume that the adversary has a-priori partial information (imagine an encrypted protocol session where we know that all protocols start with a "hello" message, like SMTP) or even partial control (imagine a website where you type a username and the website responds with a message "Hello, <username>") over what plaintext is getting encrypted. In order to cover these realistic cases, it is necessary for the definition to allow the adversary to influence the choice of plaintexts. Once you include that into your definition, you end up converging on the standard chosen-plaintext-attack-style definition, since it is the most pessimistic and conceptually simplest way.

If the security definition didn't allow the adversary to influence the choice of plaintext, then every time you used an encryption scheme, you would have to think to yourself: am I absolutely sure that no external entity had any influence over what I'm encrypting? The standard definition gives you a guarantee that you can more-or-less encrypt whatever you want (there are weird edge cases like encrypting the key itself, etc).

Note that quantifying over all possible $m_0, m_1$ is equivalent to giving the adversary choice of $m_0, m_1$. This is because for every $m_0, m_1$, you can consider the adversary whose only strategy is to choose those $m_0, m_1$.

Having the game itself choose the two message $m_0,m_1$ is not equivalent. Such a definition would not rule out the existence of "bad" plaintexts. Consider a scheme that says: "to encrypt $m$, if $m$ is all zeroes then reveal the secret key, otherwise do a reasonable thing." This scheme would be secure under this weaker definition (since all-zeroes $m$ is rare, assuming the message space is large enough), but not the standard definition.

One reason to favor the "adversary chooses" style of definition is that we are already quantifying over all adversaries. We don't need another quantifier.

Actually in other settings (e.g., public-key encryption, poly-time adversaries), the "forall $m_0, m_1$" style is actually stronger! I think this is contrary to your suggestion. Imagine the public key contains $f(x)$ where $f$ is a one-way function. The encryption scheme says "if $m=x$ then give out the secret key, otherwise behave as normal." Quantifying over all $m_0, m_1$ would include quantifying over $m_0 = x$, and the scheme would be deemed insecure. But no poly-time adversary could actually choose $m_0 = x$ (that implies inverting the one-way function), so the modified scheme is equivalent to the original scheme under the "adversary chooses" style, so it would be considered secure.

Answer 2

I can give many intuitive explanations as to why we define things this way, and the answer by @Mikero is a good one in this line. However, it's important to note that there are many other variants that are also legitimate. For example, the original definition of indistinguishability by Goldwasser-Micali indeed quantified over all pairs of inputs (similar to what you suggested), rather than having the adversary choose them. However, proving security for this then requires assuming hardness for non-uniform adversaries, which we didn't want to get into (not all students even know what this model is). Thus, although we chose this specific formulation for a reason, there are numerous choices that we made that would still result in a legitimate definition. But, be careful! It is easy to slightly modify a security definition and have it become completely useless, so don't take my answer to you mean that details don't matter.

On another note, an important thing to know is that the best justification for this definition is actually its equivalence to semantic security, which formalizes that the adversary can learn nothing about the plaintext from the ciphertext (anything it knows, it knows from a priori information). This holds for different uniform and non-uniform models as well, so this question is a bit orthogonal to the justification of indistinguishability.

Good luck with your studies!