SEASON 3 MODULE 3
Lattice-based SNARKs, w/ Vadim Lyubashevsky
In this module, Nicolas Mohnblatt and Vadim Lyubashevsky introduce post-quantum cryptography based on lattices, explaining the hard problems like the Small Integer Solution (SIS) problem that are believed to be resistant to quantum computers. Vadim demonstrates how to build commitment schemes from these problems and then develops a proof system to prove knowledge of a committed vector with a small norm, a critical security requirement. The presentation details the “left-right” proof technique for proving precise quadratic relations (like norms) and concludes by showing how moving from integers to polynomial rings dramatically improves the efficiency of these cryptographic constructions.
What you’ll learn:
- 00:00 Introduction and Session Outline
- 02:27 The Hard Lattice Problem: Short Integer Solution (SIS)
- 05:28 Building a (Compressing) Commitment Scheme from SIS
- 09:30 Proving Knowledge of a Committed Vector
- 17:10 Fixing the Soundness Flaw with a Matrix Challenge
- 21:52 Extracting the Witness and Proving Linear Relations
- 26:24 Proving a Precise Norm, using Left-Right Technique
- 30:08 The Full Protocol
- 44:47 The Final Hurdle: Bounding Norms with Random Projections
- 56:19 Inefficiencies of the Integer-Based Construction
- 1:01:25 The Efficient Solution: Using Polynomial Rings
- 1:14:17 The Final Trick: Using Automorphisms to Compute Norms
- 1:20:37 Session Summary and Conclusion
Below is an accompanying reading list:
- Short integer solution problem definition – Wikipedia (https://en.wikipedia.org/wiki/Short_integer_solution_problem)
- Generating hard instances of lattice problems, by Miklós Ajtai (https://dl.acm.org/doi/10.1145/237814.237838)
- Schwartz-Zippel lemma (https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma)
- An Introduction to Johnson–Lindenstrauss Transforms (https://arxiv.org/pdf/2103.00564)
- LaBRADOR: Compact Proofs for R1CS from Module-SIS (https://eprint.iacr.org/2022/1341.pdf)
- A Complete Beginner Guide to the Number Theoretic Transform (NTT) (https://eprint.iacr.org/2024/585.pdf)
ZK Whiteboard Sessions is an educational series on all things zero knowledge. Presented by ZK Hack.
Get notified on latest module upload by signing up below.