“Preview Talk” (by Team Lemur) @ TCPT2, in reply to the NIST Threshold Call
Abstract: In this talk, we present Lemur, a non-interactive synchronized multi-signature scheme based on lattice cryptography, designed for large-scale distributed systems such as blockchain protocols. Lemur builds on the ideas introduced in Squirrel and Chipmunk but fundamentally redesigns the cryptographic foundations of the framework to achieve improved efficiency. A central contribution is the introduction of the Dual Hint-MLWE assumption, a new lattice assumption that we show is at least as hard as the standard Module-LWE problem. Leveraging this assumption, Lemur redesigns the underlying key-homomorphic one-time signature (KOTS) component, resulting in significantly improved compactness and scalability, with up to an order-of-magnitude reduction in KOTS size compared with Chipmunk. We also revisit the homomorphic vector commitment layer, moving from Ring-SIS to Module-SIS assumptions and extending commitment domain from vectors to matrices, further improving aggregation efficiency. Together, these advances enable Lemur to reduce aggregate signature sizes by roughly a factor of two while supporting extremely large signer sets, making it a practical post-quantum solution for synchronized multi-signature applications. Concretely, at 128-bit post-quantum security, the current Rust implementation profile yields an aggregate of about 380 KB for one million individual signatures (versus Chipmunk’s ∼728 KB), while keeping stateful signing millisecond-scale and aggregated verification in the tens of milliseconds for 1024 signers.
Joint work: Yini Lin, Muhammed F. Esgin, Markku-Juhani O. Saarinen, Amin Sakzad, Ron Steinfeld
[Slides] Suggested readings:
- Preview Writeup (PDF): Lemur: Scalable Post-Quantum Synchronized Multi-Signatures (see also ia.cr./2026/1161)
- Chipmunk: Better Synchronized Multi-Signatures from Lattices (ia.cr./2023/1820)
- Squirrel: Efficient Synchronized Multi-Signatures from Lattices (ia.cr/2022/694)
