PCPs and Instance Compression from a Cryptographic Lens
summary
Assuming subexponential LWE, the work constructs publicly verifiable constant-query succinct PCAs for every bounded-depth NP relation by combining the JKKZ SNARG (using its holographic property) with commitments that replace large oracles so the SNARG verifier runs sublinearly. From that PCA construction it derives computational instance compression (CAC) to SAT and an or-CAC variant: compressed instances are short and valid witnesses map efficiently, while false originals make finding any witness computationally intractable.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:19The Cryptographic Lens
- 1:36Probabilistically Checkable Proofs
- 4:45Probabilistically Checkable Arguments [KR09]
- 8:26Hardness of Approximation
- 9:25Agenda
- 10:35Application: OR-Instance Compression
- 12:07More applications
- 13:42Computational Instance Compression
- 16:09Application: OR-CIC
- 16:58Technical overview
- 19:21PCA: Attempt 1
- 21:32Holographic SNARG verifier Idea: SNARG of (JKKZ20) is holographic.
- 22:37Sublinear SNARG verifier
- 23:30PCA: Construction
- 24:56Conclusions
related talks
01h 13mA Zero-Knowledge PCP Theorem
01h 08mTutorial on Proof Systems
01h 08mIncrementally Verifiable Computation for NP from Standard Assumptions
30mProof Carrying Data
01h 06mSecure Computation and Low-Complexity Cryptography
01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristic
01h 01mLocal Proofs Approaching the Witness Length
57mThe Cryptographic Lens: Visions of our Past and Future