The Fiat-Shamir heuristic is a cryptographic technique that transforms an interactive public-coin proof or identification protocol into a non-interactive one by replacing the verifier’s random challenges with the output of a cryptographic hash function applied to the prover’s messages. This removes the need for live interaction, allowing proofs and signatures to be generated and verified offline. It is foundational to many digital signature schemes and non-interactive zero-knowledge proofs, with security analysed in the random oracle model.
- The Fiat-Shamir heuristic converts an Interactive Proof System into a non-interactive one by deriving the verifier’s challenge from a Hash Function over the transcript, drawing on Public Key Cryptography.
- It is foundational to Digital Signature schemes and non-interactive Zero-Knowledge Proof systems.
Overview
- In an interactive sigma protocol the verifier sends random challenges; Fiat-Shamir replaces these with a hash of the commitment, making the challenge unpredictable yet reproducible without a live verifier.
- The transformation yields self-contained proofs and signatures that anyone can verify offline, at the cost of relying on the random oracle assumption for the hash.
- It generalises identification schemes into signatures and underpins succinct proof systems.
Key aspects
- Replacement of interactive challenges with hash-derived values.
- Security argued in the random oracle model.
- Conversion of sigma protocols into signatures.
- Need to bind all relevant context into the hash input to prevent forgeries.
Mechanisms
- The prover computes a commitment, hashes it (with the statement and any public context) to obtain the challenge, then produces the response, packaging all three as the proof.
Applications
- Schnorr and EdDSA-style Schnorr Signature constructions.
- Non-interactive zero-knowledge proofs and Bulletproofs.
- Blockchain identity and authentication protocols.
- Efficient proof systems over Elliptic Curve Cryptography.