Paper 2024/462

Perfect Zero-Knowledge PCPs for #P

Tom Gur, University of Cambridge
Jack O'Connor, University of Cambridge
Nicholas Spooner, University of Warwick, New York University
Abstract

We construct perfect zero-knowledge probabilistically checkable proofs (PZK-PCPs) for every language in #P. This is the first construction of a PZK-PCP for any language outside BPP. Furthermore, unlike previous constructions of (statistical) zero-knowledge PCPs, our construction simultaneously achieves non-adaptivity and zero knowledge against arbitrary (adaptive) polynomial-time malicious verifiers. Our construction consists of a novel masked sumcheck PCP, which uses the combinatorial nullstellensatz to obtain antisymmetric structure within the hypercube and randomness outside of it. To prove zero knowledge, we introduce the notion of locally simulatable encodings: randomised encodings in which every local view of the encoding can be efficiently sampled given a local view of the message. We show that the code arising from the sumcheck protocol (the Reed--Muller code augmented with subcube sums) admits a locally simulatable encoding. This reduces the algebraic problem of simulating our masked sumcheck to a combinatorial property of antisymmetric functions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. STOC 2024
Contact author(s)
jo496 @ cam ac uk
History
2024-03-22: approved
2024-03-19: received
See all versions
Short URL
https://ia.cr/2024/462
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/462,
      author = {Tom Gur and Jack O'Connor and Nicholas Spooner},
      title = {Perfect Zero-Knowledge {PCPs} for #P},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/462},
      year = {2024},
      url = {https://eprint.iacr.org/2024/462}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.