Fiat-Shamir Heuristic

Cryptography · Axiom Academy

Converting interactive proofs to non-interactive zero-knowledge proofs using hash functions 1. The Problem: Interactive Proofs Traditional cryptographic protocols like Schnorr's identification scheme require real-time interaction between a prover and verifier. The verifier sends random challenges, and the prover must respond immediately. This creates practical limitations: Both parties must be online simultaneously The proof cannot be reused or published Verification requires active participation 2. The Fiat-Shamir Transformation The brilliant insight: replace the verifier's random challenge with a cryptographic hash of the transcript so far. Instead of waiting for the verifier to send a random challenge c , the prover computes it themselves using a hash function: The hash function acts as a "random oracle" that both parties can compute independently. Since the prover cannot predict the hash output before creating the commitment, security is maintained. 3. Example: Schnorr Signature Scheme The Schnorr identification protocol demonstrates the transformation perfectly. The interactive version requires three messages, but with Fiat-Shamir, it becomes a signature scheme: Non-Interactive Schnorr Signature: Now the signature (r, s) can be verified by anyone, anytime, without interaction! 4. Non-Interactive Zero-Knowledge (NIZK) Proofs

This is the written version of the interactive lesson above. See the full Cryptography course.