I hope someone can help me with the sequence of games security proof for protocols. Here are my questions:

  1. What is the aim of each individual game? i.e. why can't we do this in one indistinguishable game ?

  2. How can we link each game with the previous one? i.e. I am not understanding the difference lemma which states:

Lemma 1 (Difference Lemma). Let A, B, F be events defined in some probability distribution, and suppose that A ∧ ¬F ⇐⇒ B ∧ ¬F. Then |Pr[A] − Pr[B]| ≤ Pr[F].


The general strategy in sequence of games or game-hopping proofs is the following:

Starting with the original security game, change small details in the game in every hop until you get to a game where it is easy to prove security.
You do want small changes in the game hops such that you can prove indistinguishably between the games by security assumptions.

To answer your questions concretely:

  1. The aim of each individual game is a small change from the previous game that can be proven indistinguishable from it.
  2. We link these games by bounding the advantage of an adversary noticing the difference. If no P.P.T. distinguisher is able to decide whether it plays the first or the second game, we can include this bound in the overall security bound and consider the second game instead.

The lemma you stated is a formalization of this idea.

  • $\begingroup$ That's very clear. Thank you so much for your answer $\endgroup$ – Mona Dec 3 '20 at 18:49

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.