Evidence for a highly-parallelizable pseudorandom generator with near-optimal stretch
David Witmer
May 7, 2014

A Pseudorandom generator (PRG) is a useful cryptographic primitive that amplifies randomness. Much work has been devoted to the important problem of finding more efficient PRGs. Goldreich proposed a highly parallelizable 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 strong semidefinite programming relaxations. This amount of stretch is nearly optimal, as there is an algorithm that distinguishes the output from random if the stretch is greater than n^1.5. 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