Paper 2024/1113
Ringtail: Practical Two-Round Threshold Signatures from Learning with Errors
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)
- 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
-
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}, url = {https://eprint.iacr.org/2024/1113} }