Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Allender. Some consequences of the existence of pseudorandom generators, preliminary version. Proceedings of the 19th ACM Symposium on Theory of Computing, pages 151–159, 1987.
E. Allender. Some consequences of the existence of pseudorandom generators. Journal of Computer and System Sciences, 39:101–124, 1989.
E. Allender. Applications of time-bounded Kolmogorov complexity in complexity theory. In O. Watanabe, editor, Kolmogorov Complexity and Computational Complexity, EATCS Monographs on Theoretical Computer Science, pages 4–22. Springer-Verlag, New York, 1992.
M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 112–117, 1982. Final version appears as [5].
M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850–864, 1984.
R. Boppana and R. Hirschfeld. Pseudorandom generators and complexity classes. In Advances in Computing Research, volume 5, pages 1–26. JAI Press, Greenwich, CT, 1989.
R. Gavaldà and J. Balcázar. Strong and robustly strong polynomial-time reducibilities to sparse sets. Theoretical Computer Science, 88:1–14, 1991.
J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675–695, 1977.
O. Goldreich, H. Krawczyk, and M. Luby. On the existence of pseudorandom generators. SIAM Journal on Computing, 22(6): 1163–1175, 1993.
J. Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 439–445,1983.
J. Håstad. Pseudo-random generators under uniform assumptions. Proceedings of the 22nd ACM Symposium on Theory of Computing, pages 395–404, 1990.
J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979.
R. Impagliazzo, L. Levin, and M. Luby. Pseudo-random generation from one-way functions. Proceedings of the 21st ACM Symposium on Theory of Computing, pages 12–24, 1989.
L. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61:15–37, 1984.
L. Levin. One way functions and pseudorandom generators. Combinatorica, 7(4):357–363, 1987.
M. Li and P. Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, New York, 1993.
N. Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991.
M. Sipser. A complexity theoretic approach to randomness. Proceedings of the 15th ACM Symposium on Theory of Computing, pages 330–335, 1983.
A. Yao. Theory and applications of trapdoor functions. Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 80–91, 1982.
S. Zachos and H. Heller. A decisive characterization of BPP. Information and Control, 69:125–135, 1986.
M. Zimand. Large sets in AC0: a Kolmogorov complexity related property and some applications. Proceedings of the 1th International Conference on Computing and Information, to appear.
Author information
Authors and Affiliations
Additional information
Communicated by Andrew C.-C. Yao
This research was supported in part by Grants NSF-CCR-8957604, NSF-INT-9116781/JSPS-ENG-207, and NSF-CCR-9322513. The work of the second author was done in part while visiting the University of Electro-Communications, Tokyo.
Rights and permissions
About this article
Cite this article
Han, Y., Hemaspaandra, L.A. Pseudorandom generators and the frequency of simplicity. J. Cryptology 9, 251–261 (1996). https://doi.org/10.1007/BF00189263
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00189263