# Proving semantic security implies security from key-recovery attack

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}$$:

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.

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.
• 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? Commented Oct 24, 2022 at 7:34
• 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$. Commented Oct 24, 2022 at 8:06
• 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$. Commented Oct 24, 2022 at 8:17
• 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. Commented Oct 24, 2022 at 8:23
• 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? Commented Oct 24, 2022 at 8:26