Hybrid Arguments and PRFs
  • One-Way Function (OWF): A function that is easy to compute but difficult to reverse.

  • One-Way Permutation (OWP): A one-to-one function that is easy to compute but difficult to reverse.

  • Pseudo-Random Function (PRF): A function that is indistinguishable from a random function.

  • A hardcore bit for a one-way function is a bit in the function's output that is computationally hard to predict given its input but can be efficiently verified.

Hybrid Arguments and applications

Hybrid argument, much like induction, is a pr2oof technique to prove that two distributions are computaionally indistinguishable. Why would you need such a proof? Turns out, cryptographic primitives (especially one proof we will talk about later) depend on such proof mechanisms.

To put it down more formally, assume two distributions exist, D1D_1 and D2D_2. Let us assume these two distributions are computationally indistinguable (this is a starting assumption). From here, we can define a hybrid distribution such that D1:=H0,H1,...,Hk=:D2D_1 := H_0, H_1, ..., H_k =: D_2, where kk is an upperbound we don't have to worry about right now.

Assume now, that there exists an interpolation DiD_i such that as ii is (reasonably) small and as it increases, we go from D1D_1 to D2D_2.

Next assumption we can do is assume there is a probablistic efficieint algorithm AA (An algorithm that run in polynomial time and are allowed to use randomness in their computations). The advantage of A in distinguishing D1D_1 from D2D_2 is given by the following expression.

Adv(A)=Pr[A(x)=1,x sampled from D1]Pr[A(x)=1,x sampled from D2]Adv(A) = \left| \Pr[A(x) = 1, x \text{ sampled from } D_1] - \Pr[A(x) = 1, x \text{ sampled from } D_2] \right|

In simpler terms, the advantage of AA measures how much better AA can distinguish between samples drawn from D1D_1 and D2D_2 compared to a random guess. If Adv(A)Adv(A) is close to 0, it means AA cannot distinguish between D1D_1 and D2D_2 better than random chance, indicating that the two distributions are computationally indistinguishable. Conversely, if Adv(A)Adv(A) is significantly greater than 0, it implies that AA can successfully distinguish between D1D_1 and D2D_2, suggesting that the two distributions are not computationally indistinguishable.

In the following image you can see two distributions (here visualised as true and pseudo randomness), and they start to become indistinguishable as we move "forward" in the values.

Hybrid Arguments

Let's prove a corollary using hybrid arguments

Corollary 81.7: Let ff be a one-way permutation (OWP) and hh a hard core bit for ff. Then the function G(x)=h(x)h(f(x))h(f(2)(x))h(f(n)(x))G(x) = h(x) \| h(f(x)) \| h(f^{(2)}(x)) \| \ldots \| h(f^{(n)}(x)) is a pseudorandom generator (PRG).

Proof by intuition

  1. Hybrid 0: Start with a truly random string R_0.
  2. Hybrid 1: Replace the last bit of R_0 with h(f(x)). Since h is a hard core bit, Hybrid 1 is computationally indistinguishable from Hybrid 0.
  3. Hybrid 2: Replace the last two bits of R_0 with h(f(x)) | h(f^{(2)}(x)). Since h is a hard core bit and f is a one-way permutation, Hybrid 2 is computationally indistinguishable from Hybrid 1.
  4. Continue this process up to Hybrid n, where G(x)=h(x)h(f(x))h(f(2)(x))...h(f(n)(x))G(x) = h(x) \| h(f(x)) \| h(f^{(2)}(x)) \| ... \| h(f^{(n)}(x)).
  5. Since each step only introduces a small change to the distribution, G(x) is computationally indistinguishable from a truly random string.
  6. Therefore, G(x) is a pseudorandom generator (PRG) based on the assumption that f is a one-way permutation and h is a hard core bit for f.

The formal proof is found in the reference.



Corollary 81.7 in Pass' A course in cryptography (opens in a new tab) Lecture Notes (opens in a new tab)