Pseudorandom Generators and the Frequency of Simplicity, or... Just What Does the NSA Do with Shoo-Fly Pie and Whipped Cream?

Lane A. Hemaspaandra
Computer Science Department
University of Rochester
lane@cs.rochester.edu

ABSTRACT

In the 1980s, Allender showed that if there are dense polynomial-time decidable languages containing only a finite set of non-random strings, then all pseudorandom generators are insecure. We extend this by proving that if there are dense polynomial-time decidable (or even BPP) languages containing only a sparse set of non-random strings, then all pseudorandom generators are insecure. Terms such as pseudorandom generator, sparse, etc. will be defined in the talk, and so no background will be assumed other than a standard knowledge of the computers and whipped cream.

Colloquia Series page.