Difference lemma
Let , , be events in one probability space such that occurs if and only if occurs. Then
— Sho04.
Proof
, so , and both terms lie in — Sho04.
Use in game hops
In a sequence of games, and are the events that two consecutive games output , and is a failure event. The lemma applies once both games are defined on one probability space, the adversary and the challenger using the same coins in both, and the games proceed identically unless occurs — Sho04. Over a sequence of games, the triangle inequality of the hybrid argument sums these bounds — standard.
Variations
Fundamental lemma of game playing
Two code-based games and with a flag , initialized to false and never reset, are identical-until-bad if their code differs only in statements that follow the setting of to true. For identical-until-bad games , and every adversary ,
and and set with the same probability — BR06. Run on the same coins, the two games agree up to the moment is set, which is the difference lemma with the event that is set — standard. The switching lemma has a proof in this framework — BR06.