A Zero-Knowledge PCP Theorem

Title: A Zero-Knowledge PCP Theorem

Abstract: A probabilistically checkable proof (PCP) is a proof which can be verified by inspecting a small number of symbols from the proof. The PCP theorem states that for any language in NP, there exists a polynomial-size proof that can be verified probabilistically by reading only a constant number of bits from the proof. 

We prove a “zero-knowledge PCP theorem”. For every polynomial q*, we construct PCPs for NP of polynomial length, which require only a constant number of queries to verify, and which are perfect zero knowledge against adaptive adversaries making at most q* queries to the proof. In addition, we construct exponential-length PCPs for NEXP, which require only a constant number of queries to verify, and which are perfect zero knowledge against any polynomial-time adversary.

Based on joint work with Tom Gur and Nicholas Spooner - https://arxiv.org/abs/2411.07972.

Bio: Jack is a fourth-year PhD student at the University of Cambridge, UK, where he is advised by Tom Gur. Jack is interested in cryptography, complexity theory and coding theory, and his work during his PhD has focused primarily on zero-knowledge proof systems.