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

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.

Available format(s)
Publication info
Published elsewhere. STOC 2024
Contact author(s)
jo496 @ cam ac uk
2024-03-22: approved
2024-03-19: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.