<p>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. </p>

<p>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" <em>to a circuit</em> (of necessarily bounded complexity). </p>

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

CC BY-SA 3.0
2012-11-14T04:19:53.130Z
2012-11-14T04:19:53.130Z
Suresh Venkat
<p>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.</p>

<p>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) &lt; 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$.</p>

CC BY-SA 3.0
2012-11-14T09:08:12.790Z
2012-11-14T09:08:12.790Z
Jonathan Gallagher
<p>There are two aspect that need to be mentioned.  </p>

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

<p>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$).</p>

CC BY-SA 3.0
2012-11-14T19:50:05.810Z
Thank you Noam for the answer. It was very much helpful.
user12484
CC BY-SA 3.0
2012-11-14T18:23:43.850Z
2012-11-14T18:23:43.850Z
Noam
<p>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 <strong>pseudorandom</strong> in case for every circuit of size $n$ we have</p>

<p>$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | &lt; 1/n$</p>

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

<p>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?</p>

CC BY-SA 3.0
2012-11-14T16:16:18.693Z
Check your spelling of the authors' names...
rphv
CC BY-SA 3.0
2012-11-14T16:22:50.633Z
@rphv fixed it.
Suresh Venkat
<cr.crypto-security><pseudorandomness><pseudorandom-generators><security>
What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?
user12484
# What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?

(Asked by: username_0 on 2012-11-14)

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?

**Tags:** cr.crypto-security, pseudorandomness, pseudorandom-generators, security

> **Comments:**
> **username_1**: Check your spelling of the authors' names...  
> **username_2**: @username_1 fixed it.  

---

## 3 answers

### Answer by username_4 on 2012-11-14. Score: 21 | Accepted answer

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$).

> **Comments:**
> **username_0**: Thank you username_4 for the answer. It was very much helpful.  

---

### Answer by username_2 on 2012-11-14. Score: 4

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 by username_3 on 2012-11-14. Score: 2

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$.


---

