Paper 2021/263

Non-Interactive Half-Aggregate Signatures Based on Module Lattices - A First Attempt

Abstract

The Fiat-Shamir with Aborts paradigm of Lyubashevsky 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. Informally, it can be seen as a lattice analogue of the well-known discrete-logarithm-based Schnorr signature. 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 significantly smaller than the trivial concatenation of all signatures. Ideally, the aggregation can be done offline by a third party, called public aggregation. Previous works have shown that it is possible to half-aggregate Schnorr signatures, but it was left unclear if the underlying techniques can be adapted to the lattice setting. In this work, we show that, indeed, we can use similar strategies to obtain a signature scheme allowing for public aggregation whose hardness is proven 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). Unfortunately, our scheme produces aggregated signatures that are larger than the trivial solution of concatenating. This is due to peculiarities that seem inherent to lattice-based cryptography. Its motivation is thus mainly pedagogical, as we explain the subtleties when designing lattice-based aggregate signatures that are supported by a proper security proof.

Note: Revision June 2023: Publication venue added; Publication title slightly differs from e-print title! Revision May 2022: - Moved from simple sum to random linear combination (avoid rogue-attacks while keeping security in the standard model) - Removed linear compression function T as it is prone to simple lattice attacks - Change of title (old: "Compressed Linear Aggregate Signatures Based on Module Lattices") [Revision April 2021: - 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).]