LaZer: Lattice-Based Zero-Knowledge Arguments for Lattice Relations

“Preview Talk” (by Team LaZer) @ TCPT2, in reply to the NIST Threshold Call

Abstract: In this talk we present LaZer, our Category S6 submission to the NIST First Call for Multi-Party Threshold Schemes: a lattice-based, non-interactive, transparent (no trusted setup) zero-knowledge argument of knowledge for statements about secrets in module lattices. The defining feature of LaZer is that it proves lattice relations natively - that is, directly in module-ring arithmetic, without first arithmetizing them into a circuit. This lets the proof system share lattice arithmetic (such as the NTT) with the application it certifies, express statements in their natural language of ring equalities and norm bounds, and reduce security to the very same Module-SIS and Module-LWE assumptions that already underpin the primitive being proven - introducing no new assumptions. Security is computational and plausibly post-quantum, at the 128-bit level, obtained via the Fiat–Shamir transform of a public-coin interactive argument.
The talk provides an overview of the type of statements that can be proved, how this is done using a hand full of core techniques, and potential improvements and updates that are being explored.

Joint work: Patrick Steuer, Ngoc Khanh Nguyen, Vadim Lyubashevsky, Michał Osadnik, Gregor Seiler

[Slides] Suggested readings:

• Preview Writeup (PDF): Lattice-Based Zero-Knowledge Arguments for Lattice Relations
• The LaZer Library: Lattice-Based Zero Knowledge and Succinct Proofs for Quantum-Safe Privacy (ia.cr/2024/1846)
• Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General (ia.cr/2022/284)