Katz/Lindell - 2.10: Is exhaustive search over the key-space allowed in perfect indistinguishability?

Question

I am self studying using "Introduction to Modern Cryptography (2nd edition)"

I am trying to understand how the solution to the following problem is valid:

Prove that a scheme satisfying Definition 2.5 must have $|K| \geq |M|$ without using Lemma 2.4. Specifically, let $\Pi$ be an arbitrary encryption scheme with $|K| < |M|$ Show an $A$ for which $Pr[PrivK^{eav}_{A,\Pi} = 1] > \frac{1}{2}$

Some notation:

Definition 2.5 is:

Encryption scheme $\Pi = (Gen, Enc, Dec)$ with message space $M$ is perfect indistinguishable if for every $A$ it holds that

$$ Pr[Priv^{eav}_{A,\Pi} = 1] = \frac{1}{2} $$

The notation is saying the probability that the adversary guesses the input message correctly must be equal to $\frac{1}{2}$ for perfect-indistinguishability to hold.

However, the solution does not make sense to me.

The solution is:

Considering the following $A$: output uniform $m_0, m_1 \in M$. Upon receiving ciphertext $c$, check by (exhausting search) whether there exists a key $k$ such that $Dec_k(c) = m_0$. If so output 0; else output 1.

This solution seems problematic b/c it says it is valid for the adversary to do exhaustive search over the key space. But if this was the case, for any indistinguishability-experiment, we could have an adversary that just performs exhausting search over the key-space to determine what the cipher text decrypts to.

Does anyone understand what's going on?

Answer 1

This reasoning is tempting, but it is not sound: “we could have an adversary that just performs exhausting search over the key-space to determine what the cipher text decrypts to.”

The problem is that when checking every key, it may not be clear which one is the “correct” one, i.e., what plaintext the ciphertext actually decrypts to.

To see this concretely, consider the one-time pad, which is perfectly indistinguishable. Give a ciphertext, when decrypting it with every key in the key space, we obtain every possible plaintext (of the same length as the ciphertext). This might include many “nonsense” plaintexts, but it also includes all “sensible” plaintexts (of suitable length). The adversary cannot tell which of these candidate plaintexts is the “real” one. In fact, perfect indistinguishability implies that the adversary has no better idea what the correct plaintext is after seeing the ciphertext than it had before seeing it.

So, exhaustive key search is certainly allowed in the context of perfect indistinguishability, but even this does not help the adversary break a perfectly indistinguishable system.