Ringtail: Practical Two-Round Threshold Signatures from Learning with Errors (original) (raw)

Paper 2024/1113

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

Darya Kaviani, University of California, Berkeley

Russell W. F. Lai, Aalto University

Giulio Malavolta, Bocconi University

Akira Takahashi, J.P.Morgan AI Research & AlgoCRYPT CoE

Mehdi Tibouchi, NTT (Japan)

Abstract

A threshold signature scheme splits the signing key among ell\ellell parties, such that any ttt-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 tleq1024t \leq 1024tleq1024 parties. For 128128128-bit security and t=1024t = 1024t=1024 parties, we achieve 13.413.413.4 KB signature size and 10.510.510.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: Full version

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}, doi = {10.1109/SP61157.2025.00070}, url = {https://eprint.iacr.org/2024/1113} }