Hybrid argument (cryptography)

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

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Provenance

snapshot enwiki-001364917482 · captured 2026-07-19 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Hybrid argument (cryptography)”, snapshot enwiki-001364917482. https://encyclopegia.org/a/hybrid-argument-cryptography

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.