University of Cambridge > > Algorithms and Complexity Seminar > Perfect Zero-Knowledge PCPs for #P

Perfect Zero-Knowledge PCPs for #P

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

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:

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

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity