70 Cryptography — Schnorr Protocol
70.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).
70.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 \(q\) be a prime, let \(G\) be a commutative group, and let \(g \in G\) be an element of order \(q\). For any witness \(w\), randomness \(r\), and challenge \(c\) in \(\mathbb {Z}_q\), the honest transcript — commitment \(a = g^{r}\), challenge \(c\), and response \(s = r + c\, w\) — is accepted by the verifier against the public key \(\mathit{pk} = g^{w}\); that is,
where each exponent is taken via the canonical lift of the corresponding element of \(\mathbb {Z}_q\) to \(\mathbb {N}\).
Special soundness. Let \(q\) be prime, let \(g\) be an element of order \(q\) in a commutative group \(G\), and take the public key \(\mathit{pk} = g^{w}\) for some witness \(w \in \mathbb {Z}_q\). Suppose \(a \in G\), and suppose \(c_1, c_2 \in \mathbb {Z}_q\) are distinct challenges with responses \(s_1, s_2 \in \mathbb {Z}_q\) such that both transcripts \((a, c_1, s_1)\) and \((a, c_2, s_2)\) are accepted by the verifier for \(\mathit{pk}\). 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\) be a commutative group, let \(q\) be prime, and let \(g \in G\) be an element of order \(q\), taken as the public generator. Fix a witness \(w \in \mathbb {Z}_q\) and a challenge \(c \in \mathbb {Z}_q\), and let \(\mathit{pk} = g^{w}\) be the associated public key. Then, as functions \(\mathbb {Z}_q \to G \times \mathbb {Z}_q \times \mathbb {Z}_q\) of the prover’s randomness \(r\), the honest transcript map \(r \mapsto \big(g^{r},\, c,\, r + c\cdot w\big)\) coincides with the simulator map fed the reindexed randomness \(\sigma _{w,c}(r) = r + c\cdot w\), namely \(r \mapsto \big(g^{\sigma _{w,c}(r)}\cdot (\mathit{pk}^{\, c})^{-1},\, c,\, \sigma _{w,c}(r)\big)\); that is, these two maps are equal.