Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

LeanProofs.Crypto.HardHomogeneousSpace

Definition
Grade4_LeanProofs_Crypto_HardHomogeneousSpace

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

clifford-algebraleanproofs-grade4rosetta

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

Definition code
/-
  Hard homogeneous space structure and DHKE commutativity.

  A hard homogeneous space (informal): a set X with a group G acting
  on it, such that:
  - Computing the action g·x is easy.
  - Vectorization (given x and g·x, find g) is hard.
  - Parallelization ((g·x, h·x) → (gh)·x) is hard without knowing g or h.

  When G is abelian, parallelization specialises to the Diffie-Hellman
  shared-secret identity g·(h·x) = h·(g·x), which is what this file
  formalizes algebraically. The "hardness" half of the definition is
  cryptanalytic and not formalized — see the file header comments
  in `Cl60Conjugation.lean`.

  Two key results:
  - `DHKE_commutes` : pure Cl(6,0) statement that commuting rotors
    yield the same shared secret regardless of application order.
  - `cl60HHS` : a concrete `HardHomogeneousSpace` instance whose group
    is the abelian one-parameter subgroup generated by `B0 = e6Prod 0 1`.

  Protocol constraint (worth flagging explicitly): the construction
  is secure only when both parties use the SAME generator bivector.
  Different generators (e.g. Alice with `e6Prod 0 1` and Bob with
  `e6Prod 2 3`) give rotors that may not commute, breaking the
  shared-secret identity. The `cl60HHS` instance bakes in B₀; any
  generalisation must preserve same-generator usage.
-/
import Definitions.Def_Grade4_LeanProofs_Crypto_Cl60Exponential

namespace LeanProofsGrade4P2M
namespace Cl60Conj
end Cl60Conj

namespace HardHomogeneousSpace
end HardHomogeneousSpace
end LeanProofsGrade4P2M
Source
https://github.com/MonumentalSystems/LeanProofs/blob/b656238b73d5f0f74515f6574a1dcb4e0216129f/LeanProofs/Crypto/HardHomogeneousSpace.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