Understanding why Semantic Security implies Message Recovery Security

Question

I am stuck in the proof where it says $$p_0=1/|M|$$ , I just do not understand how we can infer this equality.

Also, am I right in understanding that B is defined as choosing his two messages at random each time (i.e sampled uniformly from $M$)?

This is the link to two pictures: the first one containing the definition of Semantic Security, the second containing the definition of Message Recovery Security and the Proof I cannot follow: https://imgur.com/a/ZP6xtgq

They are from Dan Boneh and Victor Shoup's free e-book 'A Graduate Course in Applied Cryptography'"A Graduate Course in Applied Cryptography"

Answer 1

The definition of semantic security we see in the Shoup book is better explained in his well-known paper Sequences of Games: A Tool for Taming Complexity in Security Proofs.

You must pay the very attention to their words on page 15 of the book:

Actually, our attack game for defining semantic security comprises two alternative "sub-games", or "experiments" --- in both experiments, the adversary follows the same protocol; however, the challenger’s behavior is slightly different in the two experiments.

So, the point here is that we consider two games: this is why sometimes the adversary $\mathcal{B}$ receives from the SSChallenger a c (that I'll call it here) "well formed"; this is the Game 1, or the game of message $m_1$;

Sometimes, c is only "semanticly" equivalent to an encryption of $m_0$ or $m_1$; let me call it "dummy c"; this is the Game 0, or game of message $m_0$.

Furthermore, after receiving a c", the adversary $\mathcal{B}$ passes it on to $\mathcal{A}$, the message recovery adversary. When that c is "well formed", the chance of the adversary $\mathcal{B}$ is equal to the chance of $\mathcal{A}$ guessing.

But when c is dummy, $\mathcal{A}$ cannot help, and $\mathcal{B}$ best chance is $1/|M|$.

Answer 2

I personally feel that the proof is incorrect. What we can show is that $p_0 \leq \frac{1}{|M|}$ instead of equality. But the result is the same: $p-\frac{1}{|M|}\leq p_1-p_0\leq \epsilon$.