[MPTC-forum] Lemur
Yini Lin
Dear MPTC Forum,
On July 08, 2026, at 11:00, in Talk 2a2, we presented our work, Lemur: Scalable Post-Quantum Synchronized Multi-Signatures.
Lemur builds upon Squirrel and Chipmunk (CCS 2022/2023) while fundamentally redesigning the underlying key-homomorphic one-time signature (KOTS). Our main technical contribution is the introduction of the Dual Hint-MLWE assumption, a new lattice assumption that we prove is at least as hard as the standard Module-LWE problem. Based on this assumption, we prove the security of our KOTS under Dual Hint-MLWE and Module-SIS.
These new foundations enable a more compact KOTS, achieving <8 KB for one million aggregated KOTS, which is up to an order-of-magnitude improvement over Chipmunk. We also generalize the underlying homomorphic vector commitment (HVC) from the ring setting to the module setting, further improving aggregation efficiency and scalability.
Overall, Lemur reduces aggregate signature sizes by roughly a factor of two compared with Chipmunk while maintaining efficient signing and verification, making it a practical post-quantum synchronized multi-signature scheme for large-scale distributed systems.
Links:
Preview Writeup: https://csrc.nist.gov/csrc/media/Projects/threshold-cryptography/documents/TCall-1/Lemur-PW02.pdf
ePrint Paper: ia.cr/2026/1161
Lemur Team: Muhammed Esgin, Yini Lin, Markku-Juhani O. Saarinen, Amin Sakzad, and Ron Steinfeld.