# Understanding why Semantic Security implies Message Recovery Security

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"

• (1) It's because the adversary can always guess the message, and this probability (over any distribution over $\mathcal{M}$) is at least $1/|\mathcal{M}$. (2) it seems in this context the sampling is done uniformly at random from the set $\mathcal{M}$. – Occams_Trimmer May 30 '20 at 14:58
• I am very grateful for the answer, but I still do not get it. I understand the adversary's output as being a fixed function f:C->M – PhantomR May 30 '20 at 21:14
• The text says the probability is exactly 1/|M|. How would a formal proof look :( ? – PhantomR May 30 '20 at 21:16

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|$$.

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$$.

• Could you show me a complete, rigorous proof, even of this fact? It would mean a lot. – PhantomR May 8 at 12:04
• You can look at the last sentence of @McFly's answer: "The BEST chance is 1/M." THE BEST means at most. – fatpanda2049 May 8 at 14:11