Equivalence of NBU PRG and PRG

From CRYPTUTOR

Jump to: navigation, search

We show that two definitions of pseudorandom generators are equivalent:

[edit]

IND-PRG implies NBU-PRG

The IND-PRG definition is a general definition that includes all ways of distinguishing the pseudorandom distribution from random, including the method in the NBU-PRG experiment.

Suppose G is an IND-PRG. For any NBU-PRG adversary A, we can give to A the first i − 1 bits of a string and check if its guess for the ith bit is correct. This process distinguishes G's output distribution from the uniform distribution with the same advantage as A in the NBU-PRG experiment. Since we assumed G was an IND-PRG, this advantage must be negligible.

[edit]

NBU-PRG implies IND-PRG

Let G:\{0,1\}^k \to \{0,1\}^{\ell(k)} be an NBU-PRG. We use a hybrid argument to establish that it also must satisfy the IND-PRG definition. We define the following hybrid distributions over \ell(k)-bit strings:

\mathcal{D}_i = \{ y_1 \cdots y_i\, r_{i+1} \cdots r_{\ell(k)} \}_{ x \gets \{0,1\}^k ; y=G(x); r \gets \{0,1\}^{\ell(k)} }

Observe that \mathcal{D}_0 is the uniform distribution, while \mathcal{D}_{\ell(k)} is G's output distribution \{ G(x) \}_{x \gets \{0,1\}^k}. Since \ell(k) is a polynomial in the security parameter k, all that remains is to show that adjacent hybrids are computationally indistinguishable.

Suppose for contradiction that \mathcal{D}_{i-1} and \mathcal{D}_i are not computationally indistinguishable. Then some adversary A can distinguish between the distributions with non-negligible advantage \epsilon\,. Let us construct an NBU-PRG adversary A^*\, to predict the ith bit of G:

A^*\,:
  1. On input y_1 \cdots y_{i-1}, generate truly random bits r_i \cdots r_{\ell(k)}.
  2. Give y_1 \cdots y_{i-1} \, r_i \cdots r_{\ell(k)} to A.
  3. If A outputs 0, output r_i\,, otherwise output its complement (as our guess for the ith bit of G).

We now analyze the advantage of A^*\, in guessing the ith bit of G. Let \mathcal{E} be the event that it guesses correctly.

This page is under construction. Do not rely on its accuracy until it is finished. Please edit this page or use the talk page to leave comments.

So \Pr[\mathcal{E}] = 1/2 + \epsilon, and A^*\, has non-negligible advantage in the NBU-PRG experiment -- a contradiction. Thus the adjacent hybrid distributions \mathcal{D}_{i-1} and \mathcal{D}_i are computationally indistinguishable, as desired.

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Equivalence_of_NBU_PRG_and_PRG"