Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Query-oblivious PCPs with enumerable predicate families, and their accepting views (Definition 6.1)

Definition
LatticePrepro_PCP_Verifier

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

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

These definitions formalize the query-oblivious PCP verifiers used in the reduction of Section 6.

  1. Query-oblivious PCP (ObliviousPCP X). For a set XXX of instances: a finite alphabet Σ\SigmaΣ, a proof length ℓ\ellℓ, a number R\mathsf RR of random bits, a number q≥1\mathsf q\ge1q≥1 of queries, and

    • for every random string r∈{0,1}Rr\in\{0,1\}^{\mathsf R}r∈{0,1}R, a query tuple Ir=(ur,1,…,ur,q)∈[ℓ]qI_r=(u_{r,1},\dots,u_{r,\mathsf q})\in[\ell]^{\mathsf q}Ir​=(ur,1​,…,ur,q​)∈[ℓ]q;
    • for every rrr, a finite family Dr\mathcal D_rDr​ of labeled predicates Σq→{0,1}\Sigma^{\mathsf q}\to\{0,1\}Σq→{0,1}, given by a finite set of labels and an evaluation map (different labels may give the same function);
    • for every instance x∈Xx\in Xx∈X and every rrr, the label in Dr\mathcal D_rDr​ of the acceptance predicate Vx,rV_{x,r}Vx,r​.

    Neither IrI_rIr​ nor Dr\mathcal D_rDr​ depends on the instance.

  2. Acceptance (Accepts). The verifier accepts a proof π∈Σℓ\pi\in\Sigma^{\ell}π∈Σℓ on the instance xxx and the random string rrr if Vx,r(π∣Ir)=1V_{x,r}(\pi|_{I_r})=1Vx,r​(π∣Ir​​)=1, where π∣Ir=(π(ur,1),…,π(ur,q))\pi|_{I_r}=(\pi(u_{r,1}),\dots,\pi(u_{r,\mathsf q}))π∣Ir​​=(π(ur,1​),…,π(ur,q​)).

  3. Perfect completeness (PerfectlyComplete) for a language L⊆XL\subseteq XL⊆X: every x∈Lx\in Lx∈L has a proof that is accepted for every random string.

  4. Soundness error (SoundnessError) s\mathsf ss for LLL, with s\mathsf ss a real number: for every x∉Lx\notin Lx∈/L and every proof π\piπ, the number of random strings for which π\piπ is accepted is at most s⋅2R\mathsf s\cdot2^{\mathsf R}s⋅2R. That is, every proof is accepted with probability at most s\mathsf ss.

  5. Accepting views (View, Views). An accepting view for rrr is a pair (V,a)∈Dr×Σq(V,\mathbf a)\in\mathcal D_r\times\Sigma^{\mathsf q}(V,a)∈Dr​×Σq with V(a)=1V(\mathbf a)=1V(a)=1 and aj=aj′a_j=a_{j'}aj​=aj′​ whenever ur,j=ur,j′u_{r,j}=u_{r,j'}ur,j​=ur,j′​; the last condition says that a=π∣Ir\mathbf a=\pi|_{I_r}a=π∣Ir​​ for some proof π\piπ. The set of accepting views for rrr is Vr\mathcal V_rVr​, and Views is the disjoint union of the sets Vr\mathcal V_rVr​, of size m=∑r∣Vr∣\mathsf m=\sum_r|\mathcal V_r|m=∑r​∣Vr​∣. View.pred and View.ans are the two components VVV and a\mathbf aa of a view.

This is Definition 6.1 of the paper. The accepting-view code of Construction 6.2 and the reduction of Theorem 6.4 are stated for these objects.

Formalization Note. Instances form an arbitrary type XXX (the paper takes X={0,1}nX=\{0,1\}^{n}X={0,1}n), and LLL is an arbitrary subset of XXX rather than the language of a relation. Random strings are functions Fin ρ → Bool, proof locations are elements of Fin ℓ, and queries are indexed by Fin q. The Lean field names ρ and q stand for R\mathsf RR and q\mathsf qq, and the theorems call the soundness error ε. Predicates take values in Bool, and equality of predicates is equality of labels, as in the paper. The running times of the verifier and of the predicate enumerator (the parameter vt\mathsf{vt}vt) are not formalized.

Definition code
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Reduction_LinearSystem
import Definitions.Def_LatticePrepro_Conversions_Codes

/-!
# Query-oblivious PCPs (Definition 6.1)

A query-oblivious PCP verifier reads `q ≥ 1` locations of a proof `π ∈ Σ^ℓ`, chosen by a random
string `r ∈ {0,1}^ρ` alone, and applies an acceptance predicate `V_{x,r} : Σ^q → {0,1}` that may
depend on the instance `x`. For the reduction of Section 6 the predicates that can occur for a
random string `r` are listed as a family `𝒟_r` of *labeled* predicates, which does not depend on
`x`.

* `ObliviousPCP X` is this data, for instances in an arbitrary type `X` (the paper takes
  `X = {0,1}^n`). The query tuple `I_r` (`query`) and the families `𝒟_r` (`Pred`, `eval`) do not
  take the instance as an argument; the verifier (`verifier`) returns the label of `V_{x,r}`.
* `PerfectlyComplete Lang` and `SoundnessError Lang ε` are perfect completeness and soundness
  error `ε` with respect to a language `Lang ⊆ X`.
