Sigma protocol

A sigma protocol (-protocol) for a relation is a three-move public-coin protocol in which a prover holding sends a commitment , the verifier replies with a uniform challenge from a finite set , and the prover answers with a response ; the protocol is complete, special sound and special honest-verifier zero-knowledge — Dam10.

Definition

Let be a relation with for all , and . A -protocol for is a pair of efficient algorithms with a challenge space : on common input , sends , sends , sends , and accepts or rejects as a deterministic function of . A conversation is accepting for if accepts it, and the protocol satisfies the following — Dam10.

  • Completeness: for every , accepts with probability .
  • Special soundness: there is an efficient extractor such that for every and every two accepting conversations , for with , .
  • Special honest-verifier zero knowledge (SHVZK): there is an efficient simulator such that for every and every , the conversation with is distributed as a conversation between and whose challenge is . Statistical and computational SHVZK require the two distributions to be statistically or computationally indistinguishable instead.

Properties

  • Soundness error. For , special soundness leaves each commitment at most one challenge with an accepting response, so every prover makes accept with probability at most — standard.
  • Proof of knowledge. A -protocol is a proof of knowledge with knowledge error : an extractor with rewindable black-box access to a prover that makes accept with probability outputs a witness for in expected time — Dam10. In strict time, one rewinding yields two accepting conversations with a common commitment and distinct challenges with probability at least by the reset lemma — BP02.
  • Honest-verifier zero knowledge. SHVZK implies honest-verifier zero knowledge: sample and run — standard.
  • Parallel repetition. Running copies with independent commitments, a challenge and one response per copy is a -protocol with challenge space : two accepting conversations with distinct challenge vectors differ in some coordinate , and special soundness of copy extracts — Dam10.

OR composition

Let and be -protocols for relations and with challenge space and simulators such that for every , including , and every , with is accepting for under . For , a prover holding with samples and , sends with computed by , and answers the challenge with , where and is the response of to . The verifier checks and that is accepting for under for . The result is a -protocol for , and it is witness indistinguishable; more generally, sharing the challenge with a threshold secret-sharing scheme proves knowledge of witnesses for of statements without revealing which — CDS94.

Special soundness follows because two accepting conversations with differ in or in . With perfect SHVZK, the prover’s messages have the same distribution for either witness against every verifier, since is distributed as an honest commitment independent of — standard. FS90 define witness indistinguishability.

Examples

  • Schnorr (Schnorr identification protocol): for in a group of prime order , with , , , and checks — Sch91. The extractor outputs , and samples and sets , which is perfect SHVZK — standard.
  • Chaum–Pedersen: for and in a group of prime order , a proof that sends , receives , and answers ; checks and — CP92. Its Fiat–Shamir transform is the proof attached to EDL signatures — GJ03.
  • Guillou–Quisquater: for an RSA modulus , a prime exponent and with , the prover sends for , receives , and answers ; checks and — GQ88. Two accepting conversations give with , and gives the -th root of — standard.

Fiat–Shamir

The Fiat–Shamir transform replaces the challenge by a hash of the commitment and the message to obtain a signature scheme (ID ⇒ DS) — FS86. Used as a proof system, the challenge is a random-oracle hash of the statement and the commitment — standard. For a -protocol with negligible the result is a NIZK argument in the random-oracle model (HVZK ⇒ NIZK (Fiat–Shamir)) — standard. Unforgeability proofs for such signatures rewind the forger with the forking lemma and extract by special soundness — PS96.