Fiat–Shamir heuristic
E831747
The Fiat–Shamir heuristic is a cryptographic technique that transforms interactive proof systems into non-interactive ones using hash functions, widely used in digital signatures and zero-knowledge proofs.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Fiat–Shamir heuristic canonical | 2 |
| Fiat–Shamir identification scheme | 2 |
How this entity was disambiguated
This entity first appeared as the object of triple T9958212 — 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: Fiat–Shamir heuristic Context triple: [Amos Fiat, knownFor, Fiat–Shamir heuristic]
-
A.
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.
-
B.
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.
-
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.
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.
-
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: Fiat–Shamir heuristic Target entity description: The Fiat–Shamir heuristic is a cryptographic technique that transforms interactive proof systems into non-interactive ones using hash functions, widely used in digital signatures and zero-knowledge proofs.
-
A.
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.
-
B.
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.
-
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.
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.
-
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 (48)
| Predicate | Object |
|---|---|
| instanceOf |
cryptographic heuristic
ⓘ
non-interactive proof transformation technique ⓘ |
| appliedTo |
Sigma protocols
ⓘ
digital signature schemes ⓘ identification schemes ⓘ succinct non-interactive arguments of knowledge ⓘ zero-knowledge proofs ⓘ |
| basedOn |
interactive proof systems
ⓘ
public-coin identification schemes ⓘ |
| challengeGeneration | challenge = H(statement ∥ commitment ∥ auxiliary data) ⓘ |
| constructionMethod | replaces verifier’s random challenges with hash of transcript ⓘ |
| designPattern | commit–challenge–response transformed via hashing ⓘ |
| field |
cryptography
ⓘ
theoretical computer science ⓘ |
| goal |
eliminate interaction between prover and verifier
ⓘ
transform interactive proofs into non-interactive proofs ⓘ |
| influenced |
design of many modern signature schemes
ⓘ
non-interactive zero-knowledge proof systems ⓘ |
| input |
public statement
ⓘ
witness or secret ⓘ |
| introducedBy |
Adi Shamir
ⓘ
Amos Fiat ⓘ |
| limitation |
not always sound in the standard model
ⓘ
security proofs usually rely on random oracle idealization ⓘ |
| output | non-interactive proof string ⓘ |
| property |
heuristic soundness
ⓘ
non-interactive ⓘ publicly verifiable ⓘ |
| publicationVenue |
CRYPTO 1986
ⓘ
linked to:
CRYPTO conference proceedings
|
| publishedIn | “How to Prove Yourself: Practical Solutions to Identification and Signature Problems” ⓘ |
| relatedConcept |
Sigma protocol
ⓘ
linked to:
Sigma protocols
digital signature ⓘ identification protocol ⓘ interactive proof ⓘ random oracle model ⓘ zero-knowledge proof ⓘ |
| securityAssumption | hash function modeled as random oracle ⓘ |
| securityModel | random oracle model ⓘ |
| typicalHashFunction | cryptographic hash function such as SHA-2 or SHA-3 ⓘ |
| typicalUse |
constructing practical digital signatures from identification protocols
ⓘ
turning 3-move Sigma protocols into signatures ⓘ |
| usedIn |
Schnorr signature scheme
ⓘ
bulletproofs ⓘ many lattice-based signature schemes ⓘ zk-SNARK constructions ⓘ |
| uses | hash functions ⓘ |
| verificationMethod | recompute hash-based challenge and check protocol transcript ⓘ |
| yearProposed | 1986 ⓘ |
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: Fiat–Shamir heuristic Description of subject: The Fiat–Shamir heuristic is a cryptographic technique that transforms interactive proof systems into non-interactive ones using hash functions, widely used in digital signatures and zero-knowledge proofs.
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.