Encodings of assignments with prefix :
ProvedLatticePrepro.QuadraticVerifier.enc_assignOfcoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be a quadratic verifier over ( prime) with input coordinates and assignment coordinates, let be a field that is an -algebra, and let be an encoding tuple in . For an instance and values in on the auxiliary coordinates, let . Then
where is the instance encoding.
In the soundness proof of Theorem 4.6, this identity shows that the encodings of assignments over with prefix form the coset , where ; summing the translation identity over this coset produces an accepting computation on .
Formalization Note: Instances are Fin n → Bool with bits stored as , the auxiliary values are a function on AuxIdx (the coordinates with ), and the last sum runs over AuxIdx.
Preamble
import Mathlib
import Definitions.Def_LatticePrepro_Verifier_Quadratic
open LatticePrepro
open LatticePrepro.QuadraticVerifier
variable {p : ℕ} [Fact p.Prime] {K : Type} [Field K] [Algebra (ZMod p) K]
(V : QuadraticVerifier p) (ε : EncodingTuple p K V.S)Formal statement
theorem LatticePrepro.QuadraticVerifier.enc_assignOf (x : Fin V.n → Bool) (u : V.AuxIdx → ZMod p) :
ε.enc (V.assignOf x u) = V.instanceEnc ε x + ∑ i : V.AuxIdx, u i • ε.E i.1 := by sorrySource
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), auxiliary lemma used in the soundness proof of Theorem 4.6 (\label{thm:fixed-verifier-reduction}); Lean: LatticePrepro/Verifier/Quadratic.lean, LatticePrepro.QuadraticVerifier.enc_assignOf