Incrementally Verifiable Computation for NP from Standard Assumptions

on YouTube ↗01h 08m

" summary

Construction shows two concrete IVC routes: one uses subexponential iO + LWE (or bilinear maps) plus rate‑1 BARGs and complexity leveraging to get proofs of size poly(|x_i|, log T), the other uses injective PRGs + iO to get IVC for keyed “trapdoor” NP languages with proof size poly(log T). Tools include puncturable PRFs, iO hybrids and rerandomizable PRG planting, and applications demonstrated include verifiable multiparty shuffles and authenticated image edits; extraction is avoided only in the trapdoor case.

AI-written summary · about

" chapters (7)

1. 0:00IVC for NP introduction
2. 3:57IVC applications in image editing and voting
3. 8:55Valiant's IVC construction recipe
4. 17:25IVC from subexponential SNARKs
5. 33:25IVC for trapdoor NP languages
6. 51:57iO proof techniques and security
7. 1:01:16Summary of IVC research

" related talks

• 01h 09mProofs - Practice 1Justin Thaler · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 31mIndistinguishability Obfuscation, Range Avoidance, and Bounded ArithmeticRahul Ilango · Proof Complexity and Meta-Mathematics 2023
• 38mAdvisor-Verifier-Prover Games and the Hardness of Information Theoretic CryptographyBenny Applebaum · Minimal Complexity Assumptions for Cryptography 2023
• 59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-VersaAlex Lombardi, Rahul Ilango · Obfuscation
• 57mIndistinguishability Obfuscation from Well-Founded AssumptionsAayush Jain · Simons Institute Workshop: New Developments in Obfuscation
• 42mObfuscation IV: A New Assumption enabling iOAmit Sahai · Lattices: New Cryptographic Capabilities 2020