View source for Hybrid argument (cryptography)

In [[cryptography]], the '''hybrid argument''' is a proof technique used to show that two distributions are [[Computational indistinguishability|computationally indistinguishable]].

==History==
Hybrid arguments had their origin in a papers by [[Andrew Yao]] in 1982 and Shafi Goldwasser and Silvio Micali in 1983.<ref>Bellare, Mihir, and Phillip Rogaway. "[https://eprint.iacr.org/2004/331.pdf Code-based game-playing proofs and the security of triple encryption.]" Cryptology ePrint Archive (2004)</ref>

==Formal description==
Formally, to show two distributions ''D''<sub>1</sub> and ''D''<sub>2</sub> are computationally indistinguishable, we can define a sequence of ''hybrid distributions'' ''D''<sub>1</sub> := ''H''<sub>0</sub>, ''H''<sub>1</sub>, ..., ''H''<sub>''t''</sub> =: ''D''<sub>2</sub> where ''t'' is polynomial in the security parameter ''n''. Define the advantage of any probabilistic efficient (polynomial-bounded time) algorithm '''A''' as

:<math>\mathsf{Adv}_{H_i, H_{i+1}}^{\mathsf{dist}}(\mathbf{A}) := \left|\Pr[x \stackrel{\$}{\gets} H_i : \mathbf{A}(x)=1] - \Pr[x \stackrel{\$}{\gets} H_{i+1} : \mathbf{A}(x)=1] \right|,</math>

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''',

:<math>\mathsf{Adv}_{D_1, D_2}^{\mathsf{dist}}(\mathbf{A}) \leq \sum_{i=0}^{t-1}\mathsf{Adv}_{H_i, H_{i+1}}^{\mathsf{dist}}(\mathbf{A}).</math>

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

:<math>\mathsf{Adv}_{H_k, H_{k+1}}^{\mathsf{dist}}(\mathbf{A}) \geq \mathsf{Adv}_{D_1, D_2}^{\mathsf{dist}}(\mathbf{A})/t(n).</math>

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

:<math>\epsilon(n) \ge \mathsf{Adv}_{H_k, H_{k+1}}^{\mathsf{dist}}(\mathbf{A}) \geq \mathsf{Adv}_{D_1, D_2}^{\mathsf{dist}}(\mathbf{A})/t(n),</math>

then it immediately follows that its advantage to distinguish the distributions ''D''<sub>''1''</sub> = ''H''<sub>0</sub> and ''D''<sub>''2''</sub> = ''H''<sub>''t''</sub> 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.<ref>Lemma 3 in Dodis's notes.</ref>

==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).<ref>Theorem 1 in Dodis's notes.</ref>
* We can securely expand a PRG with 1-bit output into a PRG with ''n''-bit output.<ref>Lemma 80.5, Corollary 81.7 in Pass's notes.</ref>

==See also==
* [[Interactive proof system]]
* [[Universal composability]]

==Notes==
{{div col|colwidth=30em}}
{{reflist}}
{{div col end}}

==References==
* {{cite web|last1=Dodis|first1=Yevgeniy|title=Introduction to Cryptography Lecture 5 notes|url=http://www.cs.nyu.edu/courses/fall08/G22.3210-001/lect/lecture5.pdf|archive-url=https://web.archive.org/web/20141225222349/http://www.cs.nyu.edu/courses/fall08/G22.3210-001/lect/lecture5.pdf |archive-date=2014-12-25 }}
* {{cite web|last1=Pass|first1=Rafael|title=A Course in Cryptography|url=https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf}}
* {{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}}

[[Category:Cryptography]]