Schnorr.schnorr_soundness
theoremverifiedformalizationimported Lean
Special soundness of the Schnorr protocol. 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 \bbz_q$. Suppose $a \in G$, and suppose $c_1, c_2 \in \bbz_q$ are distinct challenges with responses $s_1, s_2 \in \bbz_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: \[ \frac{s_1 - s_2}{c_1 - c_2} \;=\; w \quad\text{in } \bbz_q. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {G : Type*} [CommGroup G] in variable {q : ℕ} [Fact q.Prime] in variable (g : G) in theorem Schnorr.schnorr_soundness (hg : orderOf g = q) (w : ZMod q) (a : G) (c₁ c₂ s₁ s₂ : ZMod q) (hne : c₁ ≠ c₂) (h₁ : Verify g (g ^ w.val) a c₁ s₁) (h₂ : Verify g (g ^ w.val) a c₂ s₂) : extract c₁ c₂ s₁ s₂ = w
- Formalizes
- Special soundness of the Schnorr protocol, as formalized in TCSlib (`Schnorr.schnorr_soundness`)
- Lean proof
- By Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.Schnorr.schnorr_soundness← Schnorr.schnorr_soundness (TCSlib/Cryptography/SchnorrProtocol.lean:87): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- Schnorr.VerifyThe 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…
- Schnorr.extractGiven two challenges $c_1, c_2$ and corresponding responses $s_1, s_2$ in $\mathbb{Z}_q$, the extractor returns…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {G : Type*} [CommGroup G] invariable {q : ℕ} [Fact q.Prime] invariable (g : G) in/-- **Special soundness**: given a generator `g` of order `q` and two accepting transcripts `(a, c₁, s₁)` and `(a, c₂, s₂)` for public key `pk = g^w` that share the commitment `a` but use distinct challenges `c₁ ≠ c₂`, the extractor recovers the witness: `(s₁ - s₂) / (c₁ - c₂) = w` in `ZMod q`. -/theorem Schnorr.schnorr_soundness (hg : orderOf g = q) (w : ZMod q) (a : G) (c₁ c₂ s₁ s₂ : ZMod q) (hne : c₁ ≠ c₂) (h₁ : Verify g (g ^ w.val) a c₁ s₁) (h₂ : Verify g (g ^ w.val) a c₂ s₂) : extract c₁ c₂ s₁ s₂ = w := by simp only [Verify] at h₁ h₂ have key1 : g ^ s₁.val * (g ^ w.val) ^ c₂.val = g ^ s₂.val * (g ^ w.val) ^ c₁.val := by rw [h₁, h₂, mul_right_comm] rw [← pow_mul, ← pow_mul, ← pow_add, ← pow_add, pow_eq_pow_iff_modEq, hg] at key1 have hZ : s₁ + w * c₂ = s₂ + w * c₁ := by simpa using (ZMod.natCast_eq_natCast_iff _ _ q).mpr key1 have hsub : s₁ - s₂ = w * (c₁ - c₂) := by linear_combination hZ have hc_ne : c₁ - c₂ ≠ 0 := sub_ne_zero.mpr hne rw [extract, div_eq_iff hc_ne] exact hsub