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) Cryptography (94A60) Theory of computing (68Q99)

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

(38)

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

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)