PaperlayerView exact revision on arXiv

Source-linked AI summary

Zero Knowledge for Free up to Linear Query Bounds: Quasilinear-Size Constant-Query Zero-Knowledge PCPs

Inhyuk Park, Chenglin Fan

arXiv:2610.29066v1cs.CC

TL;DR

The paper tackles whether constant-query zero-knowledge PCPs can have quasilinear length even for polynomial query bounds. It masks the Reed–Solomon proof of proximity throughout its recursion and uses a locator lemma to control input leakage. The resulting PCPs have length (T + b) · polylog(T + b), with very large constants and qualified simulator running-time guarantees.

  • Problem

    The short ZK-PCP question asks whether binary constant-query PCPs for NTIME(T) can have length ˜O(T + b) for every polynomial query bound b.

    Source: §1.1 · p. 4

  • Method

    The construction masks the Reed–Solomon proof of proximity at every recursion node and uses a locator lemma to bound each view’s input leakage by O(1) input reads per proof symbol.

    Source: §2.4 · p. 12

  • Results

    For quasilinear T, the paper gives binary constant-query PCPs of length (n + q*) · polylog(n + q*) that answer Open Problem 1 of [GOS25] for every polynomial query bound.

    Source: §1.1 · p. 4, §1.2 · p. 6

  • Takeaways & Limitations

    For b ≤ T, the resulting length is T · polylog T, the form of the shortest known constant-query PCPs without zero knowledge.

    Source: §1.1 · p. 4

    The query count and polylogarithmic exponent are absolute but very large, and strict polynomial-time perfect simulation on fair coins without a failure symbol is unavailable for this construction.

    Source: §1.5 · p. 9, §4.10 · p. 32

Abstract

from arXiv · show

We show that for all polynomials $T$ and $b$, every relation in NTIME($T$) has a binary PCP with $O(1)$ non-adaptive queries, perfect completeness, soundness error 1/2 and length $(T+b)\cdot(\log(T+b))^{O(1)}$, which is perfect zero knowledge against every adaptive, possibly malicious verifier making at most $b$ queries. This improves the length $\tilde O(T+b^2)$ of Zeilberger, O'Connor, Gur and Spooner (2026), who observed that Dinur's gap amplification preserves zero knowledge. The simulator runs in expected polynomial time (or in strict polynomial time, with a failure symbol or with negligible statistical error). For $b\le T$ the length is $T\cdot\mathrm{polylog}\,T$, the form of the shortest known constant-query PCPs without zero knowledge. Unless NP $\subseteq$ BPP, the dependence on $b$ is optimal up to the polylogarithmic factor for polynomial-time simulators: zero knowledge is free up to linear query bounds. Zero-knowledge interactive oracle proofs achieved length $\tilde O(T+b)$ in 2016-17; we obtain it for PCPs. Gur, O'Connor and Spooner (STOC 2025) asked whether NP has such PCPs of quasilinear length (their Open Problem 1). This paper answers it for every polynomial query bound, with the simulators above in place of a strict polynomial-time perfect simulator. The proofs were developed with extensive AI assistance and have been checked by the authors. We mask the Reed-Solomon proof of proximity of Ben-Sasson and Sudan at every node of its recursion. By a locator lemma, at every node, whatever $k$ of its proof symbols reveal about its input is determined by $O(k)$ input values. We prove it with the coprime-order argument of Bafna and Vyas (2026); our treatment of domain points is new. Dinur's gap amplification gives constant query complexity. The query count and the polylogarithmic exponent are absolute but very large.

1 Introduction

The paper addresses whether constant-query zero-knowledge PCPs can have quasilinear length for polynomial query bounds. It answers yes using per-node masking and a locator lemma, while noting very large constants and limits on strict-time perfect simulation.

1.1 Short zero-knowledge PCPs

  • The strong reading of the short ZK-PCP question asks for binary constant-query PCPs of length ˜O(T + b) against every polynomial query bound, with b additive to the input-time parameter T.For b ≤ T, the target length matches the T · polylog T form of shortest known constant-query PCPs without zero knowledge.Source: §1.1 · p. 4

1.3 Comparison with previous work

  • Compared with prior PCPs of length ˜O(T + b²), this construction has additive dependence on b; unlike the interactive results [BCGV16, BCFGRS17], it removes interaction.The construction uses a binary alphabet, constant queries, and an efficient simulator in contrast to the private-PCP guarantee described for.Source: §1.1 · p. 4, §1.3 · pp. 7–8

1.2 Our results

  • For every polynomial query bound b, the main theorem gives binary constant-query PCPs for NTIME(T) with perfect completeness, soundness error at most 1/2, and length (T + b) · polylog(T + b).The simulator gives identical views for adaptive, possibly malicious verifiers; it is perfect in expected polynomial time, with strict-time alternatives involving a failure symbol or negligible statistical error.Source: §1.2 · p. 5
  • At each recursion node, the locator lemma bounds what a set of proof symbols reveals about the input by evaluations on at most a constant-factor more domain points.The bound composes across recursion levels into a lazy sampler with polylogarithmic input reads per query.Source: §1.2 · pp. 6–7

1.4 Why new ideas were needed

  • The method masks the Reed–Solomon proof of proximity at every recursion node, making each node’s leak depend on only O(1) input reads per symbol read.The paper contrasts this with prior point-charged simulation analyses that require Θ(√s) input reads per symbol on balanced splits, while noting these are not lower bounds for zero-knowledge PCPs.Source: §1.4 · p. 8

