caa a22 4500 477063667 CHVBK 20180405111406.0 cr unu---uuuuu 170330e19960901xx s 000 0 eng 10.1007/BF00189263 doi (NATIONALLICENCE)springer-10.1007/BF00189263 Pseudorandom generators and the frequency of simplicity [Elektronische Daten] [Yenjo Han, Lane Hemaspaandra] Allender [2] showed that if there are dense P languages containing only a finite set of Kolmogorov-simple strings, then all pseudorandom generators are insecure. We extend this by proving that if there are dense P (or even BPP) languages containing only a sparse set of Kolmogorov-simple strings, then all pseudorandom generators are insecure. International Association for Cryptologic Research, 1996 Pseudorandom generator nationallicence Computational complexity nationallicence Kolmogorov complexity nationallicence Injectivity of pseudorandom generators nationallicence Han Yenjo Department of Computer Science, University of Rochester, 14627, Rochester, NY, USA aut Hemaspaandra Lane Department of Computer Science, University of Rochester, 14627, Rochester, NY, USA aut Journal of Cryptology Springer-Verlag 9/4(1996-09-01), 251-261 0933-2790 9:4<251 1996 9 145 https://doi.org/10.1007/BF00189263 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00189263 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Han Yenjo Department of Computer Science, University of Rochester, 14627, Rochester, NY, USA aut NATIONALLICENCE 700 1- Hemaspaandra Lane Department of Computer Science, University of Rochester, 14627, Rochester, NY, USA aut NATIONALLICENCE 773 0- Journal of Cryptology Springer-Verlag 9/4(1996-09-01), 251-261 0933-2790 9:4<251 1996 9 145 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer