Paper 2026/1868
Zero-Knowledge PCPs of Quasilinear Size via Locally Simulatable Sheaf Codes
Abstract
We show that for every polynomial $T,b \colon \mathbb{N} \to \mathbb{N}$, there exist an $O(1)$-query probabilistically checkable proof (PCP) for $\operatorname{NTIME}(T)$ of length $\widetilde{O}\bigl(T(n)+b(n)^2\bigr)$, which is $b(n)$-query perfect zero knowledge. This strictly improves on the polynomial-length zero-knowledge PCPs of Gur, O'Connor, and Spooner (STOC 2024; STOC 2025). Our construction builds on the PCPs of Ben-Sasson and Sudan (SICOMP 2008) and Dinur (JACM 2007). We prove the zero-knowledge property of our PCPs via the new machinery of locally simulatable sheaf codes.
Note: fixed some typos
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- zero-knowledge pcppcpsheaf code
- Contact author(s)
-
tg508 @ cam ac uk
nspooner @ cornell edu
hadas zeilberger @ yale edu - History
- 2026-09-06: revised
- 2026-09-02: received
- See all versions
- Short URL
- https://ia.cr/2026/1868
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1868,
author = {Tom Gur and Nicholas Spooner and Hadas Zeilberger},
title = {Zero-Knowledge {PCPs} of Quasilinear Size via Locally Simulatable Sheaf Codes},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1868},
year = {2026},
url = {https://eprint.iacr.org/2026/1868}
}
