For a prime modulus, a nonzero secret makes `a ↦ ⟨a, s⟩` surjective.
ProvedLWEReduction.dotHom_surjectiveaether-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 sorrySource