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.
