Paper 2026/1868 Original: eprint.iacr.org/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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2026-09-12: last updated
- 2026-09-02: published
- Short URL
- https://ia.cr/2026/1868
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2026/1868,
author = {Hadas Zeilberger and Jack O'Connor and Tom Gur and Nicholas Spooner},
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}
}