AFTD Auto-Formalizing Theoretical Domains

schnorr_soundness_correlated_commitments

theoremverifiedformalization

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.

  1. 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.

    line 9

    uses Schnorr.Verify

      simp only [Schnorr.Verify] at h₁ h₂
  2. 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.

    lines 10–13

      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
  3. 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).

    lines 14–15

    uses pow_mul, pow_add, pow_eq_pow_iff_modEq

      rw [← pow_mul, ← pow_mul, ← pow_add, ← pow_add, ← pow_add,
          pow_eq_pow_iff_modEq, hg] at key1
  4. 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.

    lines 16–17

    uses ZMod.natCast_eq_natCast_iff

      have hZ : s₁ + Δ + w * c₂ = s₂ + w * c₁ := by
        simpa using (ZMod.natCast_eq_natCast_iff _ _ q).mpr key1
  5. 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.

    line 18

      have hsub : s₁ - s₂ + Δ = w * (c₁ - c₂) := by linear_combination hZ
  6. (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.

    lines 19–21

    uses sub_ne_zero.mpr, div_eq_iff

      have 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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it