The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
A Pseudorandom Generator from Any One-Way Function
Johan Hastad, Russell Impagliazzo, Leonid A. Levin, Michael Luby,
Pages. 1364-1396
Abstract
Contents 1. Introduction
1.1. Concepts and tools
1.2. Outline
2. Basic notation
2.1. Probability notation
2.2. Entropy
2.3. Ensembles
3. Definitions of primitives and reductions
3.1. Adversaries and security
3.2. One-way function
3.3. Pseudorandom generator
3.4. Pseudoentropy and false-entropy generators
3.5. Hidden bits
3.6. Reductions
4. Hidden bits, hash functions, and computational entropy
4.1. Constructing a hidden bit
4.2. One-way permutation to a pseudorandom generator
4.3. One-to-one one-way function to a pseudoentropy generator
4.4. Universal hash functions
4.5. Smoothing distributions with hashing
4.6. Pseudoentropy generator to a pseudorandom generator
4.7. False entropy generator to a pseudoentropy generator
4.8. Mildly nonuniform to a uniform pseudorandom generator
4.9. Summary
5. Extracting entropy from one-way functions
5.1. One-way function with approximable preimage sizes to a pseudoentropy generator
6. Any one-way function to a false-entropy generator
6.1. Finding determined hidden bits
6.2. Construction and main theorem
6.3. The main lemmas
7. A direct construction
8. Conclusions
Key words one-way function, pseudorandom generator, cryptography, complexity theory
Mathmatical Subject Classification 68P25, 68Q25, 68Q99