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

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?

• Yes, it is valid, even in the case of this, it has perfect secrecy. No matter what power the adversary has, they cannot have an advantage, For an outer observer, their choice will be seen as random even whatever strategy they applied. Jan 3, 2022 at 6:26
• You will see a little later that we need computational indistinguishability where the we talk about polynomial adversaries.. Jan 3, 2022 at 8:32
• Did you see this We stress that no limitations are placed on the computational power of A just under 2.5? Jan 3, 2022 at 8:55

• Got it. So the claim is roughly: If we decrypt the cipher text with every possible key, it will always result in both $m_0$ and $m_1$ where $m_0$ and $m_1$ where the 2 messages that the adversary fed into the perfect indistinguishability experiment Jan 3, 2022 at 21:38