PSEUDORANDOM GENERATORS AND THE FREQUENCY OF SIMPLICITY

Authors
HAN YJ HEMASPAANDRA LA
Citation
Yj. Han et La. Hemaspaandra, PSEUDORANDOM GENERATORS AND THE FREQUENCY OF SIMPLICITY, Journal of cryptology, 9(4), 1996, pp. 251-261
Citations number
21
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods","Engineering, Eletrical & Electronic",Mathematics
Journal title
Journal of cryptology → ACNP
ISSN journal
09332790
Volume
9
Issue
4
Year of publication
1996
Pages
251 - 261
Database
ISI
SICI code
0933-2790(1996)9:4<251:PGATFO>2.0.ZU;2-E
Abstract
Allender [2] showed that if there are dense P languages containing onl y a finite set of Kolmogorov-simple strings, then all pseudorandom gen erators are insecure. We extend this by proving that if there are dens e P (or even BPP) languages containing only a sparse set of Kolmogorov -simple strings, then all pseudorandom generators are insecure.