Perfect Zero-Knowledge PCPs for #P

Add to your list(s) Download to your calendar using vCal

• Jack O'Connor (University of Cambridge)
• Tuesday 14 May 2024, 14:00-15:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

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)

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.