International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 15 February 2023

Katharina Boudgoust, Akira Takahashi
ePrint Report ePrint Report
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.
Expand

Additional news items may be found on the IACR news page.