Abstract

A probabilistically checkable proof (PCP) is a proof which can be verified by inspecting a small (usually constant) number of symbols from the proof. PCPs are fundamental objects in complexity theory, with deep connections to hardness of approximation. Informally, we say a PCP is zero-knowledge if no polynomial time algorithm with oracle access to the proof can learn anything more than the validity of the proof. Zero-knowledge proofs have been hugely influential in both cryptography and complexity theory.

We construct a perfect zero-knowledge PCP for the #P-complete language #SAT. Our construction is the first construction of a perfect zero-knowledge PCP for a language (believed to be) outside BPP . We achieve this result unconditionally, and don’t require any cryptographic assumptions.

Our construction relies on both algebraic and combinatorial techniques, including a version of the Reed-Muller code augmented with subcube sums and the combinatorial nullstellensatz. No background in zero knowledge will be assumed for the talk. (Joint work with Tom Gur and Nicholas Spooner: https://arxiv.org/abs/2403.11941)