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"

  • $\begingroup$ (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}$. $\endgroup$ – Occams_Trimmer May 30 '20 at 14:58
  • $\begingroup$ 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 $\endgroup$ – PhantomR May 30 '20 at 21:14
  • $\begingroup$ The text says the probability is exactly 1/|M|. How would a formal proof look :( ? $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.