Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

For a prime modulus, a nonzero secret makes `a ↦ ⟨a, s⟩` surjective.

Proved
LWEReduction.dotHom_surjective

by raver1975 · Sep 17, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogcryptography

For a prime modulus, a nonzero secret makes a ↦ ⟨a, s⟩ surjective.

theorem LWEReduction.dotHom_surjective{p n : ℕ} [Fact (Nat.Prime p)] (s : Fin n → ZMod p) (hs : s ≠ 0) :
    Function.Surjective (dotHom s) := by sorry

Formalization Note Transplanted verbatim from the Aether Catalog source Cryptography/LWE/SelfReductionAndSmudging.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.

Preamble
-- Thm stub generated from Cryptography/LWE/SelfReductionAndSmudging.lean
import Mathlib
import Definitions.Def_Cryptography_LWE_SearchDecisionCore
import Definitions.Def_Cryptography_LWE_SelfReductionAndSmudging
/-
Copyright (c) 2025 Harmonic. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
-/

/-!
# Three Exact Ingredients of the LWE Hardness Argument

Regev's worst-case-to-average-case programme for Learning with Errors is
assembled from a small number of *exact* statistical facts.  Three of them are
proved here, each with no slack.

1. **Noise smudging (flooding).**  Adding a bounded shift `c` to noise drawn
   uniformly from a window of `N` consecutive integers moves the distribution by
   exactly `2c/N` in `ℓ¹`.  This is the mechanism by which a large noise term
   hides a small secret-dependent offset (`smudging_l1_eq`,
   `smudging_l1_le_of_ratio`).

2. **Random self-reducibility of the LWE secret.**  Shifting the secret by a
   uniformly random `t` and correcting the samples turns *any* fixed secret into
   a uniformly random one.  Consequently the success probability of the
   rerandomised solver is the *global average* over secrets, identically for
   every starting secret (`lwe_selfReduction_average`).  This is exactly the
   statement that average-case LWE (uniform secret) is as hard as LWE with an
   adversarially chosen secret.

3. **Exact regularity of `⟨a, s⟩`, for an arbitrary modulus.**  The map
   `a ↦ ⟨a, s⟩` on `ℤ_qⁿ` is surjective precisely when the coordinates of `s`
   generate the unit ideal of `ℤ_q` (`dotHom_surjective_iff_span_top`); when
   they do, `⟨a, s⟩` is *perfectly* uniform — every value has exactly `q^{n-1}`
   preimages (`dot_fiber_card_general`, `dotProduct_uniform_general`).  The
   familiar prime-modulus statement (`s ≠ 0` suffices) drops out as a corollary.
   Over a composite modulus the criterion is genuinely weaker than "some
   coordinate is a unit": `s = (2, 3)` over `ℤ₆` has no unit coordinate yet is
   regular.  This is the reason the `b` component of an LWE sample carries no
   information beyond the noise, and the uniformity engine used inside
   search-to-decision hybrids.

## Main results

* `LWEReduction.smudging_l1_eq` — `ℓ¹` distance of a shifted uniform window is
  exactly `2c/N`.
* `LWEReduction.smudging_l1_le_of_ratio` — the usable form: distance `≤ ε` once
  `2c ≤ εN`.
* `LWEReduction.lwe_shift_secret` — the sample-level secret-shift identity.
* `LWEReduction.lwe_shift_bijective` — secret shifting is a bijection of the
  sample space.
* `LWEReduction.lwe_selfReduction_average` — worst-case secret success equals
  the average-case success.
* `LWEReduction.sum_comp_addHom` — a surjective group homomorphism has
  equinumerous fibers, so pushforward sums factor.
* `LWEReduction.dot_mem_span_iff` — the achievable inner products are exactly
  the ideal generated by the coordinates of the secret.
* `LWEReduction.dotHom_surjective_iff_span_top` — the arbitrary-modulus
  regularity criterion.
* `LWEReduction.dot_fiber_card_general` / `dotProduct_uniform_general` — exact
  uniformity of `⟨a, s⟩` for an arbitrary modulus.
* `LWEReduction.dot_fiber_card_eq`, `dotProduct_uniform`,
  `dotProduct_uniform_prob` — the prime-modulus corollaries.

## References

* Regev, "On Lattices, Learning with Errors, Random Linear Codes, and
  Cryptography", STOC 2005 / JACM 2009.
* Applebaum, Cash, Peikert, Sahai, "Fast Cryptographic Primitives and
  Circular-Secure Encryption Based on Hard Learning Problems", CRYPTO 2009.
-/

open Finset BigOperators Matrix

noncomputable section

open LWEReduction

/-! ## Section 1: Noise smudging -/




/-! ## Section 2: Random self-reducibility of the LWE secret -/

variable {n q : ℕ}






/-! ## Section 3: Exact regularity of the inner product `⟨a, s⟩` -/
Formal statement
theorem LWEReduction.dotHom_surjective{p n : ℕ} [Fact (Nat.Prime p)] (s : Fin n → ZMod p) (hs : s ≠ 0) :
    Function.Surjective (dotHom s) := by sorry
Source
https://github.com/paulklemstine/Lean/blob/53c2925a02/Catalog/Cryptography/LWE/SelfReductionAndSmudging.lean#L237

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