1.5 Limitations and open questions

  • The query count and polylogarithmic exponent are absolute but very large, and strict polynomial-time perfect simulation on fair coins without a failure symbol is unavailable for this construction.The paper also leaves open extending the theorem to superpolynomial query bounds and reducing the constants.Source: §1.5 · p. 9

2 Technical overview

The proof combines a masked Reed–Solomon proximity construction with a locator lemma that bounds how many input values a proof view can reveal, then uses local gap amplification to obtain constant-query PCPs. The resulting sampler preserves perfect zero knowledge while the proof length remains quasilinear in the input and query bound, up to polylogarithmic factors.

2 Technical overview

  • The construction has three layers: an outer reduction to Reed–Solomon proximity, a masked recursive PCPP with a lazy sampler, and zero-knowledge-preserving gap amplification.Only the masked PCPP layer is new in substance; the outer method follows in the PCP form of, and amplification formalizes an observation of.Source: §2 · p. 10

2.1 The shell: from NTIME(T) to masked Reed–Solomon proximity

  • The shell arithmetizes a Cook–Levin formula and randomizes a satisfying-table interpolant as w0 = A0 + ZH·R before checking Reed–Solomon proximity and an identity at a random point.The randomization makes w0 t-wise independent on the evaluation domain; the proof also includes w1 and PCPPs for w0 and w1/ZH.Source: §2.1 · p. 10

2.2 The RS PCPP, masked at every node

  • At each recursive node, the verifier masks its input g with a fresh uniform Reed–Solomon codeword r and proves consistency of y = g + r and their lifts.Children use fresh independent masks, and the bivariate test supplies soundness at each level.Source: §2.2 · pp. 10–11

2.3 Leaks and locators

  • A locator maps any set of proof symbols to a monotone, polynomial-time computable set of at most a constant-factor more input points that determines the view’s dependence on the input.The leak is the span of the linear functionals shared by the y-side and r-side symbols; the locator theorem bounds it using input evaluations.Source: §2.3 · p. 11

2.4 From node locators to a lazy sampler

  • Composing node locators bottom-up yields a dependence set of size at most (ln s)^(log2 a)|S|, so the lazy sampler makes at most κ̄k input reads after k queries.The sampler reads only newly required input points, then samples masks consistently with earlier answers; the dependence property gives exactness.Source: §2.4 · pp. 11–12

2.5 Proof idea for the locator lemma

  • The locator proof uses one low-bidegree curve through a small view and shows that non-row, non-column factors violate an incidence bound, leaving only heavy rows to charge.The domain-point treatment is new: it limits columns to read abscissae and adjusts the zero count to the view’s domain points.Source: §2.5 · p. 12

2.6 From polylogarithmic queries to a constant

  • Dinur’s local gap amplification converts the polylog-query shell into a binary PCP with O(1) queries while reducing the zero-knowledge query bound only by polylogarithmic locality.Each output bit depends on polylogarithmically many original proof symbols, enabling the local-computability lemma to transfer zero knowledge.Source: §2.6 · p. 13

2.7 Parameters

  • The final length is at most c_len(T + b)(ln(T + b))^C, with absolute constants, and the simulator is perfect in expected polynomial time or strict-time with failure or negligible statistical error.The final verifier uses three independent tests; fair-coin test selection costs at most a factor of two in rejection probability.Source: §2.7 · p. 13

3 Definitions

This section fixes the paper’s PCP and zero-knowledge conventions, compares them with [GOS25], and establishes a lower bound on proof length when the query bound is large. It also records how local computation transfers zero knowledge between proofs.

3.1 Notation

  • The paper’s notation fixes Reed–Solomon evaluation codes, evaluation functionals, time-constructible bounds, and NTIME(T) relations, while warning that symbols such as n and b vary by section.All logarithms are base 2 unless written ln.Source: §3.1 · p. 13

3.2 PCPs

  • A PCP has perfect completeness when every honest proof is accepted with probability 1, and soundness error ε when every proof for a no-instance is accepted with probability at most ε.The section also defines length, query complexity, randomness, and non-adaptive verification through a multiset of tests.Source: §3.2 · p. 14

3.3 Views and zero knowledge

  • Black-box perfect zero knowledge requires one universal simulator, without witness access, to reproduce the verifier’s view exactly for every bounded verifier and yes-instance.The verifier may be adaptive and malicious; the simulator may be straight-line, and the query bound counts distinct queries.Source: §3.3 · p. 14
  • The section also states that simulator running time counts verifier calls and the verifier’s coins, with the coin cost additive in the view length.The simulator’s time is polynomial whenever the verifier tosses polynomially many coins.Source: §3.3 · p. 14

3.4 Comparison with the definitions of [GOS25]

  • The theorem’s simulator is perfect in expected polynomial time, or strict polynomial time with a failure symbol or negligible statistical error, rather than strict-time perfect without failure.For this construction, strict-time perfect simulation on fair coins without failure is impossible when the honest proof has a non-constant bit.Source: §3.3 · p. 15, §3.4 · p. 15

3.5 The query bound cannot exceed the length

  • If a polynomial-time PCP has length ℓ(n) ≤ b(n) eventually and is perfect-complete, soundness-1/2, and black-box perfect zero knowledge with a polynomial-time simulator, then its language is in BPP.The same implication holds for 1/10-statistical zero knowledge with a strict-time simulator; hence for NP-complete relations ℓ(n) > b(n) infinitely often unless NP ⊆ BPP.Source: §3.5 · p. 16

3.6 Local computability

  • A proof obtained by computing each symbol from at most L symbols of a zero-knowledge proof remains zero knowledge against query bound ⌊b/L⌋, provided the map is witness-independent and defined on every proof string.The paper uses a cache-and-cap version to keep the simulator exact and straight-line.Source: §3.6 · p. 16

