What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?

Question

I am reading the classic "Hardness vs Randomness" by Nisan and Wigderson. Let $B=\{0,1\}$, and fix a function $l\colon \mathbb{N} \to \mathbb{N}$. They define a family of functions $G = \{G_n : B^{l(n)} \to B^n\}$ to be pseudorandom in case for every circuit of size $n$ we have

$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | < 1/n$

(where $x \in B^{n},y \in B^{l(n)}$ are uniform random variables).

I understand that I am to think of $x$ and $y$ as random variables, and that I want to compare the distance between $x$ and $G(y)$ as random variables. I get the intuition that circuits are being used as sort of "tests" in to see if $G$ can be "figured out." What I am really struggling with is why the condition $(*)$ is the right one. Does anyone have any advice on how to think of this definition?

Answer 1

There are two aspect that need to be mentioned.

The first is the general idea of defining a PRG by having its output look different than uniform to small circuits. This idea goes back to Yao and is really the strongest possible definition you can ask for when aiming explicitly at pseudo-randomness for computationally-bounded observers.

The second aspect is the choice of parameters where we limit the circuit size to be $n$ and the acceptance probability difference to be $1/n$, where $n$ is also the PRG output size. This choice is somewhat different than the usual crypto one where the circuit size is $poly(n)$ and the probability difference is required to be smaller than any $poly(n)$. In our case specific parameters (rather than $poly(n)$) were needed as to get the tightest results including, in particular polynomial simulations. While in principle one could have 3 different parameters, it turned out that our results had these working essentially in the same way so we folded them to a single one (in addition to the input size $l(n)$ which was viewed as a function of $n$).

Answer 2

I am by no means an expert on this, but a key component of the definition of pseudorandomness (as opposed to attempts to define randomness) is that the goal of something "pseudorandom" is to fool a circuit. In other words, the motivation is to think of the pseudorandom string being supplied to the circuit instead of the truly random string.

In that sense, it's not really that you're trying to pretend that $x$ and $G(y)$ "look the same". It's that they "look the same" to a circuit (of necessarily bounded complexity).

So the role of the circuit is crucial, as opposed to merely being a "test function".

Answer 3

Hopefully, I can expand just a little on Suresh's response. First, I don't think that the strictness of the inequality is needed in your $(*)$, and I am also not sure why $1/n$ is needed, and not $1/2n$ or something else. However, practically, I think 1/n is enough to get some interesting theoretical results.

But then you almost certainly want to assert that each $G_i$ is computable in some amount of time, say exponential. Further, I think you will have to assert that $l(n) < n$. You can think of $l(n)$ as the seed length. Thus $G_i$ is pseudorandom if it can increase the number of bits in a random string of length $l(n)$ without being detected by a circuit of size less than $n$.