Yao’s next-bit test
E503604
Yao’s next-bit test is a foundational cryptographic criterion that characterizes pseudorandomness by requiring that no efficient algorithm can predict the next bit of a sequence significantly better than random guessing, given all previous bits.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
cryptographic test
ⓘ
pseudorandomness criterion ⓘ theoretical computer science concept ⓘ |
| advantageMeasure | difference between predictor’s success probability and 1/2 ⓘ |
| advantageRequirement | advantage must be negligible in the security parameter ⓘ |
| adversaryGoal | predict the next output bit ⓘ |
| adversaryView | adversary sees prefix of the sequence ⓘ |
| appliesTo |
bit sequences
ⓘ
pseudorandom generators ⓘ |
| assumes | computationally bounded adversaries ⓘ |
| characterizes | pseudorandomness ⓘ |
| contrastWith | statistical tests of randomness ⓘ |
| coreRequirement | no efficient algorithm can predict the next bit significantly better than random guessing ⓘ |
| criterionType | next-bit unpredictability test ⓘ |
| efficiencyModel | probabilistic polynomial-time algorithms ⓘ |
| equivalenceType | if and only if characterization of pseudorandom generators ⓘ |
| equivalentTo | indistinguishability from a truly random sequence by any efficient algorithm ⓘ |
| field |
computational complexity theory
ⓘ
cryptography ⓘ theoretical computer science ⓘ |
| formalizes | unpredictability of bits ⓘ |
| given | all previous bits of the sequence ⓘ |
| implies | no polynomial-time distinguisher can tell the sequence from uniform with non-negligible advantage ⓘ |
| influenced | formal definitions of pseudorandomness in cryptography ⓘ |
| isImpliedBy | indistinguishability-based definition of pseudorandom generators ⓘ |
| logicalForm |
if a generator is pseudorandom then it passes the next-bit test
ⓘ
if a generator passes the next-bit test then it is pseudorandom ⓘ |
| mathematicalNature | asymptotic, complexity-theoretic definition ⓘ |
| namedAfter | Andrew Chi-Chih Yao NERFINISHED ⓘ |
| nature | computational, not information-theoretic, notion of randomness ⓘ |
| originatesFrom | Yao’s 1982 work on pseudorandom number generation ⓘ |
| outputDomain | binary sequences ⓘ |
| quantifiesOver |
all polynomial-time prediction algorithms
ⓘ
all positions in the output sequence ⓘ |
| randomGuessBaseline | probability 1/2 of predicting the next bit ⓘ |
| relatedConcept |
Yao’s theorem on pseudorandom generators
NERFINISHED
ⓘ
computational indistinguishability ⓘ hard-core predicates ⓘ one-way functions ⓘ |
| securityParameter | length of the generator’s seed ⓘ |
| successProbabilityBound | prediction advantage over 1/2 must be negligible ⓘ |
| testOutcome | sequence is pseudorandom if all efficient predictors fail with only negligible advantage ⓘ |
| typicalContext | construction and analysis of pseudorandom generators from one-way functions ⓘ |
| usedIn |
foundations of modern cryptography
ⓘ
security proofs for pseudorandom generators ⓘ |
| usedToDefine |
computational pseudorandomness
ⓘ
secure pseudorandom generators ⓘ |
| yearProposed | 1982 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.