Perfect Zero-Knowledge PCPs for #P

ePrint Report: Perfect Zero-Knowledge PCPs for #P

Tom Gur, Jack O'Connor, Nicholas Spooner

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 …

construction eprint report jack knowledge language non perfect report zero knowledge