Lattice-based Zero-knowledge Proofs

on YouTube ↗01h 06m

" summary

A practical toolbox for lattice-based zero-knowledge condenses range proofs, commitments and algebraic tricks to get from megabyte-scale proofs down to 10–20 kilobytes; constructions use module LWE, Ajtai-style commitments / BDLOP composition, rejection sampling and an embedding that makes ZQ statements the constant coefficient of RQ products. Parameters target q ≈ 2^16–2^32 and d = 64 or 128. Implementations show efficient proofs of small-norm witnesses, correct encryption and batchable statements; quadratic relations and exact norms are handled via JL-style reductions.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 0:11Zero Knowledge Proofs from Lattices
3. 12:03Rejection Sampling
4. 19:10Signature Schemes
5. 31:03The Commitment Scheme
6. 33:28Ite Commitment
7. 36:02Prove a Linear Relation over Our Q

" related talks

• 49mLattice-Based Zero Knowledge and ApplicationsDaniele Micciancio · ZK Day 2019: Blockchains, Micropayments and Zero Knowledge
• 33mAn Introduction to Zero Knowledge ProofsShubham Patil, Keertana Ganesh · DevOpsDays Geneva 2023
• 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)
• 38mNew Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...Dana Dachman-Soled · Minimal Complexity Assumptions for Cryptography 2023
• 33mA New Approach for Non-Interactive Zero-Knowledge from Learning with ErrorsBrent Waters · Proofs (Simons Institute)
• 53mProofs Without Evidence: Assurance on the Blockchain and Other ApplicationsDan Boneh, Dave Archer, Riad S. Wahby · RSAC 2022
• 01h 03mLinear-Time Zero-Knowledge Arguments with Logarithmic Proof-SizeJonathan Bootle · Proofs, Consensus, and Decentralizing Society Reunion 2020