A probabilistically checkable proof (PCP) is a proof which can be verified by inspecting a small (usually constant) number of symbols from the proof. 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.
We construct a perfect zero-knowledge PCP for the language #P. 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 Reed-Muller codes 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)
