Paper 2021/263

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

Katharina Boudgoust, Aarhus University
Adeline Roux-Langlois, Univ Rennes, CNRS, IRISA
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).]

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. The Computer Journal 2023
DOI
10.1093/comjnl/bxad013
Keywords
Lattice-based cryptographyModule LatticesSignature Aggregation
Contact author(s)
katharina boudgoust @ cs au dk
History
2023-06-15: last of 3 revisions
2021-03-03: received
See all versions
Short URL
https://ia.cr/2021/263
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/263,
      author = {Katharina Boudgoust and Adeline Roux-Langlois},
      title = {Non-Interactive Half-Aggregate Signatures Based on Module Lattices - A First Attempt},
      howpublished = {Cryptology ePrint Archive, Paper 2021/263},
      year = {2021},
      doi = {10.1093/comjnl/bxad013},
      note = {\url{https://eprint.iacr.org/2021/263}},
      url = {https://eprint.iacr.org/2021/263}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.