Hybrid argument (cryptography)


In cryptography, the hybrid argument is a proof technique used to show that two distributions are computationally indistinguishable.

History

Hybrid arguments had their origin in a papers by Andrew Yao in 1982 and Shafi Goldwasser and Silvio Micali in 1983.

Formal description

Formally, to show two distributions D1 and D2 are computationally indistinguishable, we can define a sequence of hybrid distributions ''D1 := H''0, H1,..., Ht =: D2 where t is polynomial in the security parameter n. Define the advantage of any probabilistic efficient 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 it has a fixed negligible advantage function ε between distributions Hi and Hi+1 for every i, so in particular,
then it immediately follows that its advantage to distinguish the distributions D1 = H0 and D2 = Ht must also be negligible.

Applications

The hybrid argument is extensively used in cryptography. Some simple proofs using hybrid arguments are:
  • If one cannot efficiently predict the next bit of the output of some number generator, then this generator is a pseudorandom number generator.
  • We can securely expand a PRG with 1-bit output into a PRG with n-bit output.