On the Existence of Pseudorandom Generators

DOI10.1137/0222069MaRDI QIDQ4277535zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Hugo Krawczyk, Michael Luby

Publication date 13 September 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0222069

zbMATH Keywords

deterministic algorithmspseudorandom generatorsregular one-way function

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Theory of computing (68Q99) Cryptography (94A60)

Recommendations

• scientific article; zbMATH DE number 4182679
• A Pseudorandom Generator from any One-way Function
• One way functions and pseudorandom generators
• Some consequences of the existnce of pseudorandom generators
• Theory of Cryptography

Cited in

(39)

• Encryption modes with almost free message integrity
• Reducing complexity assumptions for statistically-hiding commitment
• Cryptography with constant input locality
• One way functions and pseudorandom generators
• Zeta functions, one-way functions, and pseudorandom number generators.
• Randomness vs time: Derandomization under a uniform assumption
• Input locality and hardness amplification
• On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
• The function-inversion problem: barriers and opportunities
• Channels of small log-ratio leakage and characterization of two-party differentially private computation
• Sharing privacy protected and statistically sound clinical research data using outsourced data storage
• Pseudorandom generators from regular one-way functions: new constructions with improved parameters
• On the complexity of constructing pseudorandom functions (especially when they don't exist)
• Pseudorandom generators and the frequency of simplicity
• Simple constructions from (almost) regular one-way functions
• Towards sound fresh re-keying with hard (physical) learning problems
• On constructing 1-1 one-way functions
• Collision-free hashing from lattice problems
• Garbling XOR gates ``for free in the standard model
• Pseudoentropy: lower-bounds for chain rules and transformations
• (Almost) optimal constructions of UOWHFs from 1-to-1, regular one-way functions and beyond
• scientific article; zbMATH DE number 4141372 (Why is no real title available?)
• Pseudorandom Generators and Typically-Correct Derandomization
• scientific article; zbMATH DE number 3960854 (Why is no real title available?)
• A Pseudorandom Generator from any One-way Function
• scientific article; zbMATH DE number 1788110 (Why is no real title available?)
• Pseudorandom generators and the frequency of simplicity
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• The Complexity of Public-Key Cryptography
• The many entropies in one-way functions
• scientific article; zbMATH DE number 4182679 (Why is no real title available?)
• Pseudo-random generators for all hardnesses
• Paradigms for Unconditional Pseudorandom Generators
• Simple constructions from (almost) regular one-way functions
• A note on Yao's theorem about pseudo-random generators
• A new approach to generic lower bounds. Classical/quantum MDL, quantum factoring, and more
• Somewhat homomorphic encryption from linear homomorphism and sparse LPN
• On linear-size pseudorandom generators and hardcore functions
• Pseudorandom generators against advised context-free languages

This page was built for publication: On the Existence of Pseudorandom Generators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4277535)