schnorr_soundness_correlated_commitments
Special soundness of the Schnorr protocol with affine-correlated commitments: let G be a commutative group, q a prime, and g in G an element of order q. Let w in ZMod q be a witness and pk = g^(w.val) the public key. If two transcripts (a₁, c₁, s₁) and (a₂, c₂, s₂) with distinct challenges c₁ ≠ c₂ both satisfy Schnorr.Verify g (g^(w.val)) a₁ c₁ s₁ and Schnorr.Verify g (g^(w.val)) a₂ c₂ s₂, and the commitments satisfy a₂ = a₁ * g^(Δ.val) for an offset Δ in ZMod q, then (s₁ - s₂ + Δ) / (c₁ - c₂) = w in ZMod q.
Statement
theorem schnorr_soundness_correlated_commitments {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G) (hg : orderOf g = q) (w : ZMod q) (a₁ a₂ : G) (Δ : ZMod q) (ha : a₂ = a₁ * g ^ Δ.val) (c₁ c₂ s₁ s₂ : ZMod q) (hne : c₁ ≠ c₂) (h₁ : Schnorr.Verify g (g ^ w.val) a₁ c₁ s₁) (h₂ : Schnorr.Verify g (g ^ w.val) a₂ c₂ s₂) : (s₁ - s₂ + Δ) / (c₁ - c₂) = w
- Formalizes
- Ryan (2009), 'Hardware Faults and Schnorr Signatures'; Bellare & Neven (2006)
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
Read back from the Lean
For any commutative group G and any prime number q (with [Fact q.Prime]), given:
- an element g : G such that the order of g is q (orderOf g = q),
- a element w : ZMod q,
- elements a₁, a₂ : G,
- an element Δ : ZMod q satisfying a₂ = a₁ * g ^ Δ.val,
- elements c₁, c₂, s₁, s₂ : ZMod q with c₁ ≠ c₂,
- a proof h₁ that Schnorr.Verify g (g ^ w.val) a₁ c₁ s₁ holds, and
- a proof h₂ that Schnorr.Verify g (g ^ w.val) a₂ c₂ s₂ holds,
the theorem concludes that (s₁ - s₂ + Δ) / (c₁ - c₂) = w in ZMod q.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof combines the two verification equations and the affine relation between the commitments into a single group identity equating two powers of g. Because g has prime order q, this equality reduces to a congruence modulo q on the exponents, which translates to a linear equation in the field ZMod q. Since the challenges are distinct, their difference is invertible, allowing us to solve directly for the witness w.
The verification hypotheses h₁ and h₂ are expanded into group equations.
Unfolding the definition Schnorr.Verify rewrites h₁ to g ^ s₁.val = a₁ * (g ^ w.val) ^ c₁.val and h₂ to g ^ s₂.val = a₂ * (g ^ w.val) ^ c₂.val.
uses
Schnorr.Verifysimp only [Schnorr.Verify] at h₁ h₂
In the commutative group G, the identity g ^ s₁.val * g ^ Δ.val * (g ^ w.val) ^ c₂.val = g ^ s₂.val * (g ^ w.val) ^ c₁.val holds.
Substituting the verification equations h₁ and h₂ along with the correlation a₂ = a₁ * g ^ Δ.val expresses both sides in terms of a₁, g ^ Δ.val, (g ^ w.val) ^ c₁.val, and (g ^ w.val) ^ c₂.val. Commutativity of multiplication in G (`group`) completes the equality.
have key1 : g ^ s₁.val * g ^ Δ.val * (g ^ w.val) ^ c₂.val = g ^ s₂.val * (g ^ w.val) ^ c₁.val := by rw [h₁, h₂, ha] group
The exponents satisfy s₁.val + Δ.val + w.val * c₂.val ≡ s₂.val + w.val * c₁.val [MOD q].
Combining powers of g using pow_mul and pow_add writes both sides as single powers of g. Since g has order q (hg), two powers of g are equal if and only if their exponents are congruent modulo q (pow_eq_pow_iff_modEq).
uses
pow_mul,pow_add,pow_eq_pow_iff_modEqrw [← pow_mul, ← pow_mul, ← pow_add, ← pow_add, ← pow_add, pow_eq_pow_iff_modEq, hg] at key1
In ZMod q, the relation s₁ + Δ + w * c₂ = s₂ + w * c₁ holds.
Via ZMod.natCast_eq_natCast_iff, the modular congruence between natural numbers lifts to an equality between their casts in ZMod q, and the cast distributes over addition and multiplication.
uses
ZMod.natCast_eq_natCast_iffhave hZ : s₁ + Δ + w * c₂ = s₂ + w * c₁ := by simpa using (ZMod.natCast_eq_natCast_iff _ _ q).mpr key1
In ZMod q, rearranging gives s₁ - s₂ + Δ = w * (c₁ - c₂).
Subtracting s₂ and w * c₂ from both sides of the previous equation and factoring w yields the linear relation.
have hsub : s₁ - s₂ + Δ = w * (c₁ - c₂) := by linear_combination hZ
(s₁ - s₂ + Δ) / (c₁ - c₂) = w in ZMod q.
Since c₁ ≠ c₂, their difference c₁ - c₂ is nonzero (sub_ne_zero.mpr). In the field ZMod q, dividing by a nonzero denominator is equivalent to the corresponding multiplication (div_eq_iff), which matches the relation established in the previous step.
uses
sub_ne_zero.mpr,div_eq_iffhave hc_ne : c₁ - c₂ ≠ 0 := sub_ne_zero.mpr hne rw [div_eq_iff hc_ne] exact hsub
Schnorr.Verify- The Schnorr verification relation: Schnorr.Verify g pk a c s asserts g ^ s.val = a * pk ^ c.val.
pow_mul- In a monoid, a ^ (m * n) = (a ^ m) ^ n.
pow_add- In a monoid, a ^ (m + n) = a ^ m * a ^ n.
pow_eq_pow_iff_modEq- In a left-cancellative monoid, x ^ n = x ^ m if and only if n and m are congruent modulo the order of x.
ZMod.natCast_eq_natCast_iff- For natural numbers a and b, their natural casts in ZMod c are equal if and only if a ≡ b [MOD c].
sub_ne_zero.mpr- If a ≠ b, then a - b ≠ 0.
div_eq_iff- In a group with zero (such as a field), if b ≠ 0, then a / b = c if and only if a = c * b.
- In Lean, elements of ZMod q and their canonical natural-number representatives (.val) are distinct types, so the proof explicitly moves from group exponentiation with natural numbers to modular congruence in ℕ, and then casts back to ring equality in ZMod q.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- Special soundness of Schnorr identification under affine-correlated commitments. -/theorem schnorr_soundness_correlated_commitments {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G) (hg : orderOf g = q) (w : ZMod q) (a₁ a₂ : G) (Δ : ZMod q) (ha : a₂ = a₁ * g ^ Δ.val) (c₁ c₂ s₁ s₂ : ZMod q) (hne : c₁ ≠ c₂) (h₁ : Schnorr.Verify g (g ^ w.val) a₁ c₁ s₁) (h₂ : Schnorr.Verify g (g ^ w.val) a₂ c₂ s₂) : (s₁ - s₂ + Δ) / (c₁ - c₂) = w := by simp only [Schnorr.Verify] at h₁ h₂ have key1 : g ^ s₁.val * g ^ Δ.val * (g ^ w.val) ^ c₂.val = g ^ s₂.val * (g ^ w.val) ^ c₁.val := by rw [h₁, h₂, ha] group rw [← pow_mul, ← pow_mul, ← pow_add, ← 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 [div_eq_iff hc_ne] exact hsub