In cryptography, the hybrid argument is a proof technique used to show that two distributions are computationally indistinguishable.
Hybrid arguments had their origin in a papers by Andrew Yao in 1982 and Shafi Goldwasser and Silvio Micali in 1983.
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
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(n) and
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,
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.
The hybrid argument is extensively used in cryptography. Some simple proofs using hybrid arguments are: