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?