4 The construction and the main theorem

This section develops the construction and dependencies of the main theorem, including a locator for proof views at recursion nodes, an outer-shell PCP, and zero-knowledge-preserving gap amplification. Together these components yield constant-query binary PCPs with quasilinear length and perfect zero knowledge for polynomially many adaptive queries, with the stated simulator tradeoffs and large constants.

4.1 Roadmap and credits

  • The construction’s new contributions include its overall assembly, domain family, canonical coset choices, same-radix recursion, and domain-point refinement of the locator lemma.The authors also identify explicit parameters and show that every recursion node and every view met in the recursion satisfies the locator lemma’s hypotheses.Source: §4.1 · p. 17

4.2 Conventions

  • The PCP conventions define soundness through rejection probability and encode each field symbol in λq bits, mapping invalid bit blocks to zero before soundness is evaluated.The verifier is a multiset of tests, and query complexity is the maximum number of proof positions in a test.Source: §4.2 · p. 17

Zero knowledge.

  • Black-box perfect zero knowledge requires one universal simulator to reproduce the verifier’s view exactly for every valid witness and every adaptive, malicious verifier within the query bound.The section distinguishes expected polynomial time, strict polynomial time with a failure symbol, strict exact simulation, and strict simulation with statistical error.Source: Zero knowledge · p. 18

4.3 The domain family and the field rule

  • The construction selects n with N ≤ n < 2N and a complete binary pairing tree whose internal coprime factors have equal prime counts and ratio below 2, and defines a domain of size 8n.Source: §4.3 · pp. 19–20

4.4 Nodes, the canonical rule and the recursion

  • Every recursion node satisfies the locator-lemma hypotheses with parameters (L1, L2, K) = (14, 8, 2), using the same-radix configuration for its input and mask lifts.The canonical rule selects fourteen coset representatives outside the node’s eight domain cosets and is total on recursion nodes.Source: §4.4 · pp. 20, 22

4.5 The locator lemma at recursion nodes

  • For the recursion-node parameters, c* = 10^-13 is shown admissible for the locator lemma’s conditions.The passage begins bounding the resulting constant a(c*) but does not state the locator lemma’s conclusion here.Source: §4.5 · p. 22
  • At every recursion node, each proof view has a monotone, position-only locator of size at most a* times the view size, computable in poly(q) time.The locator’s input dependence is determined by values on its selected input positions.Source: §4.5 · p. 23, §4.7 · p. 25

4.6 The RS PCPP in the same-radix configuration

  • The same-radix RS PCPP has perfect completeness and rejection probability at least ϱh times the input’s distance from RS[D, m], where ϱh = 2660^-h.Its proof length is bounded by s(ln s)^log2 30, doubled at the root when u < n; tests read at most 16(ln s)^6 symbols.Source: §4.6 · p. 24

4.7 Zero knowledge of the PCPP

  • The RS PCPP admits an oracle-robust, exact lazy sampler, yielding a non-adaptive verifier with at most 16(ln s)^6 queries and perfect completeness.Theorem 4.26 also gives rejection probability at least (3/8)·2660^-d times the input’s distance from RS[Ĥ, u], and a sampler query-read bound of (ln s)^log2 a*.Source: §4.7 · p. 26

4.8 The outer shell

  • The outer-shell construction reduces NTIME instances to a multiplicative randomisable algebraic CSP whose code-distance parameter is at least 63/64.For proximity to C0 × C1, the PCPP has at most 16(ln ℓ)^6 queries, perfect completeness, and rejection probability at least the input distance divided by 8·2660^d.Source: §4.8 · pp. 27–28
  • The outer-shell PCP has perfect completeness, gap at least 21/(2048(η+1)·2660^d), and black-box perfect zero knowledge against adaptive malicious verifiers making ⌊t/(ηκ̄′)⌋ distinct symbol queries.It uses non-adaptive qA = max(16(ln ℓ)^6, η+1) queries and has a universal straight-line PPTF simulator.Source: §4.8 · p. 29

4.9 Zero-knowledge-preserving gap amplification (statement as used)

  • The asymptotic bounds have very large constants: the analysis gives EL ≥ 3.958·10^13 and QD ≥ 10^13, and the theorem is a feasibility statement rather than a claim of concrete efficiency.The query bound 16(ln s)^6 and every polylogarithmic factor are polylogarithmic only asymptotically.Source: §4.9 · p. 29, §4.10 · p. 33
  • The gap-amplification theorem produces a binary PCP with QD = 6⌈1/αD⌉ non-adaptive queries while preserving perfect completeness and black-box zero knowledge, reducing the query bound from b0 to ⌊b0/LD⌋.Its length is at most 27(4s0+1)|U|CD(3(4s0+1)/γ)^EC; deterministic x-only post-processing of the old proof uses at most q0 cit(3(4s0+1)/γ)^EL symbols.Source: §4.9 · p. 30

4.10 The main theorem

  • For every R in NTIME(T), the main theorem gives a binary PCP with 18⌈1/αD⌉ non-adaptive queries, perfect completeness, soundness at most 27/64, and length O((T+b)(ln(T+b))^C).It is perfectly zero knowledge against adaptive malicious verifiers making at most b bit queries, with a universal straight-line simulator exact in expected polynomial time; strict polynomial time is available with a failure symbol or negligible statistical error.Source: §4.10 · pp. 30–31
  • The theorem answers Gur, O’Connor and Spooner’s Open Problem 1 for every polynomial query bound, but does not provide their strict-polynomial-time perfect simulator on fair coins without a failure symbol.The stated alternatives are exact simulation in expected polynomial time, strict polynomial time with a failure symbol, or negligible-error statistical zero knowledge with a strict polynomial-time simulator.Source: §4.10 · p. 32

5 The locator lemma

This section proves that every view at a same-radix node has a monotone, efficiently computable locator of linear size, building small-view locators from circuit structure. It combines incidence bounds and divisibility arguments, including a refinement for domain columns, and records the scope of row localization.

5.1 Setting and statement

  • Every view has a monotone locator computable in polynomial time from its positions, of size at most a constant times the view.The locator lemma applies to every view, without a size threshold.Source: §5.1 · p. 34

5.2 Rows, tensor form and leaks

  • The tensor form represents each read as v(x) ⊗ w(b), while dependencies characterize the leak as supported combinations of view-point evaluations.Rows are cheap because the evaluations across each fibre form a basis, connecting row structure to input dependence.Source: §5.2 · pp. 35–36

5.3 The incidence input

  • For a mixed curve of bidegree (a, b′), Γ_A×B(F) is bounded by L1L2(3 · 2^(2/3)m^(1/3)(ab′)^(2/3) + 12ab′).The bound follows by combining a coset-pair incidence estimate with the decomposition of A×B into L1L2 coset pairs.Source: §5.3 · pp. 36–37

5.4 The divisibility lemma with domain columns

Then E | P. Condition (4) holds for every mixed F whenever

5.5 Row localisation and the proof of the locator lemma

  • Every dependency can be decomposed so its relevant rows lie in H_t(V), yielding a locator from the corresponding fibres.This row-localization result applies when the view has disjoint sides, no input reads, and satisfies the stated bounds on t and |V|.Source: §5.5 · p. 39
  • The one-polynomial argument gives threshold n + 1 − t directly as an alternative to the closure route [DLV24] [KP25]; m1 > m2 nodes are outside its claim and absent from the recursion.A no-leak construction for a set of n + n′ points is superseded by Theorem 5.26.Source: §5.5 · p. 39

5.6 A small-view locator

  • Every circuit of size at most a + b + 2 + E∗ is a row, column, hook, or Möbius-graph circuit, and each listed type is a circuit.The classification underlies the small-view locator criterion.Source: §5.6 · p. 40
  • On every node, W1 locates views touching at most n′ rows or having at most n + n′ − 1 reads, and also certain views satisfying (LP) without enough Möbius incidences.The additional condition is r(V) ≤ n′ − 2, the stated point-count bound (LP), and no Möbius graph containing n + n′ − r points of Pts′′(V).Source: §5.6 · p. 41
  • Every Möbius graph contains at most n + 1 + L1L2M(m) points of (A × B) ∪ {x̂ : x ∈ D}, where M(m) = max(3·2^(2/3)m^(1/3), 12m/p).For sufficiently large m with n′ < 2n, this bound supports W1 locating views with at most N0 = n + ⌊3n′/2⌋ − 1 reads, as well as specified views satisfying (LP).Source: §5.6 · p. 41
  • W♮ is a monotone, position-only, polynomial-time locator for every view, with size at most a(c)|V| and a sharper bound for sufficiently small views.It is contained in W ∪ W1; that union is also a monotone locator of size at most (a(c) + 1)|V|.Source: §5.6 · p. 42

6 Zero-knowledge-preserving gap amplification

This section develops Dinur-style gap amplification that preserves zero knowledge, using a canonical tester and Tseitin front end with locality and information guarantees. Under stated conditions on an input PCP, the resulting encoding yields binary PCPs of quasilinear length in T+b and constant non-adaptive query complexity.

6.1 Definitions

  • The definitions formalize coin-multiset PCP tests, verifier views, bounded-query black-box zero knowledge, and efficient local maps, which provide the framework for the theorem's locality guarantees.A local map's output at each location depends only on a specified subset of input proof positions.Source: §6.1 · p. 43

6.2 The instantiation: Dinur’s tester with canonical folding

  • Canonical folding bijects assignments on L′can(ψ) with folded strings, and the resulting Σ0 assignment tester has rejection probability ε = cT/24.The canonical choice also gives |L′can(ψ)| = 2|SAT(ψ)|−1.Source: §6.2 · pp. 44–45

6.3 The statement

  • Theorem 6.10 produces a binary, non-adaptive PCP with 6m queries, soundness error at most 1/2, and length at most 27m*|U|C^k.Here m = ⌈1/α_D⌉, k = ⌈log2(3m*/γ̂)⌉, and γ̂ = max{γ, 1/|U|}.Source: §6.3 · p. 47
  • With a black-box perfect (or ε-statistical) zero-knowledge input and query bound b, amplification preserves that guarantee for bound ⌊b/L_D⌋ and inherits straight-line simulation.The simulator is also exact (or ε-close) when the union of queried local-map supports has at most b elements; the theorem's non-adaptive-only variant guarantees only non-adaptive zero knowledge.Source: §6.3 · p. 47
  • The amplification map preserves information exactly: its output depends only on input proof bits B(x), which are recoverable from that output.Thus the mapped proof is non-constant on the prover's support exactly when the input proof restricted to B(x) is non-constant.Source: §6.3 · p. 47

6.4.1 The Tseitin front end

  • The Tseitin front end builds a constraint graph with 3m*|U| edges and a q-local honest map; it is complete and has unsatisfiability at least γ̂/(3m*) on no-instances.Each test's gate clauses, output clause, and padded tautologies are represented by clause vertices and incident constraints.Source: §6.4.1 · p. 48

