I am working on problem 2.11 from the book: A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. The problem reads as follows:

Problem 2.11: Let $\mathcal{E} = (E, D)$ be a cipher defined over $(\mathcal{K}, \mathcal{M}, \mathcal{C})$. A key recovery attack is modeled by the following game between a challenger and an adversary $\mathcal{A}$: the challenger chooses a random key $k$ in $\mathcal{K}$, a random message $m$ in $\mathcal{M}$, computes $c \leftarrow E(k, m)$, and sends $(m, c)$ to $\mathcal{A}$. In response $\mathcal{A}$ outputs a guess $\hat{k}$ in $\mathcal{K}$.

We say that $\mathcal{A}$ wins the game if $D(\hat{k}, c) = m$ and define $\text{KRadv}[\mathcal{A}, \mathcal{E}]$ to be the probability that $\mathcal{A}$ wins the game. As usual, we say that $\mathcal{E}$ is secure against key recovery attacks if for all efficient adversaries $\mathcal{A}$ the advantage $\text{KRadv}[\mathcal{A}, \mathcal{E}]$ is negligible.

Show that if $\mathcal{E}$ is semantically secure and $\epsilon = \frac{|K|}{|M|}$ is negligible, then $\mathcal{E}$ is secure against key recovery attacks. In particular, show that for every efficient key-recovery adversary $\mathcal{A}$ there is an efficient semantic security adversary $\mathcal{B}$, where $\mathcal{B}$ is an elementary wrapper around $\mathcal{A}$, such that $$\text{KRadv}[\mathcal{A}, \mathcal{E}] ≤ \text{SSadv}[\mathcal{B}, \mathcal{E}] + \epsilon$$

My attempt:

I use the following construction of $\mathcal{B}$:

enter image description here

Here we set $\hat{b}=1$ if and only if $D(\hat{k}, c)=m_1$.

Experiment $b=1$: the ciphertext $c=E(k,m_1)$, and so $(m_1, c)$ is a valid pair in the key recovery game described above. Therefore $Pr[\hat{b}=1\ |\ b=1]=\text{KRadv}[\mathcal{A}, \mathcal{E}]$.

Experiment $b=0$: the pair $(m_1, c)$ is no longer a valid pair according to the key recovery game since $c=E(k, m_0)$. For $\hat{b}=1$, we would need attacker $\mathcal{A}$ to output $\hat{k}$ such that $D(\hat{k},c)=D(\hat{k}, E(k, m_0))=m_1$.

Question: But how many such $\hat{k}$ are there? Suppose there are $x$ such keys, then would $Pr[\hat{b}=1\ |\ b=0]=\frac{x}{|\mathcal{K}|}$ ? A clear explanation of why this is true or false would help me greatly?

Recalling that $$\text{SSadv}[\mathcal{B}, \mathcal{E}]=|Pr[\hat{b}=1\ |\ b=0]-Pr[\hat{b}=1\ |\ b=1]|$$ we would have $$\text{SSadv}[\mathcal{B}, \mathcal{E}]=|\text{KRadv}[\mathcal{A}, \mathcal{E}]-\frac{x}{|\mathcal{K}|}|\geq \text{KRadv}[\mathcal{A}, \mathcal{E}]-\frac{x}{|\mathcal{K}|}$$

Hence $\text{KRadv}[\mathcal{A}, \mathcal{E}] ≤ \text{SSadv}[\mathcal{B}, \mathcal{E}] + \frac{x}{|\mathcal{K}|}$.

