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

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

Speakers: Cecilia Boschini, Darya Kaviani, Russell W. F. Lai, Giulio Malavolta, Akira Takahashi, Mehdi Tibouchi

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=Llnq1eHUt-E

Overview

In an era increasingly shaped by the looming threat of quantum computing and the growing demand for robust cryptographic solutions, the talk "Ringtail: Practical Two-Round Threshold Signatures from Learning with Errors" presented a significant advancement in post-quantum cryptography. Delivered by Darya Kaviani at IEEE S&P, this presentation introduced Ringtail, a novel threshold signature scheme designed for efficiency and security in the post-quantum landscape. The core innovation lies in its ability to achieve a secure, two-round signing protocol while relying on well-established lattice-based assumptions, specifically Module Learning With Errors (MLWE) and Self-Target Cyclotomic Isogeny System (CIS).

The urgency for such solutions is underscored by NIST's recent call for multi-party threshold cryptography, explicitly including a demand for additional post-quantum signatures. Ringtail directly addresses this need by offering a practical implementation that balances cryptographic rigor with real-world performance. Its architecture features a lean online phase, crucial for distributed systems, making it particularly attractive for applications where latency and communication overhead are critical concerns.

While achieving a notably compact signature size of 13.4 kilobytes and minimal online communication of 10.5 kilobytes for 1024 parties, Ringtail also highlights a trade-off: a substantial offline communication cost of approximately 600 kilobytes. This characteristic, acknowledged by the speakers as potentially an artifact of the security proof, points to avenues for future optimization. Nevertheless, Ringtail stands out for its provable security under standard assumptions and its superior online performance compared to prior work, marking it as a compelling candidate for the next generation of cryptographic systems.

Background

▶ Watch: Introduction to threshold signatures and Ringtail overview (0:00)

Threshold signatures are a cornerstone of modern distributed security architectures, offering a robust method for shared control over cryptographic keys. The fundamental concept involves splitting a single cryptographic signing key into multiple shares, such that no single entity holds the entire key. Instead, a predefined number, T, out of a total of N parties (often denoted as a T-of-N scheme), must collectively cooperate to produce a valid signature. Crucially, T-1 parties cannot forge a signature, ensuring that even if a subset of servers is compromised, the secret key remains secure. This distributed trust model significantly enhances resilience against single points of failure and insider threats.

The imperative for post-quantum cryptography stems from the theoretical threat posed by future quantum computers, which are expected to break many of the cryptographic algorithms widely used today, such as RSA and ECC. In response, cryptographic research has shifted towards developing quantum-resistant alternatives, with lattice-based cryptography emerging as a leading candidate. NIST's ongoing standardization process for post-quantum algorithms and its specific call for multi-party threshold cryptography highlight the critical need for practical, quantum-safe threshold signature schemes.

Prior attempts to build threshold signatures, especially in the post-quantum domain, have faced significant challenges. Generic approaches, such as those relying on Multi-Party Computation (MPC) or Fully Homomorphic Encryption (FHE), offer strong security guarantees but often come with prohibitive computational and communication overheads, rendering them concretely inefficient for many real-world applications. This limitation has driven researchers to explore more tailored, specialized solutions.

Ringtail's development is rooted in a progression of tailored lattice-based schemes. The journey begins with the Raccoon identification scheme, a foundational interactive proof of knowledge. Applying the Fiat-Shamir heuristic to the Raccoon ID scheme transforms it into a non-interactive Raccoon signature. However, directly thresholdizing this scheme presents security vulnerabilities, particularly against interactive adversaries. To overcome these, Ringtail incorporates several advanced ingredients: T-Raccoon masking to protect individual contributions, FROST specialization (specifically, a Schnorr-style random linear combination) which is key to achieving a two-round structure, and the use of simulation-based proofs to reduce its security to well-understood lattice problems like MLWE. This careful integration of techniques allows Ringtail to achieve both efficiency and provable security under standard lattice-based assumptions, addressing the shortcomings of generic and naive thresholdization attempts.

Key Findings