6.4.2 One round and its honest map

  • A gap-amplification round applies preprocessing, t-th powering, and composition with Pcan, using blocks of Boolean variables and fresh tester vertices for each powered-graph edge.The powered graph's labels assign values to Γ(u), whose size is at most d⌈t/2⌉.Source: §6.4.2 · p. 48
  • The one-round map deterministically sends every satisfying labelling to a satisfying amplified labelling, with each output label depending on at most c_it old labels.It also lets the original label at any vertex on an edge be recovered from first coordinates of amplified labels, making the witness transformation local rather than existential.Source: §6.4.2 · p. 49

6.4.3 Iteration and parameters

  • Iterating the round map and encoding labels as three bits gives a binary PCP whose verifier samples edges and has soundness error below 1/2.The proof establishes perfect completeness; the verifier accepts only if all sampled edge constraints hold.Source: §6.4.3 · p. 49

6.4.4 Zero knowledge

  • A deterministic, efficient, x-only local transformation preserves black-box zero knowledge, with a universal simulator and the same simulator class under polynomial query bounds.The result covers perfect or ε-statistical zero knowledge; if the original simulator is straight-line, the transformed simulator is straight-line as well.Source: §6.4.4 · pp. 50–51

6.5 When an input PCP suffices

  • Under the stated input-PCP conditions, every R in NTIME(T) has a binary PCP of length O((T+b)(log(T+b))^(e1+2e2(1+EC+EL))) with at most QD non-adaptive queries and soundness at most 1/2.It has perfect completeness and perfect (or ε-statistical) zero knowledge against adaptive b-bounded verifiers; the input PCP requires a non-adaptive honest verifier, polylogarithmic residual circuits, and adaptive zero knowledge for query bound B.Source: §6.5 · pp. 51–52

6.6 Remarks

  • The repaired Dinur analysis yields very large absolute parameter lower bounds, and the known gap in extending amplification to assignment testers does not affect PCPs.The remarks identify the assignment-tester gap in [Din07, §9] and state that the theorem uses other sections of Dinur’s work.Source: §6.6 · p. 52

7 Related work and credits

The section situates the construction among zero-knowledge PCPs, short PCPs, and related algebraic work. It distinguishes prior guarantees and identifies which ingredients are borrowed, re-proved, or new.

Zero-knowledge PCPs

  • Earlier zero-knowledge PCP work spans constant-soundness constructions, polynomially small soundness, and perfect zero knowledge with an efficient simulator [GOS25].The closest preceding quasilinear-length PCP has length ˜O(T+b²).Source: §7 · p. 53

Product expansion

  • Bafna and Vyas give private PCPs with quasilinear length over a polynomial-size alphabet and O(kN^1/k) queries, under stated product-expansion conditions.Their separate perfect-zero-knowledge PCP guarantee is for satisfying assignments and has no efficient simulator.Source: §7 · p. 53

Zero knowledge in interactive models

  • Quasilinear-size zero knowledge was achieved for interactive oracle proofs by Ben-Sasson et al., while related work develops succinct-constraint detection and simulator composition.Zero-knowledge sumcheck and sumcheck commitment are due to [CFS17] and [CFGS22].Source: §7 · p. 53

Short PCPs

  • Ben-Sasson and Sudan’s Reed–Solomon PCPP with Dinur’s gap amplification gives constant queries and length TpolylogT.Anshu et al. give a separate NP PCP construction with polylogarithmic queries, but it is not zero knowledge [ABGNV26].Source: §7 · p. 53

Product expansion

  • The locator-lemma proof follows the divisibility-argument structure of Bafna and Vyas, but re-proves the needed steps using and.The section uses because the nodes allow m < p and use subgroups of different orders, unlike bounds cited for smaller subgroups of the same order [KMSV17] [KSV22] [MV19].Source: §7 · p. 54

Credits

  • Table 2 lists every ingredient not originating in this paper and where it is used; re-proved results are marked as such and are not claimed as new.The authors identify the overall assembly, domain family, canonical cosets, same-radix recursion configuration, locator-lemma applications, and domain-point treatment as new [p05].Source: §7 · p. 54, Table 2 · p. 54

A Parameters and constants

The appendix collects construction parameters and details the length bookkeeping. It also records a locator-constant refinement and comments on the size of constants.

A Parameters and constants

  • Section A.1 lists construction parameters, while Section A.2 gives detailed length bookkeeping for Theorem 4.34.Section A.3 records a locator-constant reduction that is not used elsewhere; Section A.4 discusses constant sizes.Source: A Parameters and constants · p. 56
  • Neither Proposition A.1 nor Section A.3 changes the form of the main theorem.The locator-constant reduction in Section A.3 is not used elsewhere.Source: A Parameters and constants · p. 56
  • The appendix’s parameter and constant details support the construction without changing the stated theorem form.Section A.2 expands the length bookkeeping of Theorem 4.34.Source: A Parameters and constants · p. 56

A.1 The parameter table

The parameter table records the final PCP’s zero-knowledge guarantee and length alongside explicit construction parameters. Its constants are absolute but very large.

Shell PCP parameters

  • The root shell PCP uses domain size ℓ = 8n, while its query count is bounded by max(16(ln ℓ)^6, η+1).The table gives recursion depth d ≤ log2 ln ℓ and residual-circuit exponent 14.Source: §A.1 · pp. 56–57

