Paper 2024/311

Aggregating Falcon Signatures with LaBRADOR

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.

Note: Changelog (August 9, 2024) Technical: – In our instantation of LaBRADOR, where we previously recommended the use of a high-splitting ring, we now recommend using a 2-splitting ring bringing us closer to the original parameters in [BS23]. Through the lifting approach from [CHK+ 21], this allows both shorter proofs and more efficient ring computations. We report our improved aggregate signature sizes in Section 7. – We highlight how our approach can be adapted to the same synchronized model as Squirrel [FSZ22] and Chipmunk [FHSZ23], giving sublinear sizes by eliminating the need for salts. Editorial: – Restructured and improved the exposition for predicate special soundness. Section 4 gives preliminaries on multi-round special soundness, and exemplifies its limitations with a worked example. Section 5 introduces predicate special soundness definitions and applies them to the example from Section 4. – Section 7 now has a greater emphasis on concrete aggregate signature sizes and comparisons to existing schemes. – Various minor editorial changes.