Proving semantic security implies security from key-recovery attack

Question

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.

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.