Construction A lattices and reduction modulo (Lemma B.1)
DefinitionLatticePrepro_Conversions_ConstructionA_Extcoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Fix a prime and a coordinate set .
- Reduction modulo (
redMod): the -linear map that reduces every coordinate modulo . - Construction A (
constructionA): for a linear code , the lattice
The bundle also contains two rewriting lemmas: the coordinates of the reduction (redMod_apply), and that the canonical lift of a word (with entries in , liftZMod) reduces to (redMod_liftZMod).
This is the lattice of Lemma B.1, used in the lattice reduction of Lemma 3.12.
Formalization Note. constructionA C is a Submodule ℤ (M → ℤ), defined as the preimage of , regarded as an additive subgroup, under reduction modulo .
Definition code
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Conversions_ConstructionA
/-! Further definitions from `LatticePrepro/Conversions/ConstructionA.lean`, continuing `Def_LatticePrepro_Conversions_ConstructionA`. -/
namespace LatticePrepro
open Finset
variable {p : ℕ} [Fact p.Prime] {M : Type*}
/-- Coordinatewise reduction modulo `p` as a `ℤ`-linear map. -/
def redMod (p : ℕ) (M : Type*) : (M → ℤ) →ₗ[ℤ] (M → ZMod p) :=
LinearMap.pi fun i => (Int.castAddHom (ZMod p)).toIntLinearMap ∘ₗ LinearMap.proj i
@[simp] lemma redMod_apply (v : M → ℤ) (i : M) : redMod p M v i = (v i : ZMod p) := rfl
/-- The Construction A lattice `Λ_𝒞 = {v : v mod p ∈ 𝒞}`. -/
def constructionA (C : Submodule (ZMod p) (M → ZMod p)) : Submodule ℤ (M → ℤ) :=
(C.restrictScalars ℤ).comap (redMod p M)
@[simp] lemma redMod_liftZMod (y : M → ZMod p) : redMod p M (liftZMod y) = y := by
funext i
simp [liftZMod]
end LatticePrepro
Source
G. Fenzi, G. Weissenberg, Nearly Optimal Hardness for CVP and NCP with Preprocessing (STOC 2027 submission #847; IACR ePrint 2026/2634, https://eprint.iacr.org/2026/2634), Lemma B.1 (\label{lem:construction-a-gap}) in Appendix B.2 (\label{subsec:conversion-proof}); Lean: LatticePrepro/Conversions/ConstructionA.lean, LatticePrepro.redMod, LatticePrepro.constructionA