Blum–Micali pseudorandom number generator

E117703

cryptographic primitive number-theoretic algorithm pseudorandom number generator stream cipher primitive

The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (3)

Label	Occurrences
Blum-Micali pseudorandom generator	1
Blum–Micali pseudorandom number generator canonical	1
“How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits”	1

How this entity was disambiguated

This entity first appeared as the object of triple T990927 — 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: Blum–Micali pseudorandom number generator
Context triple: [Manuel Blum, notableWork, Blum–Micali pseudorandom number generator]

A. Probabilistic Encryption
Probabilistic Encryption is a cryptographic technique that uses randomness in the encryption process so that the same message encrypts to different ciphertexts, enhancing security against attackers.
B. New Directions in Cryptography
New Directions in Cryptography is a landmark 1976 paper that introduced the concepts of public-key cryptography and digital signatures, fundamentally reshaping modern cryptography and secure communications.
C. Merkle puzzles
Merkle puzzles are an early cryptographic protocol that introduced the concept of public-key exchange by allowing two parties to establish a shared secret over an insecure channel using computationally asymmetric “puzzle” problems.
D. Secrecy, Authentication, and Public Key Systems
"Secrecy, Authentication, and Public Key Systems" is Ralph Merkle's influential doctoral thesis that helped lay the foundations of modern public-key cryptography and secure communication protocols.
E. Merkle–Damgård construction
The Merkle–Damgård construction is a fundamental method for building collision-resistant cryptographic hash functions from fixed-size compression functions, used in many classic hash algorithms like MD5 and SHA-1.
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: Blum–Micali pseudorandom number generator
Target entity description: The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.

A. Probabilistic Encryption
Probabilistic Encryption is a cryptographic technique that uses randomness in the encryption process so that the same message encrypts to different ciphertexts, enhancing security against attackers.
B. New Directions in Cryptography
New Directions in Cryptography is a landmark 1976 paper that introduced the concepts of public-key cryptography and digital signatures, fundamentally reshaping modern cryptography and secure communications.
C. Merkle puzzles
Merkle puzzles are an early cryptographic protocol that introduced the concept of public-key exchange by allowing two parties to establish a shared secret over an insecure channel using computationally asymmetric “puzzle” problems.
D. Secrecy, Authentication, and Public Key Systems
"Secrecy, Authentication, and Public Key Systems" is Ralph Merkle's influential doctoral thesis that helped lay the foundations of modern public-key cryptography and secure communication protocols.
E. Merkle–Damgård construction
The Merkle–Damgård construction is a fundamental method for building collision-resistant cryptographic hash functions from fixed-size compression functions, used in many classic hash algorithms like MD5 and SHA-1.
F. None of above. chosen

Statements (45)

Predicate	Object
instanceOf	cryptographic primitive ⓘ number-theoretic algorithm ⓘ pseudorandom number generator ⓘ stream cipher primitive ⓘ
assumes	existence of one-way permutations ⓘ
basedOn	discrete logarithm problem ⓘ one-way function ⓘ
category	provably secure pseudorandom generator ⓘ
constructionType	bit-by-bit generator ⓘ
designedFor	cryptographic applications ⓘ key stream generation ⓘ
developedBy	Manuel Blum ⓘ Silvio Micali ⓘ
field	computational number theory ⓘ cryptography ⓘ theoretical computer science ⓘ
formalizedIn	complexity-theoretic framework ⓘ
hasAbbreviation	BM generator ⓘ
hasComplexity	polynomial time per output bit ⓘ
hasProperty	bitwise output ⓘ computationally indistinguishable from uniform ⓘ next-bit unpredictable ⓘ provably secure under standard assumptions ⓘ
influenced	Yao’s pseudorandom generator construction ⓘ subsequent number-theoretic PRGs ⓘ
input	secret seed ⓘ
introducedIn	“How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits” ⓘ linked to: Blum–Micali pseudorandom number generator
namedAfter	Manuel Blum ⓘ Silvio Micali ⓘ
output	pseudorandom bit sequence ⓘ pseudorandom bitstream ⓘ
publicationYear	1984 ⓘ
relatedTo	Blum–Blum–Shub pseudorandom number generator ⓘ Yao’s next-bit test ⓘ
requires	large prime modulus ⓘ primitive root modulo prime ⓘ
securityGuarantee	next-bit test implies all polynomial-time statistical tests ⓘ
securityModel	polynomial-time adversary ⓘ
securityReliesOn	hardness of computing discrete logarithms ⓘ
securityType	computational security ⓘ
seedSpace	elements of the underlying group ⓘ
typicalGroup	multiplicative group of integers modulo a large prime ⓘ
uses	cyclic group modulo a prime ⓘ generator of a multiplicative group ⓘ modular exponentiation ⓘ

How these facts were elicited

Referenced by (3)

Full triples — surface form annotated when it differs from this entity's canonical label.

Manuel Blum → notableWork → Blum–Micali pseudorandom number generator ⓘ

Blum–Micali pseudorandom number generator → introducedIn → “How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits” ⓘ

linked to: Blum–Micali pseudorandom number generator

Yao’s pseudorandom generator construction → relatedTo → Blum-Micali pseudorandom generator ⓘ