schnorr_soundness_affine_related_keys
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 secret witness and pk₁ = g^(w₁.val). Let α, β in ZMod q define a related witness w₂ = α * w₁ + β with public key pk₂ = g^(w₂.val). Suppose an identical commitment a in G is used in two transcripts (a, c₁, s₁) and (a, c₂, s₂) that satisfy Schnorr.Verify for pk₁ and pk₂ respectively. If c₁ ≠ α * c₂, then (s₁ - s₂ + β * c₂) / (c₁ - α * c₂) = w₁ in ZMod q.
Statement
theorem schnorr_soundness_affine_related_keys {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G) (hg : orderOf g = q) (w₁ α β : ZMod q) (a : G) (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₁ - α * c₂) = w₁
- Related work
- Goldreich, Foundations of Cryptography, vol. 1, Sec. 4.4
- Verified
- 20 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$, given:
- an element $g \in G$ such that the order of $g$ in $G$ is $q$ (orderOf g = q),
- elements $w_1, \alpha, \beta \in \mathbb{Z}/q\mathbb{Z}$,
- a group element $a \in G$,
- elements $c_1, c_2, s_1, s_2 \in \mathbb{Z}/q\mathbb{Z}$,
assuming that:
1. $c_1 \neq \alpha \cdot c_2$ in $\mathbb{Z}/q\mathbb{Z}$,
2. Schnorr.Verify g (g ^ w₁.val) a c₁ s₁ holds, and
3. Schnorr.Verify g (g ^ (α * w₁ + β).val) a c₂ s₂ holds,
then in the field $\mathbb{Z}/q\mathbb{Z}$:
$$(s_1 - s_2 + \beta \cdot c_2) / (c_1 - \alpha \cdot c_2) = w_1$$
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 extracts the primary secret witness w₁ from two Schnorr transcripts sharing the same commitment a across affine-related keys w₂ = α * w₁ + β. Cross-multiplying the two verification equations eliminates the shared commitment a, yielding an equality between powers of the generator g. Because g has order q, this implies a linear congruence on the exponents modulo q, which translates to a linear equation over ZMod q; since c₁ ≠ α * c₂, the coefficient of w₁ is invertible, directly giving the explicit witness extraction formula.
Cross-multiplying the verification equations eliminates the commitment a, giving g ^ s₁.val * (g ^ (α * w₁ + β).val) ^ c₂.val = g ^ s₂.val * (g ^ w₁.val) ^ c₁.val.
Unfolding the definition of Schnorr.Verify reveals that g ^ s₁.val = a * pk₁ ^ c₁.val and g ^ s₂.val = a * pk₂ ^ c₂.val. Substituting these into both sides, the commitment a cancels because multiplication in the commutative group G satisfies (a * x) * y = (a * y) * x (mul_right_comm).
uses
mul_right_commsimp only [Schnorr.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]
The exponents satisfy s₁.val + (α * w₁ + β).val * c₂.val ≡ s₂.val + w₁.val * c₁.val [MOD q].
Applying exponent rules for products (pow_add) and powers (pow_mul) combines both sides into single powers of g. Because g has order q (hg), equality of powers g ^ m = g ^ n is equivalent to congruence of the exponents 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_eq_pow_iff_modEq, hg] at key1
In ZMod q, s₁ + (α * w₁ + β) * c₂ = s₂ + w₁ * c₁.
Modular equivalence of natural numbers modulo q is equivalent to equality of their canonical projections in ZMod q (ZMod.natCast_eq_natCast_iff). Projecting both sides into ZMod q yields the identity in the ring ZMod q.
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, s₁ - s₂ + β * c₂ = w₁ * (c₁ - α * c₂).
Expanding the product (α * w₁ + β) * c₂ = α * w₁ * c₂ + β * c₂ and rearranging terms groups all terms containing the secret witness w₁ on the right-hand side as w₁ * (c₁ - α * c₂).
have hsub : s₁ - s₂ + β * c₂ = w₁ * (c₁ - α * c₂) := by linear_combination hZ
(s₁ - s₂ + β * c₂) / (c₁ - α * c₂) = w₁ in ZMod q.
Since c₁ ≠ α * c₂ (hne), the difference c₁ - α * c₂ is nonzero (sub_ne_zero.mpr). In the field ZMod q, dividing both sides by this nonzero factor (div_eq_iff) isolates the witness w₁.
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
mul_right_comm- In a commutative semigroup, (a * b) * c = (a * c) * b.
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, powers x ^ n and x ^ m are equal if and only if n ≡ m modulo the order of x.
ZMod.natCast_eq_natCast_iff- Two natural numbers have equal images in ZMod c if and only if they are congruent modulo c.
sub_ne_zero.mpr- If a ≠ b, then a - b ≠ 0.
div_eq_iff- For b ≠ 0 in a group with zero (such as a field), a / b = c is equivalent to a = c * b.
- In Lean, group exponentiation takes natural number exponents (.val), requiring an explicit bridge (ZMod.natCast_eq_natCast_iff) between modular equivalence over ℕ and equality in the ring ZMod q, whereas on paper exponents are treated directly as elements of ℤ/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 the Schnorr protocol with affine-related keys: nonce reuse across related keys extracts the primary witness. -/theorem schnorr_soundness_affine_related_keys {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G) (hg : orderOf g = q) (w₁ α β : ZMod q) (a : G) (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₁ - α * c₂) = w₁ := by simp only [Schnorr.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₂ + β * c₂ = 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