▶ Watch: Naive thresholdization and its security challenges (2:59)

Ringtail introduces a compelling set of features and performance characteristics that position it as a leading solution for post-quantum threshold signatures:

• Two-Round Protocol: A primary achievement of Ringtail is its highly efficient signing protocol, which consists of only two phases: one offline round and one online round. This minimization of interactive rounds is crucial for practical deployments, especially in geographically distributed systems where network latency can significantly impact performance. The online phase, in particular, is optimized for speed and minimal communication.
• Concrete Efficiency for Online Phase: While some aspects of the protocol, particularly offline communication, exhibit higher costs, Ringtail demonstrates the best online costs among prior work. This is a critical advantage, as the online phase is typically the latency-sensitive part of a signing operation, directly affecting user experience or application responsiveness.
• Compact Signature Size: Ringtail produces relatively small signatures, with a size of 13.4 kilobytes. While not the absolute smallest possible, this is a reasonable size for a lattice-based post-quantum signature, especially considering the security and threshold properties it provides.
• Low Online Communication: For a large number of parties, specifically 1024 parties, the online communication required is only 10.5 kilobytes. This low online communication overhead further contributes to its practical efficiency, making it suitable for scenarios involving many participants without overwhelming network resources.
• Provable Security from Standard Assumptions: A cornerstone of Ringtail's strength is its provable security. The scheme is rigorously reduced to standard Module LWE and Self-Target CIS assumptions in the classical random oracle model. This reliance on well-studied and widely accepted lattice problems provides strong confidence in its cryptographic security against both classical and quantum adversaries.
• Heavy Offline Communication: A notable characteristic of Ringtail is its substantial offline communication complexity, measured at approximately 600 kilobytes. The speakers acknowledge this as a significant cost, suggesting it might be an artifact of the security proof rather than an inherent limitation, and identify it as a key area for future optimization. Despite this, the offline nature means it does not impede the latency-critical online signing process.
• WAN Performance Dominance by Network Latency: The evaluation included a Wide Area Network (WAN) experiment involving eight geographically dispersed servers. The results decisively showed that network latency dominates local latency, underscoring the paramount importance of minimizing the number of message-specific roundtrips in such distributed settings. This finding validates Ringtail's two-round design as a highly effective strategy for real-world deployments.

Technical Deep Dive

▶ Watch: Ringtail's solution: Frost Schnorr Random Linear Combination (4:25)

The construction of Ringtail is an intricate journey from a basic interactive identification scheme to a sophisticated, two-round threshold signature.

The foundation of Ringtail is the Raccoon Identification (ID) scheme, an interactive protocol between a prover (Alice) and a verifier (Bob).

1. Setup: Alice possesses an LWE secret key (SK), and Bob holds the corresponding public key (PK).
2. Commitment Phase: Alice first samples two vectors, R and E*, from a Gaussian distribution. She then computes a commitment **H = A R + E, where A is a public random matrix. Alice sends H** to Bob.
3. Challenge Phase: Bob receives H and samples a challenge C from a ternary distribution (typically {-1, 0, 1}). Bob sends C back to Alice.
4. Response Phase: Alice, upon receiving C, crafts her response **Z = C * SK + R. She then sends Z** to Bob.
5. Verification Phase: Bob checks two conditions: first, that **A Z is approximately equal to C PK + H, and second, that Z is "small" (i.e., its coefficients are within a certain bound, indicating it was properly formed from Gaussian samples). The mathematical property that C * E + E*** is small ensures verification passes if Alice used the correct secret key.

To transform this interactive ID scheme into a non-interactive signature, prior work applies the Fiat-Shamir heuristic. The interactive challenge C from Bob is replaced by a deterministic hash function. Alice herself computes C = hash(PK, M, H), where M is the message to be signed. This allows Alice to generate a signature (H, Z) without needing Bob's interaction.

Thresholdizing this basic Raccoon signature naively involves using Shamir secret sharing for the LWE secret key. Each of N parties receives a share SKi of the secret key and performs the following:

• Offline Phase (Naive): Each party i samples its own Ri and Ei* (Gaussian vectors) and computes its commitment share **Hi = A Ri + Ei. These Hi** shares are exchanged among the T participating parties.
• Online Phase (Naive): The T parties sum their received Hi shares to reconstruct a combined commitment H_total = Σ Hi. They then compute the challenge C = hash(PK, M, H_total). Each party i calculates its signature contribution **Zi = C * SKi + Ri. These Zi** shares are exchanged.
• Finalization (Naive): The T parties sum their Zi shares to obtain the final signature Z_total = Σ Zi.

However, this naive approach is vulnerable. An interactive adversary could craft a malicious Hj and Zj tuple to forge a signature contribution. Ringtail addresses this critical flaw using a FROST Schnorr random linear combination technique:

1. Offline Phase (Ringtail):

• Instead of vectors Ri and Ei, each party i* now samples matrices ri and ei from a Gaussian distribution.
• They compute a different type of commitment share, **Di = A * ri + ei**.
• These Di matrices are exchanged among the T participating parties, and each party aggregates them into D_total = Σ Dj. This offline phase can be completed before the message M is known.

1. Online Phase (Ringtail):

• Once a message M needs to be signed, the T parties compute a value U by applying a Gaussian hash to the protocol transcript up to this point. This U value acts as a one-time randomizer.
• The actual commitment H for the signature is then computed as **H = D_total * U. This construction makes it computationally hard for an adversary to engineer their contribution ahead of time because U** is derived from elements unknown during the offline phase.
• The Fiat-Shamir challenge C is then computed as C = hash(PK, M, H).
• Each party i calculates its signature contribution **Zi = C SKi + ri U + NI, where NI is a one-time PRF mask with a zero share. The ri * U** term incorporates the random linear combination and is crucial for security.
• These Zi contributions are exchanged among the T parties.

1. Finalization (Ringtail):

• The T parties sum their received Zi contributions to form the final signature Z_total = Σ Zi.

The use of **D_total U for the commitment H and the inclusion of ri U in the signature contribution Zi are the core innovations that prevent the forging attacks possible in the naive thresholdization. The NI** term ensures privacy and unlinkability of individual shares. Additional protocol details, including precise parameter choices and security proofs, are elaborated in the full paper.

Demo / Proof of Concept

▶ Watch: Implementation details and performance evaluation (6:00)

The practical viability of Ringtail was demonstrated through a robust implementation and evaluation study. The scheme was implemented in 1800 lines of Go, a modern programming language known for its concurrency features and performance, making it suitable for network-intensive cryptographic protocols. The source code is publicly available, allowing for independent verification and further research.

For the evaluation, the team utilized AWS 16 vCPU and 32GB machines, providing a high-performance environment to accurately measure the computational and communication overheads. This choice of infrastructure ensures that the reported performance metrics are relevant to typical cloud-based deployments.

Ringtail's performance was benchmarked against two key baselines:

• T-Raccoon: An existing threshold signature scheme that operates in three rounds and relies on standard assumptions. This baseline provides a comparison point for the round complexity and security model.
• EKT: Another two-round threshold signature scheme, but one that relies on non-standard assumptions. This comparison highlights Ringtail's advantage in achieving a two-round protocol while maintaining provable security under more widely accepted cryptographic assumptions.

A crucial part of the evaluation involved a Wide Area Network (WAN) experiment. This setup simulated a real-world distributed environment by deploying eight servers geographically across the world. This experiment was designed to assess the impact of network latency on the protocol's performance, a factor often overlooked in local benchmark studies.

The results of the evaluation were insightful:

• Ringtail's local latency and total communication costs were found to be higher than some prior work. This is largely attributed to the heavy offline communication (approximately 600 kilobytes), which contributes to the total communication burden.
• However, Ringtail exhibited the best online costs out of the prior work. This is a critical finding, as the online phase is typically the bottleneck in interactive protocols, and Ringtail's optimization here translates directly into faster signing operations for users.
• The WAN experiment decisively confirmed that for geographically distributed parties, network latency dominates local latency. This observation strongly underscores the importance of minimizing the number of message-specific roundtrips (i.e., the number of rounds) in a protocol. Ringtail's two-round design is thus a practical necessity for efficient operation in real-world, high-latency network environments.

