Fiat–Shamir heuristic

E831747

cryptographic heuristic non-interactive proof transformation technique

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.

Try in SPARQL Jump to: Surface forms Statements Referenced by

Observed surface forms (1)

Surface form	Occurrences
Fiat–Shamir identification scheme	2

Statements (48)

Predicate	Object
instanceOf	cryptographic heuristic ⓘ non-interactive proof transformation technique ⓘ
appliedTo	Sigma protocols NERFINISHED ⓘ 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 NERFINISHED ⓘ Amos Fiat NERFINISHED ⓘ
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 NERFINISHED ⓘ
publishedIn	“How to Prove Yourself: Practical Solutions to Identification and Signature Problems” NERFINISHED ⓘ
relatedConcept	Sigma protocol NERFINISHED ⓘ 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 NERFINISHED ⓘ bulletproofs ⓘ many lattice-based signature schemes ⓘ zk-SNARK constructions ⓘ
uses	hash functions ⓘ
verificationMethod	recompute hash-based challenge and check protocol transcript ⓘ
yearProposed	1986 ⓘ

Referenced by (4)

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

Amos Fiat → knownFor → Fiat–Shamir heuristic ⓘ

this entity surface form: Fiat–Shamir identification scheme

Amos Fiat → notableConcept → Fiat–Shamir heuristic ⓘ

this entity surface form: Fiat–Shamir identification scheme