Sigma Protocols and the Fiat-Shamir Transform

Corresponds to Chapter 19.4–19.12. Abstracts Schnorr’s protocol into the general Sigma protocol template (commit, challenge, respond), with two defining properties: special soundness (two accepting transcripts with the same commitment but different challenges let you extract a witness — this is what makes the protocol a genuine proof of knowledge) and special honest-verifier zero-knowledge — compare the abstract interactive-proof framework in zero-knowledge-proofs, of which Sigma protocols are the concrete, efficient, discrete-log-flavored instance used throughout deployed cryptography. Covers several worked Sigma protocols beyond Schnorr’s (for representations, for Diffie-Hellman triples, for general linear relations, for a homomorphism’s preimage, and for RSA), the Fiat-Shamir heuristic (replace the verifier’s random challenge with a hash — the general version of the Schnorr-signature trick, and the starting point for non-interactive-zero-knowledge-and-snarks), and ways to combine Sigma protocols: AND-proofs and OR-proofs (proving you know a witness for one of several statements, without revealing which), witness independence as the property OR-proofs rely on, and multi-extractability as a stronger, composition-friendly alternative to ordinary special soundness.

Outline (TODO — flesh out each)

• Sigma protocols — basic definitions
• Special soundness
• Special honest-verifier zero knowledge
• Examples: Okamoto’s protocol, Chaum-Pedersen, linear relations, preimage of a homomorphism, RSA
• Identification and signatures from Sigma protocols
• The Fiat-Shamir heuristic for signatures
• Combining Sigma protocols — AND-proofs and OR-proofs
• Witness independence and applications
• Actively secure identification protocols; Okamoto’s identification protocol
• Multi-extractability — another notion of “proof of knowledge”