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

${\displaystyle {\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,

${\displaystyle {\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 < t(n) and

${\displaystyle {\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,

${\displaystyle \epsilon (n)\geq {\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₁ = H₀ and D₂ = 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

Notes

References

• Dodis, Yevgeniy. "Introduction to Cryptography Lecture 5 notes" (PDF). Archived from the original (PDF) on 2014-12-25.
• Pass, Rafael. "A Course in Cryptography" (PDF).
• Fischlin, Marc; Mittelbach, Arno. "An Overview of the Hybrid Argument" (PDF).