{{Short description|Cryptographic proof technique}} 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.<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 fixed negligible advantage function ''ε(n)'' between distributions ''H''<sub>''i''</sub> and ''H''<sub>''i''+1</sub> for every ''i'', so in particular,
:<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.
==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