* `View r` is the set `𝒱_r` of accepting views for `r`, and `Views` is the set of all accepting
  views; `card_views_le` is the bound `m ≤ 2^ρ · K · |Σ|^q` on their number `m`.

Notation: the symbols follow the paper, except that the number of random bits is `ρ` (the
paper's `𝖱`) and the soundness error is `ε` (the paper's `𝗌`). The bound `K` on the number of
predicates per random string is the paper's `𝗸`.

The running times of the verifier and of the predicate enumerator are not formalized.
-/

namespace LatticePrepro

/-- A query-oblivious PCP verifier with enumerable predicate families (Definition 6.1), for
instances in `X`. -/
structure ObliviousPCP (X : Type) where
  /-- The alphabet `Σ`. -/
  Alphabet : Type
  [fintypeAlphabet : Fintype Alphabet]
  [decEqAlphabet : DecidableEq Alphabet]
  /-- The proof length `ℓ`. -/
  ℓ : ℕ
  /-- The number `ρ` of random bits. -/
  ρ : ℕ
  /-- The number `q` of queries. -/
  q : ℕ
  /-- The verifier makes at least one query. -/
  q_pos : 0 < q
  /-- The query tuple `I_r = (u_{r,1}, …, u_{r,q})`. It does not depend on the instance. -/
  query : (Fin ρ → Bool) → Fin q → Fin ℓ
  /-- The labels of the predicate family `𝒟_r`. It does not depend on the instance. -/
  Pred : (Fin ρ → Bool) → Type
  [fintypePred : ∀ r, Fintype (Pred r)]
  [decEqPred : ∀ r, DecidableEq (Pred r)]
  /-- The predicate `Σ^q → {0,1}` with a given label. Different labels may give the same
  function. -/
  eval : (r : Fin ρ → Bool) → Pred r → (Fin q → Alphabet) → Bool
  /-- The label in `𝒟_r` of the acceptance predicate `V_{x,r}`. -/
  verifier : X → (r : Fin ρ → Bool) → Pred r

namespace ObliviousPCP

attribute [instance] fintypeAlphabet decEqAlphabet fintypePred decEqPred

variable {X : Type} (P : ObliviousPCP X)

/-- Random strings `r ∈ {0,1}^ρ`. -/
abbrev Rand : Type := Fin P.ρ → Bool

/-- Proofs `π ∈ Σ^ℓ`. -/
abbrev Proof : Type := Fin P.ℓ → P.Alphabet

/-- The verifier accepts the proof `π` on instance `x` and random string `r`:
`V_{x,r}(π|_{I_r}) = 1`. -/
def Accepts (x : X) (r : P.Rand) (π : P.Proof) : Prop :=
  P.eval r (P.verifier x r) (fun j => π (P.query r j)) = true

instance (x : X) (r : P.Rand) (π : P.Proof) : Decidable (P.Accepts x r π) :=
  inferInstanceAs (Decidable (P.eval r (P.verifier x r) (fun j => π (P.query r j)) = true))

/-- Perfect completeness: every instance in `Lang` has a proof that is accepted for every random
string. -/
def PerfectlyComplete (Lang : Set X) : Prop :=
  ∀ x ∈ Lang, ∃ π : P.Proof, ∀ r, P.Accepts x r π

/-- Soundness error `ε`: for an instance outside `Lang`, every proof is accepted for at most an
`ε` fraction of the `2^ρ` random strings. -/
def SoundnessError (Lang : Set X) (ε : ℝ) : Prop :=
  ∀ x, x ∉ Lang → ∀ π : P.Proof,
    ((Finset.univ.filter fun r => P.Accepts x r π).card : ℝ) ≤ ε * 2 ^ P.ρ

/-- The accepting views `𝒱_r` for the random string `r`: pairs `(V, a)` of a labeled predicate
`V ∈ 𝒟_r` and an answer tuple `a ∈ Σ^q` with `V(a) = 1` and `a = π|_{I_r}` for some proof `π`,
that is, `a_j = a_{j'}` whenever `u_{r,j} = u_{r,j'}`. -/
abbrev View (r : P.Rand) : Type :=
  {p : P.Pred r × (Fin P.q → P.Alphabet) //
    P.eval r p.1 p.2 = true ∧ ∀ j j', P.query r j = P.query r j' → p.2 j = p.2 j'}

variable {P} in
/-- The labeled predicate of an accepting view. -/
def View.pred {r : P.Rand} (w : P.View r) : P.Pred r := w.1.1

variable {P} in
/-- The answer tuple of an accepting view. -/
def View.ans {r : P.Rand} (w : P.View r) : Fin P.q → P.Alphabet := w.1.2

/-- All accepting views, over all random strings. Their number is `m`. -/
abbrev Views : Type := Σ r : P.Rand, P.View r

end ObliviousPCP

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), Definition 6.1 (\label{def:query-oblivious-pcp}); Lean: LatticePrepro/PCP/Verifier.lean, LatticePrepro.ObliviousPCP, LatticePrepro.ObliviousPCP.Rand, LatticePrepro.ObliviousPCP.Proof, LatticePrepro.ObliviousPCP.Accepts, LatticePrepro.ObliviousPCP.PerfectlyComplete, LatticePrepro.ObliviousPCP.SoundnessError, LatticePrepro.ObliviousPCP.View, LatticePrepro.ObliviousPCP.View.pred, LatticePrepro.ObliviousPCP.View.ans, LatticePrepro.ObliviousPCP.Views

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