Seminario Interdipartimentale di Algoritmica
 
 
 

Lunedì 15 Dicembre 2003  ore 12:00
An epsilon-Biased Generator in NC0
Luca Trevisan
UC Berkeley

DIS - Dipartimento di Informatica e Sistemistica, via Salaria 113
Aula C2, piano secondo

Abstract:
We study a question first asked by Cryan and Miltersen: is it
possible to construct a (cryptographically strong) pseudorandom
generator such that every bit of the output dependes only on a
constant number k of bits of the seed? Cryan and Miltersen rule out
the case k=3 and leave the case k>3 open, while suggesting a
possible line of attack.
We rule out the case k=4, and give a construction of an
"epsilon-biased" generator where every bit of the output depends on
only 5 bits of the seed. Being "epsilon-biased" is a weaker property
than being a cryptographically strong generator, but our result
shows that pseudorandom generators with k=5 might exist, and it
also shows that their existence cannot be ruled out using the
approach suggested by Cryan and Miltersen.
We will also mention some generalizations of our results to larger
values of k.
(Joint work with Elchanan Mossel and Amir Shpilka)