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.