A Pseudorandom Generator from any One-way Function

1999/01/01 by Johan Håstad, Russell Impagliazzo, Leonid A. Levin +1 · 9 citations
Computer Science · Mathematics · #Cryptography and Data Security #Chaos-based Image/Signal Encryption #Computability, Logic, AI Algorithms #Pseudorandom generator #Pseudorandom number generator #Pseudorandom generator theorem #Pseudorandom function family #Self-shrinking generator #Pseudorandomness #Random seed #Generator (circuit theory) #Construct (python library) #Computer science #Function (biology) #Linear congruential generator #Algorithm #Mathematics #Physics #Induction generator #Power (physics) #Programming language

paper · doi:10.1137/s0097539793244708

openalex publication_date 1999/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15

Abstract

Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any one-way function. Since it is easy to construct a one-way function from a pseudorandom generator, this result shows that there is a pseudorandom generator if and only if there is a one-way function.

Citations

• A Mathematical Theory of Communication
• How to Construct Pseudorandom Permutations from Pseudorandom Functions
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• New directions in cryptography
• BPP has subexponential time simulations unlessEXPTIME has publishable proofs
• Probabilistic encryption
• A method for obtaining digital signatures and public-key cryptosystems

Cited by

• On Cryptographic Assumptions and Challenges
• Public-key cryptosystems from the worst-case shortest vector problem
• A Decade of Lattice Cryptography
• Evolution and future directions in embedded security
• W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes
• On the Security of the Winternitz One-Time Signature Scheme
• The Hardness of Learning Quantum Circuits and its Cryptographic Applications
• Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem
• More Efficient Privacy Amplification With Less Random Seeds via Dual Universal Hash Function
• Computational Complexity
• Pseudorandom generator [wikipedia]