International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Shuichi Katsumata , PQShield and AIST
Kaoru Takemure , PQShield and AIST
Thomas Espitau , PQShield
Download:
DOI: 10.1007/978-3-031-68394-7_13 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: 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 less than two-rounds 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 reprocessed 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 (AOM-MLWE) assumption. We believe this to be a strong inclusion to our lattice toolkits with an independent interest. We establish the selective security of AOM-MLWE based on the standard MLWE and MSIS assumptions, and provide an in depth analysis of its adaptive security, which our threshold signature is based on.
BibTeX
@inproceedings{crypto-2024-34164,
  title={Two-Round Threshold Signature from Algebraic One-More Learning with Errors},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68394-7_13},
  author={Shuichi Katsumata and Kaoru Takemure and Thomas Espitau},
  year=2024
}