A Zero-Knowledge PCP Theorem
summary
Claims a constructive method that achieves polynomial-size proofs for every NP language whose verifier makes constant-query verification while leaking nothing even to adversaries that probe up to Q(n) positions (Q can be any polynomial, even exponential B with proof length polynomial in n and B). Uses Reed‑Muller-style encodings, a zero-knowledge LTC, randomized masking, sumcheck with variable‑order reversal and low‑degree extensions; produces nonadaptive PCPs (and an NEXP variant) with perfect zero‑knowledge and provable soundness, and the constructions succeed as stated.
AI-written summary · about
chapters (14)
- 0:00Zero-knowledge PCPs intro
- 1:13What is a PCP
- 3:21Zero-knowledge PCPs defined
- 8:24Prior work on ZK-PCPs
- 11:42Our construction
- 13:04Why should you care about zero-knowledge PCPs
- 19:03Building ZK-PCPs from scratch
- 22:55Zero-knowledge LTCs
- 31:27Constructing the zero-knowledge LTC
- 39:38Zero-knowledge PCPP & sumcheck
- 41:06Sumcheck in zero-knowledge
- 55:44Multivariate sumcheck
- 1:01:15Results & future work
- 1:02:58Q&A
related talks
01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristic
01h 06mLattice-based Zero-knowledge Proofs
33mAn Introduction to Zero Knowledge Proofs
26mPCPs and Instance Compression from a Cryptographic Lens
28mZero Knowledge Proofs and Their Future Applications
23mZKBoo: Faster Zero-Knowledge for Boolean Circuits
48mProving UNSAT in Zero Knowledge
49mLattice-Based Zero Knowledge and Applications