Final PCP

  • The final verifier’s non-adaptive query count is 18⌈1/αD⌉, with the table also listing a lower bound of 3·10^13.The query-count expression appears with the final-PCP parameters.Source: §A.1 · p. 57
  • The final PCP is perfectly zero knowledge against adaptive malicious verifiers making at most b distinct bit queries.Its zero-knowledge guarantee is stated as running in expected polynomial time.Source: §A.1 · p. 57
  • The theorem’s simulator is universal and straight-line, and the stated completeness and soundness entries include a bound of 27/64 for three runs.The table lists the simulator and three-run bound separately.Source: §A.1 · p. 57
  • The final PCP length is at most N(log2 N)^(Cexact+1), and this bound holds for every N ≥ Nthr under the stated threshold condition.Source: §A.1 · p. 57

Locator parameters

  • The locator lemma uses a = a* ≥ a(c*) with c* = 10^-13, and the table reports log2 a* between 87.3701 and 87.3702.A separate refinement reports log2 ã between 49.9600 and 49.9601 [p58].Source: §A.1 · pp. 57–58

A.2 The length exponent

The appendix derives the length exponent by tracking shell-PCP parameters, gap amplification, and the fixed-point choice. It gives an explicit exponent and notes that the locator constant contributes additively.

A.2 The length exponent

  • The final length is at most c′len(T+b)(ln(T+b))^Cexact(ln ln(T+b))^(2EL), with Cexact = 27 + log2 80 + log2 a + (15 + log2 2660)(EC + EL).For sufficiently large T+b, it is also at most (T+b)(log2(T+b))^Cexact+1.Source: §A.2 · p. 58
  • The locator constant enters the length exponent only additively, through log2 a.The T-term’s exponent is smaller than the b-term’s exponent by 5 + log2 a + eEL.Source: §A.2 · pp. 58–59
  • The shell PCP has query count bounded by (ln ℓ)^6 and residual-circuit size bounded by (ln ℓ)^14, while its inverse gap is bounded by (ln ℓ)^(1+log2 2660).These shell quantities do not depend on the locator constant; the locator lemma enters through the sampler’s read factor and zero-knowledge parameter.Source: §A.2 · p. 58
  • Gap amplification contributes e = 15 + log2 2660 to the logarithmic exponent through the residual-circuit and inverse-gap bounds.Theorem 6.10 supplies the amplification step [p85].Source: §A.2 · p. 58
  • The fixed-point choice uses an explicit computable envelope for the parameter function, with t selected from b and that function.The derivation sets Y0 = max(Npts,b,|x|) and relates ln ℓ to ln Y0 above the stated threshold.Source: §A.2 · p. 59
  • The appendix states that the exponent’s constants are extremely large and that the threshold Nthr is likewise very large.It says the cited lower bounds on amplification parameters reflect the analysis of with repairs, not limits of gap amplification.Source: §A.2 · p. 59

A.3 A further reduction of the locator constant

The appendix tightens the locator constant through a refined divisibility argument, then explains the scale and origin of the construction’s large constants. It also clarifies that the appendix’s simulation bounds are not lower bounds for zero-knowledge PCPs themselves.

A.3 A further reduction of the locator constant

  • The proof extends divisibility to degrees t ≤ cn by bounding incidences for binomial and non-binomial factors, preserving the induction and locator size bound.For non-binomial factors, the incidence estimate uses [CZ13, Theorem 2]; the resulting size bound includes the coset branch cost K/c^2.Source: §A.3 · pp. 60–61
  • The revised locator constant lowers log2 a by 37.41 bits, but the resulting bound remains far from 2/2660 and applies only at enormous sizes.The non-trivial regime still starts at m1 ≥ 2.34 · 10^7 and m ≥ 5 · 10^14.Source: §A.3 · pp. 60–61

A.4 How to read the constants

  • Both constructions inherit very large polylogarithmic exponents from Dinur’s constant-query gap-amplification step; the claimed improvement is linear rather than quadratic dependence on b.The paper says neither result is a practical construction and leaves lowering the exponents to future work.Source: §A.4 · pp. 61–62

B Necessity of the hypotheses

  • The appendix studies point-charging bounds for fixed views of masked lifts; its examples are not lower bounds for zero-knowledge PCPs or evidence that a composed PCP fails zero knowledge.The locator lemma itself uses no additional design-law hypothesis restricting incidences between grid symbols and low-degree curves.Source: B Necessity of the hypotheses · p. 62

B.1 Charges, samplers and basic lemmas

This section formalizes how a view of a masked linear proof leaks input functionals, and how those leaks translate into input reads for simulation. It develops charge and locator tools, sampler bounds, and certificates for lower-bounding charge size.

B.1 Charges, samplers and basic lemmas

  • A valid charge spans every input functional determining a view, while a locator assigns each view a monotone, efficiently computable valid charge of size at most a constant times the view size.A straight-line simulator for a fixed view is an exact point-reading sampler; bounds here do not cover samplers querying other functionals such as Hermite jets.Source: §B.1 · pp. 62–63
  • For a masked linear proof, the view’s input-dependent law is determined by the intersection of the function spaces read from the masked input and mask.Each functional in that intersection is a fixed linear function of the view, and those functional values suffice to sample the view exactly by Gaussian elimination.Source: §B.1 · p. 63
  • Every exact sampler must query functionals spanning any input value fixed by its output; consequently, a lower bound on valid-charge size lower-bounds its input reads.For statistical samplers on uniform finite-field inputs, the probability that the queried set fails to span the determined functional is at most 2ε.Source: §B.1 · p. 63
  • Views of size below u/a′ can use a small valid charge, while larger views can be charged by the whole domain, yielding a locator with constant max(a, a′|D|/u).Any u distinct domain points form a valid charge for every view.Source: §B.1 · p. 63
  • A charge spanning evaluations for a functional h must contain at least LC(h) points; repeated recurrence roots or roots outside D force at least u + 1 − LC(h) points.The criterion uses the characteristic polynomial of h’s shortest linear recurrence.Source: §B.1 · p. 64

