Date and Time: Sept. 17, 4pm-5pm
Place: Center for ELC (Seminar Room, 4th floor)
Speaker: David Witmer (CMU, Doctoral student)
Title: Goldreich's PRG: Evidence for near-optimal polynomial stretch

Abstract:
Goldreich proposed a simple, highly parallelizable pseudorandom generator
(PRG) construction whose security is related to the hardness of constraint
satisfaction problems.  We give two types of evidence that a particular
instantiation of this generator that stretches n bits to n^1.499 bits is
secure.  Specifically, we show that this PRG is secure against linear tests
and attacks based on the Lasserre hierarchy.  This amount of stretch is
nearly optimal, as there is an algorithm that distinguishes the output from
random if the stretch is O(n^1.5 log(n)).  Previous work had only shown
that Goldreich's generator with stretch up to n^1.249 was secure against
linear tests.

Joint work with Ryan O'Donnell

Host: Osamu Watanabe (watanabe(at)is.titech.ac.jp)