I am trying to understand what the Hybrid Argument is in cryptography and why is it useful.
By the definition of the Hybrid Argument we know that to prove that if two distributions $D = D_1, D_2, ..., D_k = D'$ can be distinguished, then $\exists D_i, D_{i+1} $ that can be distinguished.
Let:
- $\alpha, \beta, \gamma \in \mathbf{N}$
- $0 < \alpha < \beta < \gamma$
- $g_1$ be a $(\alpha, \beta)$-pseudo-random generator
- $g_2$ be a $(\beta, \gamma)$-pseudo-random generator
Consider $g(x) = g_2(g_1(x))$, then we want to prove by using the Hybrid Argument that $g(x)$ is $(\alpha-\gamma)$-pseudo-random generator.
Let's also define the following distributions on $ \{ 0,1 \}^\gamma$:
- $D_1: y$ uniform in $ \{ 0,1 \}^\gamma$
- $D_2: y = g_1(x)$ for $x$ uniform in $ \{ 0,1 \}^\alpha$
- $D_3: y = g_2(z)$ for $z$ uniform in $ \{ 0,1 \}^\beta$
Here we can prove that g is a pseudo-random generator by using the triangle inequality:
By reduction to absurd, there's a distinguisher $A$ between $D_1$ and $D_2 \rightarrow A$ must either:
- Distinguish between $D_1$ and $D_3$
- Distinguish between $D_2$ and $D_3$
It's in this point that the triangle inequality is used to show the contradiction. Wouldn't it be easy for the distinguisher A to differentiate the two distributions as they have different length?
Also, what's the triangle inequality in this context and why does it help us deduce that there's a contradiction with this statement?