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.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Yao’s next-bit test canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T5214021 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Yao’s next-bit test Context triple: [Blum–Micali pseudorandom number generator, relatedTo, Yao’s next-bit test]
-
A.
Blum–Micali pseudorandom number generator
The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.
-
B.
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
"Modern Cryptography, Probabilistic Proofs and Pseudorandomness" is a foundational textbook that systematically develops the theoretical underpinnings of modern cryptography, focusing on probabilistic proof techniques and the theory of pseudorandomness.
-
C.
In a World of Pseudorandomness
"In a World of Pseudorandomness" is a theoretical computer science work exploring the foundations, constructions, and implications of pseudorandomness in computation and cryptography.
-
D.
Blum–Blum–Shub pseudorandom number generator
The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
-
E.
Håstad’s switching lemma
Håstad’s switching lemma is a fundamental result in computational complexity theory that provides powerful bounds on the simplification of Boolean formulas under random restrictions, with major applications in circuit lower bounds.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Yao’s next-bit test Target entity description: 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.
-
A.
Blum–Micali pseudorandom number generator
The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.
-
B.
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
"Modern Cryptography, Probabilistic Proofs and Pseudorandomness" is a foundational textbook that systematically develops the theoretical underpinnings of modern cryptography, focusing on probabilistic proof techniques and the theory of pseudorandomness.
-
C.
In a World of Pseudorandomness
"In a World of Pseudorandomness" is a theoretical computer science work exploring the foundations, constructions, and implications of pseudorandomness in computation and cryptography.
-
D.
Blum–Blum–Shub pseudorandom number generator
The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
-
E.
Håstad’s switching lemma
Håstad’s switching lemma is a fundamental result in computational complexity theory that provides powerful bounds on the simplification of Boolean formulas under random restrictions, with major applications in circuit lower bounds.
- F. None of above. chosen
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
ⓘ
linked to:
Andrew Yao
|
| 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
ⓘ
linked to:
Yao’s pseudorandom generator construction
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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Yao’s next-bit test Description of subject: 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.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.