4
$\begingroup$

background

In [Shoup2004], Victor Shoup synthesizes the 'sequence of games' technique for proving security properties: Roughly it consists in a sequence from game_0 to game_n, game_0 consisting in the property. You prove that for any two games the two probability of success are negligibly close, then you prove that the probability of success of game_n is negligibly close to the target probability; it follows that the probability of success for game_0 is negligibly close to the target probability, which proves the property.

Shoup identifies 3 types of transitions, namely indistinguishability-based, failure-event based and bridging step (which is a bit apart).

In the failure-event based transition, the two games are equivalent unless a failure event $F$ happens; then Shoup states:

to prove that $Pr[S_i ]$ is negligibly close to $Pr[S_{i+1}]$, it suffices to prove that $Pr[F]$ is negligible.

EDIT writing it as a theorem could make it clearer:

Theorem(Shoup's Framework)
Let $(G_i)_{i=0..n}$ be a sequence of games with their respective "Fault" event $(S_i)_{i=0..n}$
If $\forall i ~ |Pr[S_i]-Pr[S_{i+1}]|$ negl. ("transition lemmas")
and If |Pr[S_n] - Target| negl.
Then |Pr[S_0] - Target| negl.

Lemma(Shoup's Fault-based transition)
If $Pr[S_{i+1}|$ not $F] = Pr[S_i]$
And $Pr[F]$ negl.
Then $|Pr[S_{i+1}]-Pr[S_i]|$ negl.

Question

It is not hard to prove that this is true. However I think that the requirement on $Pr[F]$ is way too strong: one can prove security with much more frequent faults. Namely I think I can prove it holds for non-negligible $Pr[\bar{F}]$ (proba of non-fault) as soon as the success probability $Pr[S_{i+1}]$ is negligibly close to the target probability (which is 1/2 here, didn't look if it works for target 0). The latter ("$Pr[S_{i+1}] - 1/2$ negligible") will prove right later in the proof anyway thanks to the other transitions.

Question: does the following theorem hold, and has it been added to Shoup's framework for crypto proofs ?

Argumentation

Lemma(My Fault-based transition):
(we assume Target = 1/2)
If Pr[$S_1$ | not F ] = Pr[$S_0$]
and If Pr[not F] non-negl.
and If |Pr[$S_1$]-1/2| negl
Then |Pr[$S_1$]-Pr[$S_0$]| negl.

proof

Let "OK" be then event "not F". When a failure event happens, the algorithm can still make a random guess before halting, thus $Pr[S_1 | \bar{OK}] = 1/2$

$Pr[S_1] \geq Pr[S_1 | OK ].Pr[OK] + Pr[S_1 | \bar{OK}].Pr[\bar{OK}]$
$Pr[S_1] \geq Pr[S_0].Pr[OK] + ½ (1 - Pr[OK])$
$Pr[S_1] \geq Pr[OK](Pr[S_0] - ½) + ½$
$(Pr[S_1] - ½)\frac{1}{Pr[OK]} + ½ \geq Pr[S_0]$
$Pr[S_0] - Pr[S_1] \leq (½ - Pr[S_1])(1 + \frac{1}{Pr[OK]})$

Then since $(½ - Pr[S_1])$ is negligible and $(1 + \frac{1}{Pr[OK]})$ is polynomially bounded, $Pr[S_0] - Pr[S_1]$ is negligible which ends the proof.

Recall that the hypothesis "$|Pr[S_{i+1}] - 1/2|$ negligible" will be proven right later in the proof, so it's not a problem having it.

Improve this question
$\endgroup$
1
  • $\begingroup$ Well, the assumption is that as long the fault event does not happen then adversary cannot identify that the simulator cheats by not giving her the true transcripts of the original game. This event F is often of this form: [F: A breaks a problem as DDH, CDH, DL, etc] I cannot get why you want to make an assumption that this even happens not negligibly since if this is the case then everything is broken.... $\endgroup$
    – curious
    Apr 7, 2015 at 13:35

3 Answers 3

Reset to default
3
+50
$\begingroup$

However I think that the requirement on $\Pr[F]$ is way too strong: one can prove security with much more frequent faults.

Maybe this short paper by Alexander W. Dent could be of interest: A Note On Game-Hopping Proofs? In this paper he introduces a fourth kind of game hop, namely transitions based on large failure events, which seems to be exactly what you were looking for?

He gives examples both for computational games (i.e. where the adversary is challenged to compute some value) and for distinguishing games. Note, that to apply this kind of game hop, it is required that the "failure event" be independent of the adversary's probability of winning in the initial game.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, that's the same proof, great. this paper is not that much cited so it's hard to say how many confidence you can put in it, but I'm relieved to see that I'm not the only one using that ! By the way it is weird that so few people cite it, I think this transition is quite useful. $\endgroup$
    – Cédric Van Rompay
    Apr 17, 2015 at 15:30
5
$\begingroup$

My experience of such proofs is that often you're proving a much stronger statement: in any execution of Game i+1, either everything is distributed identically to Game i or else F must have happened. In other words, the conditional distribution of game i+1 conditioned on F not happening is identical to the distribution of Game i.

For example, one of Bellare's applications of this technique is the "poisoned point" principle: you choose the value of a hash function or similar at a particular point. As long as the adversary does not query the function at this particular point, the new game is identically distributed to the old one. If he does query this point, you abort.

Of course what you will argue next is that since you chose your poisoned point at random, the chance of the adversary querying this exact point is negligible. But the actual game-hop doesn't depend on the probability of F happening, it only says either all is well or else F must have happened.

Failure events with non-negligible probabilities happen frequently in hybrid arguments. They tend to make for very lossy reductions of course but the principle stays the same, the hop itself is Pr[S_{i+1} = 1 | not F] = Pr[S_i = 1] and then you compute the probability of F in a separate step to get your "concrete security" constants.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Good answer. Do you have any example for the last paragraph? $\endgroup$
    – cygnusv
    Apr 8, 2015 at 13:27
  • 2
    $\begingroup$ @cygnusv an example is Corons proof for RSA FDH signatures. $\endgroup$
    – DrLecter
    Apr 8, 2015 at 13:44
  • $\begingroup$ @Bristol Even in Bellare's framework and when using the poisoned point technique, the probability of fault (what you call "proba of F happening") has to be bounded to complete the proof, c.f [BR2008 "Code-Based Game-Playing Proofs...", §4.7, Proof of Lemma 9, about the end of the proof] "Finally, we must bound the probability that bad gets set in game G_5". And here again the probability of fault is already low so they express the adversarial advantage with that: [BR2008 Eq. (15)]. My point is that you can still prove "Adv is negl" with a much more frequent F. $\endgroup$
    – Cédric Van Rompay
    Apr 8, 2015 at 16:35
  • 1
    $\begingroup$ Ok, so here's a counter-example (I think) to the original claim. Let $G_0$ be a game that picks a bit $b$ at random and outputs it; you win by guessing $b$ so $Pr[S_0] = 1$. Let $G_1$ be the game that picks $b$ at random but does not output it, so $Pr[S_1] = 1/2$. Now let $F$ be the event that the adversary guesses incorrectly in game 1. We have $Pr[F] = 1/2$ and $Pr[S_1|\neg F] = Pr[S_0] = 1$ yet $Pr[S_0]$ and $Pr[S_1]$ are not close. $\endgroup$
    – user2552
    Apr 14, 2015 at 9:42
  • $\begingroup$ @Bristol Damn, it gave me a cold sweat, but I now think the counter example does not work. My bad, this is because I do not define the problem formally enough (proba space and all..). My event F is defined a priori from the event $S_1$, yours is not. It is required because you catch the fault before you end your game, which I need for the first assumption in my proof : if F happens you can still give an answer to $G_1$. This is not possible with your suggested F, that's why it doesn't work. $\endgroup$
    – Cédric Van Rompay
    Apr 16, 2015 at 17:03
3
$\begingroup$

Ok, here's a version that definitely works. Three points:

  • If we know $S_2$ is close to $1/2$, then the statement that $S_1$ and $S_2$ are close is equivalent to saying that $S_1$ is close to $1/2$. So I'll prove the latter version.

  • The way to deal with the edge cases, I think, is to demand Pr$[S_2|F] = 1/2$. This is the case whenever the game (not the adversary!) can detect the failure event, in which case it can abort with a random guess as you say.

  • I'll give a concrete-security version as that's easier to prove i.m.o.

Theorem. Suppose that $G_1, G_2$ are games and $S_1,S_2$ are the events that the adversary wins games 1,2 respectively. Suppose that $F$ is an event defined in $G_2$ with $Pr[F] < 1$. Suppose that Pr$[S_2] = 1/2 + \delta$ and that $Pr[S_2|F] = 1/2$ and $Pr[S_2|\neg F] = Pr[S_1]$. Then $Pr[S_1] = 1/2 + \frac{\delta}{Pr[\neg F]}$.

Proof. Applying conditional probability,

$Pr[S_2] = 1/2 + \delta = Pr[S_2|F]Pr[F] + Pr[S_2|\neg F]Pr[\neg F]$

Subsitute $Pr[F] = 1 - Pr[\neg F]$, $Pr[S_2|F] = 1/2$ and $Pr[S_2|\neg F] = Pr[S_1]$:

$1/2 + \delta = 1/2 (1 - Pr[\neg F]) + Pr[\neg F]Pr[S_1]$

Reorder to get

$Pr[S_1] = 1/2 + \frac{\delta}{Pr[\neg F]}$

q.e.d.

In particular, we can now compute

$\left|Pr[S_2] - Pr[S_1]\right| \leq \delta\left(1 - \frac{1}{Pr[\neg F]}\right)$

If $\delta$ is negligible and $Pr[\neg F]$ is non-negligible then $\delta/Pr[\neg F]$ should be negligible too.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Are you sure with your conclusion ? $\delta$ negl. means "$\forall p$ polynomial, $\delta \leq 1/p$ beyond some value". Now $Pr[\neg F]$ non-negl means "$\exists p_0$ polynomial, $Pr[\neg F] \geq p_0$ for all input" thus $1/Pr[\neg F] \leq p_0$ ; thus $\delta/Pr[\neg F] \leq p_0/p ~\forall p$". Conclusion should be "negligible". $\endgroup$
    – Cédric Van Rompay
    Apr 17, 2015 at 15:09
  • $\begingroup$ Thanks. Getting a "not" wrong is always the worst kind of mistake ... edited. $\endgroup$
    – user2552
    Apr 17, 2015 at 15:17
  • $\begingroup$ Great, then it seems we agree. Thanks a lot for all the efforts you put in that, sorry that the bounty goes to @hakoja but the kind of reference he gave was exactly what I was looking for. $\endgroup$
    – Cédric Van Rompay
    Apr 17, 2015 at 15:38

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.