Paper 2024/311

Aggregating Falcon Signatures with LaBRADOR

Marius A. Aardal, Aarhus University
Diego F. Aranha, Aarhus University
Katharina Boudgoust, National Council for Scientific Research
Sebastian Kolby, Aarhus University
Akira Takahashi, J.P.Morgan AI Research & AlgoCRYPT CoE

Several prior works have suggested to use non-interactive arguments of knowledge with short proofs to aggregate signatures of Falcon, which is part of the first post-quantum signatures selected for standardization by NIST. Especially LaBRADOR, based on standard structured lattice assumptions and published at CRYPTO’23, seems promising to realize this task. However, no prior work has tackled this idea in a rigorous way. In this paper, we thoroughly prove how to aggregate Falcon signatures using LaBRADOR. First, we improve LaBRADOR by moving from a low-splitting to a high-splitting ring, allowing for faster computations. This modification leads to some additional technical challenges for proving the knowledge soundness of LaBRADOR. Moreover, we provide the first complete knowledge soundness analysis for the non-interactive version of LaBRADOR. Here, the multi-round and recursive nature of LaBRADOR requires a complex and thorough analysis. For this purpose, we introduce the notion of predicate special soundness (PSS). This is a general framework for evaluating the knowledge error of complex Fiat-Shamir arguments of knowledge protocols in a modular fashion, which we believe to be of independent interest. Lastly, we explain the exact steps to take in order to adapt the LaBRADOR proof system for aggregating Falcon signatures and provide concrete estimates for proof sizes. Additionally, we formalize the folklore approach of obtaining aggregate signatures from the class of hash-then-sign signatures through arguments of knowledge.

Available format(s)
Public-key cryptography
Publication info
LaBRADORFalconAggregate SignaturesFiat-ShamirSpecial-soundness
Contact author(s)
maardal @ cs au dk
dfaranha @ cs au dk
katharina boudgoust @ lirmm fr
sk @ cs au dk
takahashi akira 58s @ gmail com
2024-02-26: approved
2024-02-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marius A. Aardal and Diego F. Aranha and Katharina Boudgoust and Sebastian Kolby and Akira Takahashi},
      title = {Aggregating Falcon Signatures with LaBRADOR},
      howpublished = {Cryptology ePrint Archive, Paper 2024/311},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.