Paper 2023/159

Sequential Half-Aggregation of Lattice-Based Signatures

Katharina Boudgoust, Aarhus University
Akira Takahashi, University of Edinburgh
Abstract

With Dilithium and Falcon, NIST selected two lattice-based signature schemes during their post-quantum standardization project. Whereas Dilithium follows the Fiat-Shamir with Aborts (Lyubashevsky, Asiacrypt'09) blueprint, Falcon can be seen as an optimized version of the GPV-paradigm (Gentry et al., STOC'06). An important question now is whether those signatures allow additional features such as the aggregation of distinct signatures. One example are sequential aggregate signature (SAS) schemes (Boneh et al., Eurocrypt'04) which allow a group of signers to sequentially combine signatures on distinct messages in a compressed manner. The present work first reviews the state of the art of (sequentially) aggregating lattice-based signatures, points out the insecurity of one of the existing Falcon-based SAS (Wang and Wu, PROVSEC'19), and proposes a fix for it. We then construct the first Fiat-Shamir with Aborts based SAS by generalizing existing techniques from the discrete-log setting (Chen and Zhao, ESORICS'22) to the lattice framework. Going from the pre-quantum to the post-quantum world, however, does most often come with efficiency penalties. In our work, we also meet obstacles that seem inherent to lattice-based signatures, making the resulting scheme less efficient than what one would hope for. As a result, we only achieve quite small compression rates. We compare our construction with existing lattice-based SAS which all follow the GPV-paradigm. The bottom line is that none of the schemes achieves a good compression rate so far.

Note: Full version

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ESORICS 2023
DOI
10.1007/978-3-031-50594-2_14
Keywords
Sequential Aggregate SignatureDilithiumFalconFiat-Shamir with Aborts
Contact author(s)
katharina boudgoust @ cs au dk
takahashi akira 58s @ gmail com
History
2024-03-04: revised
2023-02-09: received
See all versions
Short URL
https://ia.cr/2023/159
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2023/159,
      author = {Katharina Boudgoust and Akira Takahashi},
      title = {Sequential Half-Aggregation of Lattice-Based Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/159},
      year = {2023},
      doi = {10.1007/978-3-031-50594-2_14},
      url = {https://eprint.iacr.org/2023/159}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.