In summary, the implementation and evaluation validated Ringtail's design choices, demonstrating its practical efficiency, particularly in the critical online phase, and confirming the strategic advantage of its two-round structure in distributed settings.

Defensive Implications

▶ Watch: Summary of Ringtail and future research directions (6:50)

The advent of Ringtail provides several significant implications for cybersecurity defenders and organizations looking to secure their digital assets against both classical and quantum threats.

Firstly, Ringtail offers a practical, provably secure two-round post-quantum threshold signature scheme. This directly addresses the NIST call for multi-party threshold cryptography in the post-quantum era. For organizations planning their migration to quantum-resistant cryptography, Ringtail presents a concrete option that combines strong security guarantees (from standard Module LWE and Self-Target CIS assumptions) with operational efficiency. Defenders can now consider deploying a threshold signature solution that is not only resistant to future quantum attacks but also performs adequately in real-world, distributed environments.

Secondly, the emphasis on a two-round protocol with optimized online costs is a critical defensive advantage. In many high-stakes operational scenarios, such as transaction signing, certificate authorities, or key management systems, the latency of a signing operation is paramount. Ringtail's design ensures that the most time-sensitive part of the process – the online interaction – is as lean and fast as possible. This minimizes the window of opportunity for attackers during active signing and improves the responsiveness of systems relying on threshold signatures. Defenders should prioritize solutions that minimize online rounds and communication, especially for geographically dispersed teams or cloud-native applications where WAN latency is a major factor.

Thirdly, the distributed trust model inherent in threshold signatures, coupled with Ringtail's post-quantum security, significantly enhances resilience. By ensuring that no single server or individual holds the entire secret key, the scheme mitigates risks associated with single points of compromise, insider threats, or key exfiltration. Even if an adversary compromises T-1 parties, the secret key remains safe, making it much harder to forge signatures. This distributed security posture is a fundamental defensive strategy that Ringtail makes more robust against future computational threats.

Finally, the detailed evaluation, particularly the WAN experiment, provides valuable insights for system architects. The finding that network latency dominates local latency in distributed settings reinforces the strategic importance of choosing cryptographic protocols with minimal rounds. When evaluating and deploying threshold signature solutions, defenders should not only look at cryptographic strength but also at the round complexity and online communication costs, as these directly impact the system's performance and availability in a geographically distributed operational context. This information can guide infrastructure design and protocol selection to ensure optimal security and operational efficiency.

Key Takeaways

• Ringtail is a practical, two-round post-quantum threshold signature scheme, directly addressing NIST's call for such solutions based on standard lattice assumptions.
• It achieves provable security from well-established Module LWE and Self-Target CIS assumptions in the classical random oracle model.
• The scheme demonstrates excellent online performance, with low latency and minimal communication (10.5 KB for 1024 parties), making it highly efficient for real-time signing operations.
• Despite its high offline communication costs (~600 KB), the two-round structure is critical for performance in Wide Area Network (WAN) deployments, where network latency significantly outweighs local computation.
• Ringtail provides a robust distributed trust model, ensuring that the secret key remains secure even if T-1 parties are compromised, enhancing resilience against various attack vectors.
• Future work aims to reduce the substantial offline communication complexity and enhance security guarantees, such as achieving adaptive or UC security.

About the Speaker(s)

The talk "Ringtail: Practical Two-Round Threshold Signatures from Learning with Errors" was presented by Darya Kaviani. She is part of a collaborative team of researchers who authored the paper, including Cecilia Boschini, Russell W. F. Lai, Giulio Malavolta, Akira Takahashi, and Mehdi Tibouchi. While specific affiliations and titles for all speakers were not detailed in the transcript, Darya Kaviani delivered the presentation, outlining the technical intricacies and practical implications of the Ringtail scheme. Their collective work contributes significantly to the field of post-quantum cryptography, particularly in the domain of threshold signatures.