Paper 2021/263

Compressed Linear Aggregate Signatures Based on Module Lattices

Katharina Boudgoust and Adeline Roux-Langlois

Abstract

The Fiat-Shamir with Aborts paradigm of Lyubashevsky (Asiacrypt’09) has given rise to efficient lattice-based signature schemes. One popular implementation is Dilithium which is a finalist in an ongoing standardization process run by the NIST. An interesting research question is whether it is possible to combine several unrelated signatures, issued from different signing parties on different messages, into one single aggregated signature. Of course, its size should be much smaller than the trivial concatenation of all signatures. Ideally, the aggregation can be done offline by a third party, called public aggregation. Doröz et al. (IACR eprint 2020/520) proposed a first lattice-based aggregate signature scheme allowing public aggregation. However, its security is based on the hardness of the Partial Fourier Recovery problem, a structured lattice problem which neither benefits from worst-to-average reductions nor wasn’t studied extensively from a cryptanalytic point of view. In this work we give a first instantiation of an aggregate signature allowing public aggregation whose hardness is proven in the aggregate independent-chosen-key model assuming the intractability of two well-studied problems on module lattices: The Module Learning With Errors problem (M-LWE) and the Module Short Integer Solution problem (M-SIS). Both benefit from worst-case to average-case hardness reductions. The security model we use is a more restricted variant of the original aggregate chosen-key model. Our protocol can be seen as an aggregated variant of Dilithium. Alternatively, it can be seen as a transformation of the protocol from Doröz et al. to the M-LWE/M-SIS framework.

Note: Added description of a known attack against the aggregate signature scheme in the chosen key model (Section 4.3) and revised the underlying security model (Section 4.1).