Sequential Half-Aggregation of Lattice-Based Signatures

With  \(\textsf {Dilithium} \) and  \(\textsf {Falcon} \) , NIST selected two lattice-based signature schemes during their post-quantum standardization project. Whereas \(\textsf {Dilithium} \) follows the Fiat-Shamir with Aborts (Lyubashevsky, Asiacrypt’09) blueprint, \(\textsf {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 ( \(\textsf{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 \(\textsf {Falcon} \) -based \(\textsf{SAS}\) (Wang and Wu, PROVSEC’19), and proposes a fix for it. We then construct the first Fiat-Shamir with Aborts based  \(\textsf{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  \(\textsf{SAS}\) which all follow the GPV-paradigm. The bottom line is that none of the schemes achieves a good compression rate so far.