Paper 2023/159

Sequential Half-Aggregation of Lattice-Based Signatures

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