Fiat-Shamir Heuristic

A cryptographic method where a prover convinces a verifier that a statement is true without revealing any information beyond the statement's validity. The Fiat-Shamir heuristic is the standard mechanism for converting interactive ZKPs into non-interactive zero-knowledge proofs (NIZKs) by replacing the verifier's random challenges with a hash function output.

• Completeness: An honest prover always convinces an honest verifier
• Soundness: A dishonest prover cannot convince a verifier of a false statement
• Zero-knowledge: The verifier learns nothing beyond the truth of the statement

A one-way mathematical algorithm that maps arbitrary input data to a fixed-size output called a digest. In the Fiat-Shamir heuristic, a cryptographic hash function like SHA-256 or Keccak-256 acts as the non-interactive replacement for the verifier's random challenge. The security of the transformation depends on modeling the hash function as a random oracle—an idealized function that returns a truly random output for each unique input.

• Pre-image resistance: Infeasible to reverse the hash
• Collision resistance: Infeasible to find two inputs with the same digest
• Avalanche effect: A single bit change radically alters the output

A cryptographic mechanism for proving the authenticity and integrity of a digital message. The Fiat-Shamir heuristic is the foundation of the Schnorr signature scheme, which transforms an interactive identification protocol into a compact, non-interactive signature. The signer computes a challenge as the hash of the message and a commitment value, then produces a response that serves as the signature.

• Key generation: Produces a private signing key and public verification key
• Signing: Uses the private key and message hash to create a signature
• Verification: Uses the public key to confirm the signature's validity

An idealized security model where a hash function is treated as a truly random function accessible to all parties via an oracle. The Fiat-Shamir heuristic's security proof relies on the random oracle model: the verifier's random challenge is replaced by querying the oracle with the protocol transcript. In practice, a concrete hash function like SHA-256 substitutes for the oracle.

• Heuristic nature: Security in the random oracle model does not guarantee security with a real hash function
• Controversy: Some cryptographers argue proofs in this model are weaker than standard-model proofs
• Practical acceptance: Widely used due to efficiency gains over standard-model alternatives

A two-phase cryptographic protocol where a sender commits to a value in the commit phase and reveals it in the reveal phase. In interactive proofs that use Fiat-Shamir, the prover first sends a commitment, then receives a challenge. The non-interactive version hashes the commitment to derive the challenge.

• Hiding: The commitment reveals nothing about the committed value
• Binding: The sender cannot change the value after committing
• Pedersen commitments: A common scheme based on discrete logarithms, often used with Fiat-Shamir transformations

A specific class of three-move interactive proof systems with a structure of commitment → challenge → response. The Fiat-Shamir heuristic directly applies to Sigma protocols, converting them into non-interactive proofs by computing the challenge as the hash of the commitment and the statement being proven.

• Special soundness: From two accepting transcripts with the same commitment but different challenges, a witness can be extracted
• Special honest-verifier zero-knowledge: A simulator can generate valid transcripts given the challenge in advance
• Applications: Used in Schnorr signatures, identity verification, and anonymous credentials