Linear-Time Zero-Knowledge Arguments with Logarithmic Proof-Size

on YouTube ↗01h 03m

" summary

Claim: cryptographic arguments with a linear-time prover and indexer, polylogarithmic verification and logarithmic query complexity, constructed by turning tensor-query IOPs into point-query IOPs via a code-based compiler that uses linear-time encodable codes and tensor-product encodings, plus masking and a Merkle-style hashing step to get a crypto argument. Built information-theoretic IOPs and then hashed them; works but requires large fields (≥ Omega(n)) and incurs nontrivial coding overheads and unknown concrete constants.

AI-written summary · about

" chapters (33)

1. 0:00Intro
2. 0:43The holy grail for efficient zero-knowledge
3. 2:13What counts as linear time?
4. 3:10Obstacles
5. 4:41The holy grail requires
6. 4:51A ray of hope
7. 8:03Interactive oracle proofs
8. 9:14Approach for sublinear proof size and verification
9. 11:12The code-based compiler
10. 12:23Approach for polylogarithmic proof size verification
11. 13:25Related techniques
12. 24:45Quick and easy tensor IOPs
13. 26:51The compiled point-query IOP
14. 28:45Encodings using the tensor code c
15. 29:41How does the consistency test work?
16. 30:47A folding operation
17. 31:06Computing query answers by folding
18. 31:46Partial tensor encodings
19. 32:10Partially encoding tensor IOP proofs
20. 32:21How do we check consistency?
21. 32:38How the IOPP checks consistency
22. 33:01The consistency check IOPP
23. 33:13What the verifier wants to check
24. 33:24Spot-checks using few queries
25. 34:58Analysis: prover complexity
26. 36:12Analysis: query and verifier complexity
27. 38:07Zero-knowledge and tensor encodings
28. 38:42Codeword entries leak information
29. 39:10Masking with encoding randomness
30. 40:12Defining zero-knowledge algebraically
31. 45:27Tensor products of zero-knowledge code
32. 48:59Query bounds under tensor products
33. 50:11Summary of results

" related talks

• 01h 06mLattice-based Zero-knowledge ProofsVadim Lyubashevsky · Quantum and Lattices Joint Reunion Workshop
• 01h 09mProofs - Practice 1Justin Thaler · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 13mA Zero-Knowledge PCP TheoremNicholas Spooner · Proofs (Simons Institute)
• 43mConstant-Round Arguments from One-Way FunctionsGuy N. Rothblum · Minimal Complexity Assumptions for Cryptography 2023
• 41mTalk by Elaine Shi (Carnegie Mellon University)Elaine Shi · Obfuscation
• 57mThe Cryptographic Lens: Visions of our Past and FutureShafi Goldwasser · Symposium on Visions of the Theory of Computing 2013
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 38mNew Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...Dana Dachman-Soled · Minimal Complexity Assumptions for Cryptography 2023