B.2 The square-root threshold

  • The appendix identifies a square-root threshold for locally simulatable sheaf codes and shows that some same-radix views have global leaks still paid for by the locator.The Reed–Solomon PZK-PCPP of is √n-local with zero-knowledge query bound √n/8−2, yielding length ˜O(T + b^2).Source: §B.2 · p. 64

B.3 A single lift is not enough

A single lift can expose a tangent-related input functional whose point-reading charge is as large as the input dimension. The result depends on the view layout and does not establish privacy or leakage of a Shamir-type secret.

B.3 A single lift is not enough

  • A row-and-column view of one lift fixes the evaluations on a fibre and a tangent functional, forcing every exact point-reading sampler to read at least u input points.The read-to-view ratio is at least u/(DX + DY), which is Ω(√s) on balanced splits.Source: §B.3 · p. 64
  • The standard layout GY = φ(D) supplies the readable row needed for the tangent-leak argument; the complementary layout requires determining n1 off-fibre row values, which is unresolved.The argument is characteristic-free because φ′(x0) ≠ 0 when the roots of φ − b are simple.Source: §B.3 · p. 65
  • The exhibited functionals are Hermite conditions on the fibre, so the theorem neither exhibits a Shamir-type secret C(0) leak nor decides whether the joint views are private.It establishes a cost for point-charged simulation of a grid-plus-curve view.Source: §B.3 · p. 65
  • A virtual column outside D can fix its evaluation evx0 from DY column reads, while every valid charge restricted to D still needs at least u points.The lower bound follows because the evaluations at W ∪ {x0} are independent when |W| ≤ u − 1.Source: §B.3 · p. 65

B.4 Two masked lifts must not share a column

The section analyzes leakage when two masked lifts share columns, distinguishing shared off-domain columns from shared in-domain columns. Such views can fix input evaluations or derivatives that require large point charges.

B.4 Two masked lifts must not share a column

  • The two-lift framework also considers unequal radices, and the stated results require no characteristic, coprimality, or divisibility hypothesis.The main theorem’s same-radix configuration is the special case k1 = k2.Source: §B.4 · pp. 65–66
  • If two lifts share an off-domain column, enough reads from each lift fix its input evaluation, forcing every valid charge to contain at least u domain points.The required reads are ⌈u/k1⌉ and ⌈u/k2⌉, with ratio about k1k2/(k1 + k2).Source: §B.4 · p. 65
  • A shared in-domain column with the specified row and domain reads fixes both evx0 and ∂x0, so any point set spanning the leak needs at least u points.At u = n = k1k2, the ratio is at least n/(2(k1 + k2)).Source: §B.4 · p. 65
  • Even two reads at one shared off-domain position can leak a nonzero remainder evaluation with charge n1, giving ratio n1/2.This is distinct from the shared-column result when u > n1; when u = n1, it reduces to the case with both reads on the same row.Source: §B.4 · p. 66

B.5 Degrees not divisible by the radix: the top-block family

The section identifies expensive leaks at degrees not divisible by the radix and shows why a locator bound for every degree needs divisibility conditions. Under the stated divisibility condition, the ratio bound is asymptotically sharp for split ratios above one.

Top-block leak conditions

  • A top-block view of full columns leaks a nonzero vector that every finite W spanning it must support with at least u − ρ2 + 1 points.The columns must satisfy the stated bounds on K1 and K2, including K1 + K2 ≥ ρ1 + 1.Source: §B.5 · p. 66

Scope of the family

  • At u = k1k2 − 1 for coprime unequal radices, every member has ratio at most 1.At this degree, ρi = ki − 1.Source: §B.5 · p. 66

Degrees congruent to 1

  • When u ≡ 1 modulo the radix, one full column per lift forces |W| ≥ u, with ratio about k/2 for equal radices.For transversal radices, the stated ratio at u = k1k2 + 1 is (k1k2 + 1)/(k1 + k2 + 2).Source: §B.5 · p. 66

Bad degrees

  • For every coprime transversal pair, a degree below n with neither radix dividing it yields a leak requiring |W| ≥ u*, with ratio at least kmin/(3 + 6/kmax).The construction uses two full columns from the lift with ρ = 2 and one from the other lift.Source: §B.5 · p. 67

Divisibility condition

  • A locator lemma covering every degree therefore needs a divisibility hypothesis; under k1 | u, the ratio is less than k2/(k1 + 1).The section notes that non-(DIV) degrees in [n/2, n] are often not harmless for constant-factor bounds.Source: §B.5 · p. 67

Sharpness under (DIV)

  • Under k1 | u, explicit constructions make the ratio approach any rational split ratio t/ℓ > 1, asymptotically attaining the proposition’s cap.The integer-split construction is the case ℓ = 1.Source: §B.5 · p. 67

Scope of the bound

  • For split ratios below 2, exact scans find best ratios 1.903 and 2.800 in the stated ranges, below the cap; if both radices divide u, the family is absent.The reported scan covers 220,707 cases with K < 2 and 367,845 with 2 ≤ K < 3.Source: §B.5 · p. 67

B.6 Transversal lifts with unbounded column sets

The section analyzes leaks for transversal lifts when column sets are not bounded in the same way as in the locator construction. It gives spectral lower bounds and examples showing that unrestricted or several restricted column-set families can defeat constant-ratio locators.

Aligned product leak

  • Reading one row from each lift across all rows yields an aligned product leak whose span is one-dimensional and described by a generator h.The section gives its coordinates using the row characters and states that the two spans correspond under CRT.Source: §B.6 · p. 68

Rational kernels

  • Rational kernels produce nonzero leaks from i roots per row on one lift and j per row on the other, with dim Λ(VB) ≥ ij.With at most one off-fibre read per row and lift and no domain reads, a nonzero leak is characterized by a bilinear Möbius incidence vanishing at all read points.Source: §B.6 · p. 68

Spectral lower bound

  • For a transversal grid, every W spanning fB has size at least the least cyclic gap of the nonzero spectrum E* together with 0.The proof uses a BCH-bound argument on the cyclic spectrum.Source: §B.6 · pp. 68–69

Möbius incidence cost

  • For a Möbius kernel with (β, γ) ≠ (0, 0), every W spanning fB has size at least σM = min(εlo − 1, n + 1 − 2εlo).If β = γ = 0, the two sides instead read a shared column.Source: §B.6 · p. 69

Unbounded column sets

  • With unbounded column-coset counts and no design law, coprime-radix views can require a locator ratio growing with n1, so no constant ratio suffices.The exhibited view has |V| = 2n1 + 3 and forces |W| ≥ n1(n1 + 2)/3 − 1; the result shows these two restrictions cannot both be dropped.Source: §B.6 · p. 69

Free column sets

  • Allowing arbitrary off-domain column sets also admits the Theorem B.24 view and its unbounded-ratio conclusion.The stated view reads λµn2 on one side and λ′µn1 on the other, with the two cosets chosen off D.Source: §B.6 · p. 69

Restricted column sets

  • Restrictions (ALN), (ALN2), or (HALF) do not restore a constant-ratio locator when column-coset counts are unbounded and no design law is imposed.The theorem supplies witness families for each restriction.Source: §B.6 · p. 69

Bounded designs

  • For monomial kernels on bounded designs, sufficiently large n1 makes the view inadmissible or its minimal charge smaller than |VB|.The proposition bounds the number of cosets met by each side in terms of ℓ and the radices.Source: §B.6 · p. 70

B.7 The same-radix configuration: global leaks exist, and the locator pays for them

The same-radix configuration admits global leaks, including views with no locally leaking row. The locator lemma addresses these by locating the leaks rather than requiring every view to have only local leaks.

Locator setting

  • The locator setup uses coset-union columns and fibres, and the tensor representation maps lift reads to v(a) ⊗ w(b) and domain reads to v(x) ⊗ w(xn).The construction’s locator works for arbitrary coset designs without subgroup alignment.Source: §B.7 · pp. 70, 74

Möbius circuits

  • With distinct coordinates and no domain reads, at most n + n′ − 1 lift reads are independent; at n + n′ reads, a leak occurs exactly when the points lie on a Möbius graph.In the latter case, the leak space is one-dimensional.Source: §B.7 · p. 70

Global leaks

  • A view using n abscissae on one row plus additional reads can have a one-dimensional global leak confined to one or two row fibres, although no row has a local leak.The near-saturation construction likewise confines its leak to the union of two row fibres.Source: §B.7 · p. 71

Spread-out views

  • For θ ≤ 3/4, views can leak while every row carries fewer than θn reads, with size at most (1 − θ)u + 3n′.These examples show that a claim that every sufficiently small view has only local leaks is false, but the leaks remain located.Source: §B.7 · pp. 71–72

Locator response

  • The locator of Theorem 5.3 charges these examples using domain points, heavily read row fibres, or a D-coset; every nonempty view with τ = 0 is located.The stated c* is 10^-13.Source: §B.7 · p. 72

Product expansion

  • A Möbius graph with n + n′ points obstructs ρ-product expansion above the stated threshold, connecting the incidence condition to product expansion.The section relates this condition to earlier product-expansion results and notes that the locator lemma absorbs small-node failures through its coset branch.Source: §B.7 · pp. 72–73

Free-column examples

  • On free column sets, exact computations find one-dimensional leaks with ratios 1.50, 2.00, and 2.37 in three small cases, but the authors claim no general lower bound.Moving one point off the Möbius graph kills the leak in each reported case.Source: §B.7 · p. 73

Degree-k graphs

  • Degree-k graph leaks were computed only for k ≤ 3 at small nodes; extending them generally is conjectural, while the locator lemma requires no design law.The paper states that the incidence input holds for every coset design with m < p.Source: §B.7 · p. 73

B.8 Which hypotheses are necessary

The appendix distinguishes hypotheses shown necessary from those used by the proof or tested only per instance. Its closing discussion identifies open questions about the simulation paradigm and reports extensive AI assistance with author checking.

B.8 Which hypotheses are necessary

  • The appendix classifies hypotheses as proved necessary, per-instance evidence only, proved unnecessary, or used by the proof with no negative result known.It lists costly leaks for single lifts, shared columns, certain degrees, and unbounded or free column sets.Source: §B.8 · pp. 74–75

B.9 Summary and open questions

  • The appendix’s summary places the costly-leak cases at Θ(√s) on balanced splits and says the locator handles global leaks with one polynomial through the view.Open questions include a general lower bound for free column sets and whether derivative-reading samplers face a square-root barrier.Source: §B.9 · p. 75

AI methodology

  • Claude assisted extensively with construction, proof development and checking, computations, and drafting; the authors report that they checked all proofs themselves.Source: AI methodology · p. 76
Loading 2610.29066v1…