Aggregating Falcon Signatures with LaBRADOR

Marius Andre Årdal*, Diego F. Aranha, Katharina Boudgoust, Sebastian Kolby, Akira Takahashi

*Corresponding author for this work

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

2 Citations (Scopus)

Abstract

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. We start by providing 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. We then explain the exact steps to take in order to adapt the non-interactive LaBRADOR proof system for aggregating Falcon signatures and provide concrete proof size estimates. Additionally, we formalize the folklore approach of obtaining aggregate signatures from the class of hash-then-sign signatures through arguments of knowledge.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2024 - 44th Annual International Cryptology Conference, Proceedings
EditorsLeonid Reyzin, Douglas Stebila
Number of pages36
Publication dateAug 2024
Pages71-106
ISBN (Print)9783031683756
DOIs
Publication statusPublished - Aug 2024
Event44th Annual International Cryptology Conference - University of California Santa Barbara, Santa Barbara, United States
Duration: 18 Aug 202422 Aug 2024
https://crypto.iacr.org/2024/

Conference

Conference44th Annual International Cryptology Conference
LocationUniversity of California Santa Barbara
Country/TerritoryUnited States
CitySanta Barbara
Period18/08/202422/08/2024
Internet address

Fingerprint

Dive into the research topics of 'Aggregating Falcon Signatures with LaBRADOR'. Together they form a unique fingerprint.

Cite this