Construction 4.5 — the fixed-verifier system has at most evaluation tables
ProvedLatticePrepro.QuadraticVerifier.card_tblIdx_lecoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be a quadratic verifier (over any ) with instance length and assignment coordinates. The evaluation tables of the fixed-verifier system are indexed by
- the product indices: pairs with , together with ;
- the auxiliary indices: with .
Their number satisfies
In Construction 4.5 the paper counts evaluation tables and records the bound . The bound is used in Theorem 4.8 to choose the moment parameter so that the hypothesis of Theorem 4.6 holds. It also bounds the number of columns.
Formalization Note TblIdx is the sum type ProdIdx ⊕ AuxIdx of subtypes of and (as Fin (S + 1)), and is its Fintype.card.
Preamble
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Reduction_LinearSystem
import Definitions.Def_LatticePrepro_Moments_Basic
import Definitions.Def_LatticePrepro_Moments_Representation
import Definitions.Def_LatticePrepro_Verifier_Quadratic
import Definitions.Def_LatticePrepro_Reduction_FixedSystem
open LatticePrepro
open LatticePrepro.QuadraticVerifier
variable {p : ℕ} (V : QuadraticVerifier p)Formal statement
theorem LatticePrepro.QuadraticVerifier.card_tblIdx_le : Fintype.card V.TblIdx ≤ (V.S + 1) ^ 2 := by sorry
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), Construction 4.5 (\label{con:fixed-verifier}), bound on the number of evaluation tables; Lean: LatticePrepro/Reduction/FixedSystem.lean, LatticePrepro.QuadraticVerifier.card_tblIdx_le