Hybrid argument (cryptography)
In cryptography, the hybrid argument is a proof technique used to show that two distributions are computationally indistinguishable.
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 the papers by Andrew Yao in 1982 and Shafi Goldwasser and Silvio Micali in 1983.
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 n. Define the advantage of any probabilistic efficient (polynomial-bounded time) algorithm A as \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|, 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{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}).
Thus there must exist some k s.t. 0 ≤ k \mathsf{Adv}_{H_k, H_{k+1}}^{\mathsf{dist}}(\mathbf{A}) \geq \mathsf{Adv}_{D_1, D_2}^{\mathsf{dist}}(\mathbf{A})/t(n). 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 i and H i+1 for every i, so in particular, \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), then it immediately follows that its advantage to distinguish the distributions D 1 = H 0 and D 2 = H t 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). We can securely expand a PRG with 1-bit output into a PRG with n-bit output.
See also
Interactive proof system Universal composability
Text derived from https://en.wikipedia.org/w/index.php?oldid=1364917482 under CC BY-SA 4.0; modifications have been made.