Repository logo
 

Perfect Zero-Knowledge PCPs for #P

Accepted version
Peer-reviewed

Type

Conference Object

Change log

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 nullstellen- satz 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.

Description

Keywords

Journal Title

Conference Name

STOC 2024

Journal ISSN

Volume Title

Publisher

Publisher DOI

Publisher URL

Sponsorship
MRC (MR/S031545/2)
Engineering and Physical Sciences Research Council (EP/X018180/1)