Paper 2024/496

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

Thomas Espitau, PQShield
Shuichi Katsumata, PQShield, National Institute of Advanced Industrial Science and Technology
Kaoru Takemure, PQShield, National Institute of Advanced Industrial Science and Technology
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 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 (AOMMLWE) assumption. We believe this to be a strong inclusion to our lattice toolkits with an independent interest. We establish the selective security of AOMMLWE 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2024
Keywords
Threshold signatureLatticeRaccoonTwo-round signing protocolOne-more assumption.
Contact author(s)
thomas espitau @ pqshield com
shuichi katsumata @ pqshield com
kaoru takemure @ pqshield com
History
2024-07-02: revised
2024-03-28: received
See all versions
Short URL
https://ia.cr/2024/496
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/496,
      author = {Thomas Espitau and Shuichi Katsumata and Kaoru Takemure},
      title = {Two-Round Threshold Signature from Algebraic One-More Learning with Errors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/496},
      year = {2024},
      url = {https://eprint.iacr.org/2024/496}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.