Non-Interactive Zero-Knowledge and SNARKs

Corresponds to Chapter 20. Extends Sigma protocols from simple algebraic statements (knowledge of a discrete log, a DH triple) to arbitrary properties of encrypted or committed data — e.g. proving an encrypted vote is a valid 0/1 value without decrypting it, the motivating example for a voting-protocol application. Non-interactive proof systems remove the live back-and-forth entirely, most simply by applying the Fiat-Shamir transform from sigma-protocols-and-the-fiat-shamir-transform to collapse an interactive Sigma protocol into a single message, with its own formal syntax and soundness/zero-knowledge definitions (illustrated by applying Fiat-Shamir to the Chaum-Pedersen protocol). Computational zero- knowledge generalizes further with range proofs (prove a committed value lies in a range, without revealing it) as the running example. Closes with the modern succinct-proof landscape: bulletproofs (compressing many Sigma-protocol rounds logarithmically) and SNARKs (succinct non-interactive arguments, whose proof size and verification time are essentially independent of the statement’s complexity) — and the striking general theorem that everything provable can be proved in zero knowledge.

Outline (TODO — flesh out each)

• Languages and soundness
• Proving properties on encrypted data
• A generic protocol for non-linear relations
• Non-interactive proof systems — basic syntax
• The Fiat-Shamir transform (for NIZK); example: a voting protocol
• Non-interactive soundness; non-interactive zero knowledge
• Applying Fiat-Shamir to the Chaum-Pedersen protocol
• Computational zero-knowledge; range proofs
• Bulletproofs — compressed Sigma protocols
• Succinct non-interactive zero-knowledge proofs (SNARKs)
• Fun application: everything provable can be proved in zero knowledge