Two-Round Threshold Signature from Algebraic One-More Learning with Errors

Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring two-rounds or less are based on heavy tools such as (fully) homomorphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round signatures from classical assumptions either rely on idealized model such as algebraic group models or on one-more type assumptions, none of which we have a nice analogue in the lattice world. In this work, we construct the first efficient two-round lattice-based threshold signature without relying on FHE or HTDC. It has an offline-online feature where the first round can be preprocessed without knowing message or the signer sets, effectively making the signing phase non-interactive. The signature size is small and shows great scalability. For example, even for a threshold as large as 1024 signers, we achieve a signature size roughly 11 KB. At the heart of our construction is a new lattice-based assumption called the algebraic one-more learning with errors ( \(\textsf{AOM}\text {-}\textsf{MLWE} \) ) assumption. We believe this to be a strong inclusion to our lattice toolkits with an independent interest. We establish the selective security of \(\textsf{AOM}\text {-}\textsf{MLWE} \) based on the standard \(\textsf{MLWE} \) and \(\textsf{MSIS} \) assumptions, and provide an in depth analysis of its adaptive security, which our threshold signature is based on.