An introduction to lattice-based folding schemes
summary
Claims a lattice-based folding pipeline that yields post-quantum security plausibly and provers that run in about n·λ·log d field multiplications (highly parallelizable), with verifiers costing roughly λ + log n small-field hashes plus d ring operations. Construction uses ring/SWIFFT-style linear-homomorphic commitments (about 30–40× faster than EC Pedersen), Module‑SIS, and a decomposition trick to avoid norm blowup plus lattice range proofs via bit decomposition and table‑lookup/monomial embedding. RoK reductions are built and work; open issues include Fiat‑Shamir in the QROM and truly non‑interactive post‑quantum folding.
AI-written summary · about
chapters (11)
- 0:00Introduction to the talk
- 1:27Motivation for scaling SNARKs
- 3:26The concept of folding
- 7:11Defining folding schemes
- 12:24Lattice-based constructions
- 18:14Security and technical challenges
- 20:40Framework for lattice folding
- 32:20Addressing knowledge extraction
- 36:43Lattice-based range proofs
- 44:54Advanced lookup techniques
- 56:47Summary and open questions
related talks
40mPost-Quantum
58mQuantum 2
01h 04mLattice-Based Post-Quantum iO from Circular Security with Random Opening Assumption
01h 06mLattice-based Zero-knowledge Proofs
01h 40mHistorical Talk on Lattice-Based Cryptography
01h 08mCryptography from Ideal Lattices
01h 09mProofs - Practice 1
24mA Framework for Post-Quantum Succinct Arguments