Yao’s pseudorandom generator construction
E503603
Yao’s pseudorandom generator construction is a foundational cryptographic method that transforms any one-way function into a pseudorandom generator, establishing a deep connection between computational hardness and pseudorandomness.
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
cryptographic construction
ⓘ
pseudorandom generator construction ⓘ theoretical computer science concept ⓘ |
| assumes | existence of a one-way function secure against polynomial-time adversaries ⓘ |
| author | Andrew Chi-Chih Yao NERFINISHED ⓘ |
| basedOn | one-way function ⓘ |
| consequence | equivalence between one-way functions and pseudorandom generators up to standard assumptions ⓘ |
| coreIdea |
extract one pseudorandom bit from a one-way function using a hard-core predicate
ⓘ
iterate the hard-core predicate on related inputs to obtain multiple pseudorandom bits ⓘ |
| establishes | implication from existence of one-way functions to existence of pseudorandom generators ⓘ |
| field |
computational complexity theory
ⓘ
cryptography ⓘ theoretical computer science ⓘ |
| formalizedIn | standard cryptography textbooks ⓘ |
| goal | construct a pseudorandom generator from any one-way function ⓘ |
| hasImpactOn |
derandomization of probabilistic algorithms
ⓘ
design of pseudorandom functions ⓘ understanding of minimal assumptions for cryptography ⓘ |
| hasProperty |
polynomial-time computable given oracle access to the one-way function
ⓘ
security based on hardness of inverting underlying one-way function ⓘ stretchable output length ⓘ |
| implies |
equivalence between next-bit unpredictability and pseudorandomness of distributions
ⓘ
existence of pseudorandom generators if one-way functions exist ⓘ |
| influenced |
modern cryptographic pseudorandomness theory
ⓘ
subsequent constructions of pseudorandom generators from weaker assumptions ⓘ |
| input | one-way function ⓘ |
| introducedIn | paper "Theory and Application of Trapdoor Functions" NERFINISHED ⓘ |
| mathematicalArea |
complexity-theoretic cryptography
ⓘ
probability theory in computation ⓘ |
| namedAfter | Andrew Chi-Chih Yao NERFINISHED ⓘ |
| output | pseudorandom generator ⓘ |
| relatedTo |
Blum-Blum-Shub pseudorandom generator
NERFINISHED
ⓘ
Blum-Micali pseudorandom generator NERFINISHED ⓘ Goldreich-Levin hard-core predicate theorem NERFINISHED ⓘ |
| relatesConcept |
computational hardness
ⓘ
pseudorandomness ⓘ |
| securityArgument | hybrid argument over output bits ⓘ |
| securityNotion | next-bit unpredictability ⓘ |
| taughtIn | graduate cryptography courses ⓘ |
| usedIn |
complexity-theoretic foundations of cryptography
ⓘ
design of stream ciphers ⓘ proofs about derandomization ⓘ |
| usesConcept |
computational indistinguishability
ⓘ
hard-core predicate ⓘ hybrid argument ⓘ |
| yearProposed | 1982 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.
Blum–Micali pseudorandom number generator
→
influenced
→
Yao’s pseudorandom generator construction
ⓘ