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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – kelalaka
    Jan 3, 2022 at 6:26
  • $\begingroup$ You will see a little later that we need computational indistinguishability where the we talk about polynomial adversaries.. $\endgroup$
    – kelalaka
    Jan 3, 2022 at 8:32
  • $\begingroup$ Did you see this We stress that no limitations are placed on the computational power of A just under 2.5? $\endgroup$
    – kelalaka
    Jan 3, 2022 at 8:55

1 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.

  • $\begingroup$ 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 $\endgroup$
    – Foobar
    Jan 3, 2022 at 21:38
  • $\begingroup$ That’s correct (if the system is perfectly indisinguishable). $\endgroup$ Jan 3, 2022 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.