Paper 2024/1113

Ringtail: Practical Two-Round Threshold Signatures from Learning with Errors

Cecilia Boschini, ETH Zürich
Darya Kaviani, University of California, Berkeley
Russell W. F. Lai, Aalto University
Giulio Malavolta, Bocconi University, Max Planck Institute for Security and Privacy
Akira Takahashi, J.P.Morgan AI Research & AlgoCRYPT CoE
Mehdi Tibouchi, NTT (Japan)
Abstract

A threshold signature scheme splits the signing key among $\ell$ parties, such that any $t$-subset of parties can jointly generate signatures on a given message. Designing concretely efficient post-quantum threshold signatures is a pressing question, as evidenced by NIST's recent call. In this work, we propose, implement, and evaluate a lattice-based threshold signature scheme, Ringtail, which is the first to achieve a combination of desirable properties: (i) The signing protocol consists of only two rounds, where the first round is message-independent and can thus be preprocessed offline. (ii) The scheme is concretely efficient and scalable to $t \leq 1024$ parties. For $128$-bit security and $t = 1024$ parties, we achieve $13.4$ KB signature size and $10.5$ KB of online communication. (iii) The security is based on the standard learning with errors (LWE) assumption in the random oracle model. This improves upon the state-of-the-art (with comparable efficiency) which either has a three-round signing protocol [Eurocrypt'24] or relies on a new non-standard assumption [Crypto'24]. To substantiate the practicality of our scheme, we conduct the first WAN experiment deploying a lattice-based threshold signature, across 8 countries in 5 continents. We observe that an overwhelming majority of the end-to-end latency is consumed by network latency, underscoring the need for round-optimized schemes.

Note: Fixed typos

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
threshold signatureslatticeLWE
Contact author(s)
cecilia boschini @ inf ethz ch
daryakaviani @ berkeley edu
russell lai @ aalto fi
giulio malavolta @ hotmail it
takahashi akira 58s @ gmail com
mehdi tibouchi @ normalesup org
History
2024-07-10: approved
2024-07-09: received
See all versions
Short URL
https://ia.cr/2024/1113
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1113,
      author = {Cecilia Boschini and Darya Kaviani and Russell W. F. Lai and Giulio Malavolta and Akira Takahashi and Mehdi Tibouchi},
      title = {Ringtail: Practical Two-Round Threshold Signatures from Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1113},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/1113}},
      url = {https://eprint.iacr.org/2024/1113}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.