Hybrid argument (Cryptography)

In cryptography, the hybrid argument is a proof technique used to show that two distributions are computationally indistinguishable.
Formal description.
Formally, to show two distributions "D"1 and "D"2 are computationally indistinguishable, we can define a sequence of "hybrid distributions" "D"1 := "H"0, "H"1, ..., "H""t" =: "D"2 where "t" is polynomial in the security parameter. Define the advantage of any probabilistic efficient (polynomial-bounded time) algorithm A as
where the dollar symbol ($) denotes that we sample an element from the distribution at random.
By triangle inequality, it is clear that for any probabilistic polynomial time algorithm A,
Thus there must exist some "k" s.t. 0 ≤ "k" < "t" and
Since "t" is polynomial-bounded, for any such algorithm A, if we can show that its advantage to distinguish the distributions "H""i" and "H""i"+1 is negligible for every "i", then it immediately follows that its advantage to distinguish the distributions "D""1" = "H"0 and "D""2" = "H""t" must also be negligible. This fact gives rise to the hybrid argument: it suffices to find such a sequence of hybrid distributions and show each pair of them is computationally indistinguishable.
Applications.
The hybrid argument is extensively used in cryptography. Some simple proofs using hybrid arguments are: