Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

LeanProofs.Crypto.CentralSimplicity

Definition
Grade4_LeanProofs_Crypto_CentralSimplicity

by lisamegawatts · Sep 18, 2026 · Mathlib c5ea003 (Lean v4.30.0)

clifford-algebraleanproofs-grade4rosetta

Foundational definitions and structural lemmas from LeanProofs.Crypto.CentralSimplicity, required by the selected LeanProofs theorem graph.

Definition code
/-
  Central simplicity and conjugacy search security.

  ## The core security question

  The security of NA-PDE-Sig rests on conjugacy search hardness in
  Cl⁺(n,0). If the even subalgebra decomposes as A ⊕ B, conjugacy
  search splits into independent subproblems — each potentially easy.

  This file establishes the algebraic framework:

  ## Proved here (abstract ring theory, 0 sorry):

  1. **Central element splitting** (`central_elem_splits_conj`):
     If z commutes with all elements, then z·(M·X·M⁻¹) = M·(z·X)·M⁻¹.
     Conjugation respects any central decomposition.

  2. **Complementary splitting** (`one_sub_central`, `complement_splits_conj`):
     If z is central, so is (1-z). Both components are independent CS instances.

  3. **Full CS decomposition** (`cs_decomposes_via_central_idempotent`):
     A CS instance (X, M·X·M⁻¹) over an algebra with central idempotent z
     splits into two independent CS instances: one in z·A, one in (1-z)·A.

  4. **Central involution yields idempotents** (`involution_idempotent_sq`,
     `involution_idempotent_orthogonal`, `involution_idempotent_complete`):
     If Z² = 1 and Z is central, then (1+Z)/2 and (1-Z)/2 are orthogonal
     central idempotents decomposing A. (Requires char ≠ 2.)

  ## Algebraic facts (used as hypotheses in the security argument):

  **Cl⁺(5,0) ≅ Cl(0,4) ≅ M₄(F_p)** — central-simple, center = F_p.
  - Cl⁺(n+1, 0) ≅ Cl(0, n) by the standard even-subalgebra isomorphism
    (Mathlib: `CliffordAlgebra.equivEven`)
  - Cl(0, 4) has even dimension (n=4): pseudoscalar I₄ anticommutes with
    generators, so I₄ is NOT in the center of the full algebra
  - Center = F_p (scalars only), no decomposition possible
  - Security: conjugacy search is ONE monolithic problem in a 16-dim algebra

  **Cl⁺(4,0) ≅ Cl(0,3) ≅ M₂(F_p) ⊕ M₂(F_p)** — NOT central-simple.
  - Cl(0, 3) has odd dimension (n=3): pseudoscalar I₃ commutes with
    all elements, I₃ ∈ center, and I₃² = 1
  - Center = F_p[I₃] ≅ F_p × F_p (2-dimensional)
  - Idempotents (1±I₃)/2 decompose the algebra into two copies of M₂(F_p)
  - Attack: conjugacy search splits into TWO independent 4-dim problems,
    each solvable in O(log p) via Jordan normal form

  **Cl⁺(6,0) ≅ Cl(0,5)** — center = F_p[I₅] with I₅² = -1.
  - Odd dimension (n=5): I₅ commutes with all elements, I₅² = -1
  - Center = F_p[√-1], which is either F_{p²} or F_p × F_p depending on
    whether -1 is a square mod p
  - For p ≡ 3 mod 4 (includes Mersenne31): center = F_{p²}, algebra is
    central-simple over F_{p²} but NOT over F_p

  ## Dimension parity rule

  The center of Cl⁺(n+1, 0) ≅ Cl(0, n) is:
  - F_p (trivial center) when n is even  → SAFE for conjugacy search
  - F_p[I_n] (non-trivial)  when n is odd → may decompose, UNSAFE

  So Cl(5,0) (n=4, even) is secure and Cl(4,0) (n=3, odd) is broken.
  This is the algebraic reason the protocol uses Cl(5,0).
-/
import Definitions.Def_Grade4_LeanProofs_Crypto_Cl60EvenClosure
import Definitions.Def_Grade4_LeanProofs_Foundations_Cl60BasisIndependence
import Mathlib.RingTheory.SimpleRing.Matrix
import Mathlib.RingTheory.SimpleRing.Field

namespace LeanProofsGrade4P2M


noncomputable section

namespace Cl60Conj

/-! ## Section 1: Central elements split conjugation

  The fundamental algebraic fact: if z commutes with all ring elements,
  it commutes through any conjugation. This is pure ring theory — no
  Clifford algebra structure needed. -/







/-! ## Section 2: CS decomposition via central idempotent

  If z is a central idempotent (z² = z, z central, z ≠ 0, z ≠ 1), the
  algebra decomposes as zA ⊕ (1-z)A and conjugacy search decomposes
  correspondingly. Each component is an independent CS instance. -/



/-! ## Section 3: Central involution yields idempotents (abstract fact)

  If Z is a central element with Z² = 1 (a "central involution") in
  a ring of characteristic ≠ 2, then e₊ = (1+Z)/2 and e₋ = (1-Z)/2
  are orthogonal central idempotents:
  - e₊² = e₊, e₋² = e₋
  - e₊ · e₋ = 0
  - e₊ + e₋ = 1
  - e₊, e₋ are central (since Z is)

  This is the concrete mechanism for the Cl⁺(4,0) attack: the
  pseudoscalar I₄ satisfies I₄² = 1 and is central, giving the
  decomposition Cl⁺(4,0) ≅ M₂(F_p) ⊕ M₂(F_p).

  For Cl⁺(5,0): the even subalgebra has center = F_p (scalars only),
  so no such involution Z ≠ ±1 exists, and the algebra is indecomposable.

  We prove the key algebraic identity that the idempotent decomposition
  respects multiplication, which is what makes each summand a subalgebra. -/



/-! ## Section 4: Instantiation for conjBy (Cl(6,0) algebra) -/





/-! ## Section 5: Concrete center computation in Cl(6,0)

  The pseudoscalar I₆ = e₀₁ · e₂₃ · e₄₅ is central in Cl⁺(6,0)
  and squares to -1. This demonstrates the non-trivial center that
  exists for even-dimensional Clifford algebras.

  For Cl(6,0): center(Cl⁺(6,0)) ⊇ ℝ[I₆] ≅ ℂ (since I₆² = -1).
  This is the Cl(6,0) analog of the Cl(4,0) decomposition issue. -/

open Cl60Even

/-- Extract commutativity from vanishing cl6Comm. -/
 theorem comm_of_cl6Comm_zero {A B : Cl60} (h : cl6Comm A B = 0) :
    A * B = B * A := by
  unfold cl6Comm at h; exact sub_eq_zero.mp h

/-- The three bivector factors of pseudoscalar60 pairwise commute
    (disjoint index pairs {0,1}, {2,3}, {4,5}). -/
 theorem ps60_factors_commute :
    e6Prod (0 : Fin 6) 1 * e6Prod 2 3 = e6Prod 2 3 * e6Prod 0 1 ∧
    e6Prod (0 : Fin 6) 1 * e6Prod 4 5 = e6Prod 4 5 * e6Prod 0 1 ∧
    e6Prod (2 : Fin 6) 3 * e6Prod 4 5 = e6Prod 4 5 * e6Prod 2 3 := by
  exact ⟨
    comm_of_cl6Comm_zero (cl6_comm_no_shared
      (by decide) (by decide) (by decide) (by decide) (by decide) (by decide)),
    comm_of_cl6Comm_zero (cl6_comm_no_shared
      (by decide) (by decide) (by decide) (by decide) (by decide) (by decide)),
    comm_of_cl6Comm_zero (cl6_comm_no_shared
      (by decide) (by decide) (by decide) (by decide) (by decide) (by decide))⟩

/-- **I₆² = -1 in Cl(6,0).**

    The pseudoscalar squares to -1 because it is a product of three
    pairwise-commuting bivectors, each squaring to -1:
    I₆² = (e₀₁ · e₂₃ · e₄₅)² = e₀₁² · e₂₃² · e₄₅² = (-1)³ = -1.

    Compare: in Cl(4,0), I₄² = +1 (two factors), giving decomposition.
    In Cl(5,0), I₅ has odd grade and is NOT in Cl⁺(5,0). -/
theorem pseudoscalar60_sq : pseudoscalar60 * pseudoscalar60 = -1 := by
  unfold pseudoscalar60
  set A := e6Prod (0 : Fin 6) 1
  set B := e6Prod (2 : Fin 6) 3
  set C := e6Prod (4 : Fin 6) 5
  obtain ⟨hAB, hAC, hBC⟩ := ps60_factors_commute
  have hA2 : A * A = -1 := e6Prod_sq (by decide : (0 : Fin 6) ≠ 1)
  have hB2 : B * B = -1 := e6Prod_sq (by decide : (2 : Fin 6) ≠ 3)
  have hC2 : C * C = -1 := e6Prod_sq (by decide : (4 : Fin 6) ≠ 5)
  -- (ABC)² = A²B²C² because A,B,C pairwise commute.
  -- Rearrange using commutativity to group same factors.
  calc A * B * C * (A * B * C)
      -- Reassociate: all equal modulo associativity
      = A * B * (C * A) * (B * C)    := by simp only [mul_assoc]
    _ = A * B * (A * C) * (B * C)    := by rw [← hAC]
    _ = A * (B * A) * C * (B * C)    := by simp only [mul_assoc]
    _ = A * (A * B) * C * (B * C)    := by rw [← hAB]
    _ = A * A * B * C * (B * C)      := by simp only [mul_assoc]
    _ = A * A * B * (C * B) * C      := by simp only [mul_assoc]
    _ = A * A * B * (B * C) * C      := by rw [← hBC]
    _ = A * A * (B * B) * (C * C)    := by simp only [mul_assoc]
    _ = (-1) * (-1) * (-1)           := by rw [hA2, hB2, hC2]
    _ = -1                           := by norm_num









/-! ## Section 6: Keygen safety — central seeds must be rejected

  If the public seed C is central (commutes with all elements), then
  rotor conjugation fixes it: `rotorConj R C = C` for every rotor R.
  This means the public key `pk = PDE^k(rotorConj R C) = PDE^k(C)` is
  deterministic from public information — revealing NOTHING about R.

  Design constraint: keygen MUST reject any C that is central. In
  Cl⁺(6,0), the center is {a·1 + b·I₆}, so this is an explicit
  algebraic check (no scalar + pseudoscalar components).

  In Cl⁺(5,0) (center = scalars only), this check reduces to
  "C is not a scalar multiple of 1" — much easier. -/







/-! ## Section 7: The pseudoscalar is a non-trivial central element

  Together with `pseudoscalar60_sq : I₆² = -1`, the following shows
  that `center(Cl⁺(6,0)) ⊇ {a·1 + b·I₆ | a, b ∈ ℝ}` — strictly larger
  than the scalars.

  This is the algebraic fact that distinguishes Cl(6,0) from Cl(5,0):
  in Cl(5,0), there is NO analog of I₆ inside the even subalgebra,
  so the center is just the scalars. -/



/-! ## Section 8: Rotor group structure

  The set of rotors `{R : IsRotor60 R}` forms a group under multiplication
  (Spin(6)). This closure property is needed to reason about composite
  rotors in signature and key exchange protocols. -/







/-! ## Section 9: Dangerous seed characterization

  The most dangerous public seed is one that is BOTH central AND a
  fixed point of PDE. Such a seed makes the public key exactly equal
  to the seed itself — completely trivializing the scheme. -/



/-! ## Section 10: Non-abelian witness (CS hardness foundation)

  Conjugacy search hardness requires the underlying group to be
  non-abelian. If Cl⁺(6,0) were commutative, conjugacy would be
  trivial (M · C · M⁻¹ = C for all M).

  Here we provide concrete witnesses that Cl(6,0) and its even
  subalgebra are non-commutative: bivectors sharing an index do
  not commute. -/





/-! ## Section 11: Matrix algebra central-simplicity

  The security argument for Cl⁺(5,0) rests on the fact that
  Cl⁺(5,0) ≅ M_4(F_p) and M_4(F_p) is central-simple. Here we
  machine-check the latter fact using Mathlib's structure theory:
  for any field F, M_n(F) is a simple ring.

  This leaves the isomorphism Cl⁺(5,0) ≅ M_4(F_p) as the only
  remaining algebraic hypothesis — and that is standard Artin-
  Wedderburn structure theory. -/







/-! ## Section 12: Mersenne31 safety for Cl(6,0)

  The Cl(6,0) production keys at Mersenne31 are NOT structurally broken
  by the discovery that I₆ ∈ center(Cl⁺(6,0)), even though I₆ is a
  non-trivial central element.

  The reason: the Cl(4,0) attack requires a central involution Z with
  **Z² = +1**, which yields the orthogonal idempotents (1±Z)/2. In
  Cl⁺(6,0), the central element I₆ has **I₆² = -1** instead.

  Over a field where -1 is NOT a square (e.g., F_p with p ≡ 3 mod 4),
  the subalgebra F[I₆]/(I₆²+1) is a genuine quadratic field extension
  F_{p²}, NOT a product F × F. Fields have only trivial idempotents.

  Mersenne31 = 2³¹ - 1 = 2147483647, and 2147483647 ≡ 3 mod 4. So
  √-1 ∉ F_{Mersenne31}, and the Cl(6,0) keys are structurally sound.

  The migration to Cl(5,0) was correct for size/cleanliness, not
  because Cl(6,0) was broken. -/







end Cl60Conj

end


end LeanProofsGrade4P2M
Source
https://github.com/MonumentalSystems/LeanProofs/blob/b656238b73d5f0f74515f6574a1dcb4e0216129f/LeanProofs/Crypto/CentralSimplicity.lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me