4
$\begingroup$

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:

  1. $\alpha, \beta, \gamma \in \mathbf{N}$
  2. $0 < \alpha < \beta < \gamma$
  3. $g_1$ be a $(\alpha, \beta)$-pseudo-random generator
  4. $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$

enter image description here

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?

$\endgroup$
1
  • $\begingroup$ You last hybrid does not correspond to your construction. That's the first clue, that something went wrong. $\endgroup$
    – Maeher
    Feb 28, 2023 at 15:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.