Next-bit unpredictable PRG

From CRYPTUTOR

(Redirected from Next Bit Unpredictable PRG)
Jump to: navigation, search

Next-bit unpredictability is an alternative definition for pseudorandom generators that is based on predictability instead of computational indistinguishability. However, the two definitions are equivalent.

[edit]

Definition

A function G is a next-bit unpredictable pseudorandom generator (NBU-PRG) if it has the following properties (the first two are the same as in the standard definition of a pseudorandom generator):

  • Efficiency: G is computable in (deterministic) polynomial time in the input length.
  • Regular stretch: There is a polynomial \ell such that:
    • \ell(k) > k for all k. The quantity \ell(k)-k is often called the stretch of G.
    • |G(x)| = \ell(|x|) for all strings x.
  • Unpredictability: For all non-uniform PPT adversaries A (polynomial in the security parameter k), and for all i \in \{1, \ldots, \ell(k)\}, the advantage of A in the following experiment is negligible in k:
Next-Bit Prediction Experiment:
  1. We choose a random x \gets \{0,1\}^k.
  2. We compute y=G(x)\, and give the first i − 1 bits (y_1 \cdots y_{i-1}) to the adversary A.
  3. A outputs a bit b (a guess for y_i\,).
We say that the advantage of A in this experiment is \Pr[ b = y_i ] - 1/2.

That is, given the first i − 1 bits of output from G, no adversary can guess the ith bit with significant advantage.

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Next-bit_unpredictable_PRG"