Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Encodings of assignments with prefix (x,1)(x,1)(x,1): enc(z)=θx+∑i>n+1ziEi\mathrm{enc}(z) = \theta_x + \sum_{i > n+1} z_i E_ienc(z)=θx​+∑i>n+1​zi​Ei​

Proved
LatticePrepro.QuadraticVerifier.enc_assignOf

by WizardOfMenlo · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

Let VVV be a quadratic verifier over Fp\mathbb{F}_pFp​ (ppp prime) with nnn input coordinates and SSS assignment coordinates, let KKK be a field that is an Fp\mathbb{F}_pFp​-algebra, and let E=(E0=0,E1,…,ES)E = (E_0 = 0, E_1, \dots, E_S)E=(E0​=0,E1​,…,ES​) be an encoding tuple in KKK. For an instance x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n and values u=(ui)n+1<i≤Su = (u_i)_{n+1 < i \le S}u=(ui​)n+1<i≤S​ in Fp\mathbb{F}_pFp​ on the auxiliary coordinates, let z=assignOf(x,u)=(1,x1,…,xn,1,un+2,…,uS)z = \mathrm{assignOf}(x, u) = (1, x_1, \dots, x_n, 1, u_{n+2}, \dots, u_S)z=assignOf(x,u)=(1,x1​,…,xn​,1,un+2​,…,uS​). Then

enc(z)=∑i=0SziEi=θx+∑i=n+2Sui Ei,\mathrm{enc}(z) = \sum_{i=0}^{S} z_i E_i = \theta_x + \sum_{i=n+2}^{S} u_i\, E_i,enc(z)=i=0∑S​zi​Ei​=θx​+i=n+2∑S​ui​Ei​,

where θx=∑i=1nxiEi+En+1\theta_x = \sum_{i=1}^{n} x_i E_i + E_{n+1}θx​=∑i=1n​xi​Ei​+En+1​ is the instance encoding.

In the soundness proof of Theorem 4.6, this identity shows that the encodings of assignments over Fp\mathbb{F}_pFp​ with prefix (x,1)(x, 1)(x,1) form the coset θx+T\theta_x + Tθx​+T, where T=span⁡Fp{Ei:i>n+1}T = \operatorname{span}_{\mathbb{F}_p}\{E_i : i > n+1\}T=spanFp​​{Ei​:i>n+1}; summing the translation identity over this coset produces an accepting computation on xxx.

Formalization Note: Instances are Fin n → Bool with bits stored as 0/1∈Fp0/1 \in \mathbb{F}_p0/1∈Fp​, the auxiliary values uuu are a function on AuxIdx (the coordinates iii with n+1<in+1 < in+1<i), 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 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), 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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me