73 Cryptography — Schnorr Protocol
73.1 Overview
This module formalises the Schnorr identification protocol over an arbitrary commutative group \(G\) with a generator \(g\) of prime order \(q\). It establishes the three core security properties: completeness (honest transcripts always pass verification), special soundness (two accepting transcripts with distinct challenges yield a witness extractor), and honest-verifier zero knowledge (simulator transcripts equal honest transcripts up to a bijective reindexing of the randomness).
73.2 Declarations
A Schnorr transcript is a triple \((a, c, s) \in G \times \mathbb {Z}_q \times \mathbb {Z}_q\), where \(a\) is the prover’s commitment (an element of the group \(G\)), \(c \in \mathbb {Z}_q\) is the verifier’s challenge, and \(s \in \mathbb {Z}_q\) is the prover’s response.
Given randomness \(r \in \mathbb {Z}_q\) and a generator \(g \in G\), the commitment is \(a := g^{r}\), where the exponent is taken via the canonical lift \(r.\mathrm{val} \in \mathbb {N}\).
Given witness \(w\), randomness \(r\), and challenge \(c\) in \(\mathbb {Z}_q\), the response is \(s := r + c \cdot w \in \mathbb {Z}_q\).
The verifier accepts a transcript \((a, c, s)\) with respect to public key \(\mathit{pk} \in G\) when \(g^s = a \cdot \mathit{pk}^{c}\), where the exponents are taken via the canonical lifts to \(\mathbb {N}\).
The honest prover’s full transcript for witness \(w\), randomness \(r\), and challenge \(c\) is the triple \((\mathrm{commit}(g, r),\; c,\; \mathrm{respond}(w, r, c))\), i.e. \((g^r,\, c,\, r + c \cdot w)\).
The zero-knowledge simulator, given public key \(\mathit{pk}\), challenge \(c\), and a fresh response \(s\), outputs the transcript \((g^s \cdot (\mathit{pk}^c)^{-1},\; c,\; s)\). The commitment is chosen so that the transcript is accepting without using the witness.
Given two challenges \(c_1, c_2\) and corresponding responses \(s_1, s_2\) in \(\mathbb {Z}_q\), the extractor returns
Let \(g \in G\) be an element of order \(q\) and let \(w, r, c \in \mathbb {Z}_q\). Then the honest transcript \((g^r, c, r + c \cdot w)\) satisfies the verifier equation with respect to the public key \(\mathit{pk} = g^w\):
Let \(g \in G\) have order \(q\), and let \(a \in G\), \(c_1 \neq c_2 \in \mathbb {Z}_q\), \(s_1, s_2 \in \mathbb {Z}_q\) be such that both transcripts \((a, c_1, s_1)\) and \((a, c_2, s_2)\) satisfy \(\mathrm{Verify}\) with respect to public key \(\mathit{pk} = g^w\). Then the extractor recovers the witness:
For fixed \(w, c \in \mathbb {Z}_q\), define the bijection \(\sigma _{w,c} : \mathbb {Z}_q \xrightarrow {\; \sim \; } \mathbb {Z}_q\) by \(r \mapsto r + c \cdot w\), with inverse \(s \mapsto s - c \cdot w\).
Let \(g \in G\) have order \(q\) and let \(w, c \in \mathbb {Z}_q\). The honest transcript map \(r \mapsto \mathrm{honest}(g, w, r, c)\) and the simulator map \(r \mapsto \mathrm{simulate}(g,\, g^w,\, c,\, \sigma _{w,c}(r))\) are equal as functions \(\mathbb {Z}_q \to \mathrm{Transcript}(G, q)\), where \(\sigma _{w,c} = \mathrm{reindex}(w, c)\) is the bijective shift \(r \mapsto r + c \cdot w\).