Proof that semantic security implies key-recovery security

Question

I'm trying to prove that semantic security implies key-recovery security. There is already a question that addresses this, but it doesn't explain the setup of the security reduction, which is what I'm interested in.

My idea is as follows:

• Given an efficient key-recovery adversary $A$, I'm constructing an semantic security adversary $B$ that is an elementary wrapper around $A$.
• $B$ computes messages $m_0$ and $m_1$ and sends them to its challenger.
• $B$'s challenger randomly chooses $m \in \{m_0, m_1\}$ and $k$, and sends back $c = E(k, m)$.
• $B$ sends $(m_0, c)$ and $(m_1, c)$ to $A$. $A$ will send back keys $k_0$ and $k_1$, respectively.
• Since $c$ was encrypted from either $m_0$ or $m_1$, either $k_0$ or $k_1$ will be the $k$ that $B$'s challenger used to compute $c$.
• $B$ computes $D(k_0, c)$ and $D(k_1, c)$ and checks which one matches $m_0$ or $m_1$. Then it sends the result to its challenger.

Is this correct? Is it considered cheating that $B$ is sending two queries $(m_0, c)$ and $(m_1, c)$ to $A$? In the question I linked above, $B$ only ever sends $(m_1, c)$ to $A$.

Thanks!

Answer 1

This is not correct, because your premise is not correct.

There exist ciphers that are semantically secure, but insecure against the key recovery attack. The natural example is the one-time pad. If you work through your proof using the one-time pad as an example, you will see that it holds until the final step when one decryption matches $m_0$ and one decryption matches $m_1$ and $B$ cannot make a determination.

The linked question has the additional constraint that the size of the possible keyspace is arbitrarily small proportion of the possible message space.

It is not considered cheating to make use of the same oracle adversary.