Aether Catalog definitions — Cryptography_LWE_SelfReductionAndSmudging
DefinitionCryptography_LWE_SelfReductionAndSmudgingaether-catalogcryptography
Definition bundle for the Aether Catalog module Cryptography.LWE.SelfReductionAndSmudging, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Cryptography/LWE/SelfReductionAndSmudging.lean by skeleton subtraction
import Mathlib
import Definitions.Def_Cryptography_LWE_SearchDecisionCore
/-
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
namespace LWEReduction
/-! ## Section 1: Noise smudging -/
/-- The uniform probability mass on a finite set of integers (here indexed by
`ℕ`, i.e. a window of consecutive noise values). -/
def unifMass (S : Finset ℕ) (x : ℕ) : ℝ := if x ∈ S then 1 / (S.card : ℝ) else 0
/-! ## Section 2: Random self-reducibility of the LWE secret -/
variable {n q : ℕ}
/-- An LWE sample value `b = ⟨a, s⟩ + e`. -/
def lweSample (a s : Fin n → ZMod q) (e : ZMod q) : ZMod q := a ⬝ᵥ s + e
/-! ## Section 3: Exact regularity of the inner product `⟨a, s⟩` -/
/-- The inner product with a fixed secret, as a group homomorphism. -/
def dotHom {p n : ℕ} (s : Fin n → ZMod p) : (Fin n → ZMod p) →+ ZMod p where
toFun a := a ⬝ᵥ s
map_zero' := by simp
map_add' a b := by simp [add_dotProduct]
/-! ### Arbitrary modulus: the ideal criterion -/
/-! ### The prime-modulus case, as a corollary -/
end LWEReduction
end
/-! ## Axiom verification -/