Lattice-Based Zero Knowledge and Applications

on YouTube ↗49m

" summary

Gives interactive zero‑knowledge proofs for lattice problems and shows the closest‑vector language lies in SZK, ruling out NP‑hardness for useful approximation factors. Builds protocols from LWE parity‑check lattices and a reduction mod q, uses instance‑dependent commitments (red/blue shifted lattices) and a Stern‑style permutation protocol to prove bounded-error vectors without leaking them. Derives ID schemes and Fiat‑Shamir signatures, explains efficiency fixes, and cites recent NIZK constructions based on standard LWE that yield practical, post‑quantum secure primitives.

AI-written summary · about

" chapters (29)

1. 0:00Lattice-Based Zero Knowledge and Applications
2. 4:28Lattices
3. 5:36Shortest Vector Problem (SVP)
4. 6:00Closest Vector Problem (CVP)
5. 6:31Proof Systems
6. 7:18Zero Knowledge Proofs
7. 8:39Outline
8. 11:01Limits of inapproximability
9. 13:32GG proof system
10. 16:36Properties of GG proof
11. 18:35Efficiency Issues
12. 20:26Reducing points modulo a lattice
13. 21:15Lattice Cryptography
14. 23:01Injective / Surjective Functions
15. 24:19Hash functions, Commitments, Encryption. . Collision resistant Hashing GGH 96
16. 26:06Hash functions, Commitments, Encryption . Collision resistant Hashing GGH 96
17. 26:43Prover efficiency
18. 28:14Application: Identification
19. 29:02Identification: Security
20. 29:34Proof system for CVP [MV'03]
21. 31:35Commitment schemes
22. 32:13Instance-Dependent Commitment
23. 33:13Instance-dependent security
24. 34:17Revisiting CVP interactive proofs
25. 36:29Knowledge gap
26. 37:24Stern-like protocol: no gap!
27. 39:51Improved Stern-like protocol
28. 42:33Schnorr-like protocols: small soundness error!
29. 44:42Lattice based signatures

" related talks

• 01h 06mLattice-based Zero-knowledge ProofsVadim Lyubashevsky · Quantum and Lattices Joint Reunion Workshop
• 33mAn Introduction to Zero Knowledge ProofsShubham Patil, Keertana Ganesh · DevOpsDays Geneva 2023
• 33mA New Approach for Non-Interactive Zero-Knowledge from Learning with ErrorsBrent Waters · Proofs (Simons Institute)
• 38mNew Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...Dana Dachman-Soled · Minimal Complexity Assumptions for Cryptography 2023
• 33mEducational Challenges in the Ever-Evolving Space of Zero-KnowledgeMary Maller, Luis Brandao · Zcon4 2023
• 39mLattice Based Cryptography PrimerBob Relyea · DevConf.CZ 2021
• 19mDIZK: A Distributed Zero Knowledge Proof SystemHoward Wu · USENIX Security '18
• 26mPractical, Efficient ZKPs, Economic and Social ProcessesMichael Rabin · KARPfest80