Anindya De | in theory

Suppose we have a length-increasing function ${G: \{ 0,1 \}^{n-1} \rightarrow \{ 0,1 \}^n}$ , which we think of as a pseudorandom generator mapping a shorter seed into a longer output.

Then the distribution of ${G(z)}$ for a random seed ${z}$ is not uniform (in particular, it is concentrated on at most ${2^{n-1}}$ of the ${2^n}$ elements of ${\{ 0,1 \}^n}$ ). We say that a statistical test ${D: \{ 0,1 \}^n \rightarrow \{ 0,1 \}}$ has advantage ${\epsilon}$ in distinguishing the output of ${G}$ from the uniform distribution if

$\displaystyle \left| \mathop{\mathbb P}_{z \in \{ 0,1 \}^{n-1}} [D(G(z)) =1 ] - \mathop{\mathbb P}_{x \in \{ 0,1 \}^{n}} [D(x) =1 ] \right| \geq \epsilon \ \ \ \ \ (1)$

If the left-hand side of (1) is at most ${\epsilon}$ for every ${D}$ computable by a circuit of size ${S}$ , then we say that ${G}$ is ${\epsilon}$ -pseudorandom against circuits of size ${S}$ , or that it is an ${(S,\epsilon)}$ -secure pseudorandom generator.

How secure can a pseudorandom generator possibly be? This question (if we make no assumption on the efficiency of ${G}$ ) is related to the question in the previous post on approximating a boolean function via small circuits. Both questions, in fact, are special cases of the question of how much an arbitrary real-valued function must correlate with functions computed by small circuits, which is answered in a new paper with Anindya De and Madhur Tulsiani.

Continue reading →

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

Tag Archives: Anindya De

Efficiently Correlating with a Real-valued Function and Breaking PRGs