I'm reading Boneh and Shoup's book "A Graduate Course in Applied Cryptography." Im doing one of the questions at the end of the stream ciphers chapter. I'm not sure how to do this problem:
Let $\mathcal{E} = (E,D)$ be a cipher defined over $\mathcal{K}, \mathcal{M}, \mathcal{C}$. Assume that one can efficiently generate messages from the message space $\mathcal{M}$ at random. We define an attack game between an adversary $\mathcal{A}$ and a challenger as follows. The adversary selects a message $m \in \mathcal{M}$ and sends $m$ to the challenger. The challenger computes $$b \leftarrow \{0,1\}, k \leftarrow \mathcal{K}, m_0 \leftarrow m, m_1 \xleftarrow{\\\$} \mathcal{M}, c \leftarrow E(k,m_b)$$ and sends the cipher text $c$ to $\mathcal{A}$ who then computes and outputs a bit $\hat{b}$. Define $\mathcal{A}$'s advantage to be $|Pr[\hat{b} = b] - 1/2]|$ and we say $\mathcal{E}$ is real/random secure if this advantage is negligible for all efficient adversaries.
My attempt:
For one direction, let $\mathcal{E}$ be semantically secure and let $B$ be a real/random adversary. We construct a semantic security adversary $\mathcal{A}$ with $B$ as a subroutine.
$\mathcal{A}$ selects $m_0, m_1 \in \mathcal{M}$ as per the semantic security game. The challenger responds, sending $\mathcal{A}$ $E(k, m_b)$ with $b$ chosen at random to be $0$ or $1$. Now $\mathcal{A}$ plays the role of challenger to $B$, and sends inputs $m_0$ and $c$ to $B$. (Intuitively $\mathcal{A}$ is asking $B$ if $c$ is an encryption of $m_0$ or some other random message). With these inputs, $B$ outputs a bit $\hat{b}$. $\mathcal{A}$ outputs what $B$ outputs.
I don't know how to relate $\mathcal{A}$'s semantic security advantage to $B$'s real/random semantic security advantage. And I am not sure how to construct a real/random adversary using a semantic security adversary for the other direction.
Thank you for any help!