Is my approach correct in general? It seems wrong, in particular the case when $b=0$ (I don't understand where $\frac{|K|}{|M|}$ fits in).

Updated attempt of the case $b=0$:

Let $m_1$ be sampled uniformly at random from $\mathcal{M}$. In this case $c=E(k,m_0)$. From any ciphertext, we have at most $|\mathcal{K}|$ possible messages that we can decrypt to. Let $$S=\{D(k', c)\ |\ k'\in \mathcal{K}\}$$ then $$Pr[m_1\in S]\leq\frac{|\mathcal{K}|}{|\mathcal{M}|}$$

If the event $m_1\in S$ occurs, then attacker $\mathcal{A}$ has probability $\text{KRadv}[\mathcal{A}, \mathcal{E}]$ of finding a key $\hat{k}$ such that $D(\hat{k}, c)=m_1$. Otherwise, when $m_1\not \in S$, we have probability $0$ of finding such a key because none exists. Hence

$$\text{SSadv}[\mathcal{B}, \mathcal{E}]=|\text{KRadv}[\mathcal{A}, \mathcal{E}]-Pr[m_1\in S]\cdot\text{KRadv}[\mathcal{A}, \mathcal{E}] |\geq\text{KRadv}[\mathcal{A}, \mathcal{E}](1-\frac{|\mathcal{K}|}{|\mathcal{M}|})$$

And so we are done.


1 Answer 1


I belive that there isn't a way to know how much $\hat{k}$. And even if we did it isn't correct to assume that $Pr[\hat{b}=1|b=0]=\frac{x}{|K|}$.

To handle the analysis when $b=0$ try fixing $c$ and looking at what is the maximum number of messages such that there exits a key $k$ such that $E(k,m) = c$. Also look at the probability of a message being in this specific set.

  • $\begingroup$ I think what you are saying is that even though $c=E(m_0, k)$ we can still have some keys $k'$ such that $E(m_1, k')=c$, and so attacker $\mathcal{A}$ can still play the key recovery game. Am I correct? $\endgroup$
    – Tom Finet
    Commented Oct 24, 2022 at 7:34
  • $\begingroup$ Fix $c$ as $c=E(k,m_0)$. If we had perfect security, then we would have a key for all $|\mathcal{M}|$ messages since we have a key for message $m_0$. But here we have $|\mathcal{K}|/|\mathcal{M}|<1$ keys per message, i.e. so some messages will not have a key taking it to $c$. $\endgroup$
    – Tom Finet
    Commented Oct 24, 2022 at 8:06
  • $\begingroup$ For $c=E(k, m_0)$, we have $|\mathcal{M}|-|\mathcal{K}|$ messages that cannot be decrypted from $c$, and thus cannot be encrypted to $c$. Picking $m_1$ uniformly at random, we have a $1-|\mathcal{K}|/|\mathcal{M}|$ probability that $m_1$ cannot be encryped to $c$, and hence a $|\mathcal{K}|/|\mathcal{M}|$ probability that it can be encrypted to $c$. $\endgroup$
    – Tom Finet
    Commented Oct 24, 2022 at 8:17
  • $\begingroup$ So with probability $|\mathcal{K}|/|\mathcal{M}|$ attacker $\mathcal{A}$ can play the game on $(m_1, c)$, and return the correct key with probability $\text{KRadv}[\mathcal{A}, \mathcal{E}]$, but with probability $1-|\mathcal{K}|/|\mathcal{M}|$ attacker $\mathcal{A}$ cannot play the game because no key exists which takes $c$ to $m_1$, so we have probability $0$ of finding a key in this case. $\endgroup$
    – Tom Finet
    Commented Oct 24, 2022 at 8:23
  • $\begingroup$ Hence $\text{SSadv}[\mathcal{B}, \mathcal{E}]=|\text{KRadv}[\mathcal{B}, \mathcal{E}]-\frac{|\mathcal{K}|}{|\mathcal{M}|}\text{KRadv}[\mathcal{B}, \mathcal{E}]|=\text{KRadv}[\mathcal{B}, \mathcal{E}]\cdot(1-\frac{|\mathcal{K}|}{|\mathcal{M}|})$, since $\mathcal{E}$ is semantically secure, we have a negligible $\text{SSadv}$ and so a negligible $\text{KRadv}$. I know my reasoning is a bit all over the place, but is this correct? $\endgroup$
    – Tom Finet
    Commented Oct 24, 2022 at 8:26

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.