“Hybrid argument (Cryptography)”的意思、由来-开放百科全书

词条

Hybrid argument (Cryptography)

释义

Formal description
Applications
Notes
References

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

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. Define the advantage of any probabilistic efficient (polynomial-bounded time) algorithm A as

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,

Thus there must exist some k s.t. 0 ≤ k < t and

Since t is polynomial-bounded, for any such algorithm A, if we can show that its advantage to distinguish the distributions H_i and H_i+1 is negligible for every i, then it immediately follows that its advantage to distinguish the distributions D₁ = H₀ and D₂ = H_t 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.^[1]

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).^[2]
We can securely expand a PRG with 1-bit output into a PRG with n-bit output.^[3]

Notes

1. ^Lemma 3 in Dodis's notes.
2. ^Theorem 1 in Dodis's notes.
3. ^Lemma 80.5, Corollary 81.7 in Pass's notes.

References

{{cite web|last1=Dodis|first1=Yevgeniy|title=Introduction to Cryptography Lecture 5 notes|url=http://cs.nyu.edu/courses/fall08/G22.3210-001/lect/lecture5.pdf}}
{{cite web|last1=Pass|first1=Rafael|title=A Course in Cryptography|url=https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf}}

1 : Cryptography

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。