Aggregating Falcon Signatures with LaBRADOR

TY - GEN

T1 - Aggregating Falcon Signatures with LaBRADOR

AU - Årdal, Marius Andre

AU - Aranha, Diego F.

AU - Boudgoust, Katharina

AU - Kolby, Sebastian

AU - Takahashi, Akira

PY - 2024/8

Y1 - 2024/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85202186581&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-68376-3_3

DO - 10.1007/978-3-031-68376-3_3

M3 - Article in proceedings

SN - 9783031683756

SP - 71

EP - 106

BT - Advances in Cryptology – CRYPTO 2024 - 44th Annual International Cryptology Conference, Proceedings

A2 - Reyzin, Leonid

A2 - Stebila, Douglas

T2 - 44th Annual International Cryptology Conference

Y2 - 18 August 2024 through 22 August 2024

ER -