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 ''D''₁ and ''D''₂ are computationally indistinguishable, we can define a sequence of ''hybrid distributions'' ''D''₁ := ''H''₀, ''H''₁, ..., ''H''_''t'' =: ''D''₂ where ''t'' is polynomial in the security parameter ''n''. Define the advantage of any probabilistic efficient (polynomial-bounded time) algorithm A as

:\mathsf_^(\mathbf) := \left, \Pr \stackrel H_i : \mathbf(x)=1- \Pr \stackrel H_ : \mathbf(x)=1\,

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,

:$\mathsf_^(\mathbf) \leq \sum_^\mathsf_^(\mathbf).$

Thus there must exist some ''k'' s.t. 0 ≤ ''k'' < ''t(n)'' and

:$\mathsf_^(\mathbf) \geq \mathsf_^(\mathbf)/t(n).$

Since ''t'' is polynomial-bounded, for any such algorithm A, if we can show that it has a negligible advantage function between distributions ''H''_''i'' and ''H''_''i''+1 for every ''i'', that is,

:$\epsilon(n) \ge \mathsf_^(\mathbf) \geq \mathsf_^(\mathbf)/t(n),$

then it immediately follows that its advantage to distinguish the distributions ''D''_''1'' = ''H''₀ 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:
* If one cannot efficiently predict the next bit of the output of some number generator, then this generator is a pseudorandom number generator (PRG).
* We can securely expand a PRG with 1-bit output into a PRG with ''n''-bit output.Lemma 80.5, Corollary 81.7 in Pass's notes.

See also

* Interactive proof system
* Universal composability

Notes

References

*
*
* {{cite web, last1=Fischlin, first1=Marc, last2=Mittelbach, first2=Arno, title=An Overview of the Hybrid Argument, url=https://eprint.iacr.org/2021/088.pdf

Cryptography