SCIENCE@home

On /spl epsiv/-biased generators in NC/sup 0/

Elchanan Mossel,Amir Shpilka,L. Trevisan

Published 2003 in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.

ABSTRACT

M. Cryan and P.B. Miltersen (2001) recently considered the question of whether there can be a pseudorandom generator in NC/sup 0/, that is, a pseudorandom generator that maps n bits strings to m bits strings and such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m /spl ges/ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k /spl ges/ 4. In fact they ask whether every NC/sup 0/ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC/sup 0/ generator can sample an /spl epsiv/-biased space with negligible /spl epsiv/? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2/sup -/spl Omega/(n/c4)/. For large values of k, we construct generators that map n bits to n/sup /spl Omega/(/spl radic/k)/ bits and such that every XOR of outputs has bias 2/sup -n1/(2/spl radic/k)/. We also present a polynomial-time distinguisher for k = 4, m /spl ges/ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m /spl ges/ /spl Omega/(2/sup k/n/sup [k/2]/). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2/sup -/spl Omega/(n)/ and which map n bits to /spl Omega/(n/sup 2/) bits.

PUBLICATION RECORD

  • Publication year

    2003

  • Venue

    44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.

  • Publication date

    2003-10-20

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    DOI 10.1109/SFCS.2003.1238188
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-21 of 21 references · Page 1 of 1

CITED BY

Showing 1-63 of 63 citing papers · Page 1 of 1