Threshold Signature Schemes (TSS) and their applications in MPC-based wallets

Threshold Signature Schemes (TSS) represent a significant advance in modern cryptography, allowing multiple parties to work together to sign transactions without any of them having full access to the private key. This approach ensures that even if one party is compromised, the security of the system remains intact. By eliminating the risk of a single point of failure, TSS strengthen both the privacy and resilience of the system. They are therefore ideal for applications such as Multiparty Computation (MPC)-based wallets and other self-custodial systems where security and trust in multiparty collaboration are essential.

Introduction to TSS

A Threshold Signature Scheme (TSS) is based on splitting a private key into multiple parts using secret sharing techniques. To generate a valid signature, a minimum number of these parts, known as the threshold, must be combined. This approach ensures that only an authorized subset of participants can approve transactions or messages, thereby distributing responsibility and ensuring that no single entity has full access to the private key.

The use of TSS is particularly relevant in the context of multiparty computation (MPC), which allows multiple participants to perform collaborative computations on data without exposing their private inputs. In private key management, TSS enhance security by distributing keys among multiple participants, mitigating the risks associated with the compromise of a single entity and strengthening the integrity of the system. This distribution makes TSS systems ideal for applications that require distributed collaboration and robust security, ensuring that no single party has full control over the private key.

In this article, we will explore the basics of Threshold Signature Schemes (TSS), as well as their advantages and disadvantages. We will discuss practical applications and advanced variations such as Threshold Ring Signatures (TRS), Schnorr signatures, and FROST protocol, which are fundamental to signature aggregation in the distributed ledger technologies ecosystem.

Threshold Signature Scheme (TSS) concepts and signature procedures

Secret Sharing

Secret sharing consists of dividing a secret (e.g., a private key) into multiple parts that are distributed to multiple participants. Only an authorized subset of these participants can combine their parts to reconstruct the complete secret. This strengthens the security of the system because no single party has full access to the secret, reducing the risk of compromising all information if one part is compromised.

Threshold Scheme

A threshold scheme specifies the minimum number of participants (K) required to reconstruct a secret or perform an operation, such as signing a transaction. If this threshold is not met, the secret cannot be accessed and the transaction cannot be performed. This provides resistance to partial compromises, since the attacker must compromise enough parts of the threshold to gain access.

Distributed Key Generation (DKG)

The Distributed Key Generation (DKG) process allows a group of (N) participants to jointly generate a public and private key pair. No participant has full access to the private key, eliminating the risk of a single point of failure. Only an authorized group can use the distributed parts of the private key to digitally sign.

Lagrange Interpolation

This mathematical technique allows the fractions of a secret (as parts of a private key) to be combined and reconstructed without having to collect all the distributed parts. In TSS schemes, Lagrange interpolation is essential to aggregate the partial signatures generated by the participants into a complete signature without compromising the efficiency or security of the system.

Signature process in Threshold Signature Schemes

1. Distributed Key Generation (DKG): The system’s public and private keys are generated in a distributed manner among the N participants, preventing any single entity from having full control over the private key. Each participant receives a fraction of the private key through a secret sharing scheme, such as Shamir’s Secret Sharing or Blakley’s Secret Sharing.
2. Signature generation: To sign a message or transaction, at least K participants (the defined threshold) must generate a partial signature using their portion of the private key. Each of these participants uses its portion of the secret without sharing it with the others.
3. Signature aggregation: The partial signatures generated by the K participants are combined using Lagrange interpolation. This process aggregates the partial signatures into a complete and valid signature that represents the cooperation of the participants.
4. Verification: The final signature is verified using the group’s public key, similar to how any standard digital signature is verified. Anyone can verify the validity of the signature without knowing the individual private parties.

Why should K be smaller than N?

• Fault tolerance: If K = N, the system would depend on the participation of all members, eliminating the ability to tolerate failures. By setting K < N, the system can continue to operate even if some participants are unavailable.
• Trust distribution: The goal of thresholding schemes is to prevent a single individual from controlling the system. K < N ensures that only an authorized subset can act, thereby enforcing trust distribution.

Benefits of Threshold Signature Schemes in the DLT industry

• Efficiency: You only need one signature to validate transactions, speeding up the process and reducing network load.
• Enhanced security: Distribute signature authority, minimizing the risk of a single point of failure and protecting signature integrity.
• Decentralization: Encourage an environment without a single point of control, improving security and fostering trust among users.
• Fault tolerance: Maintain functionality even if some participants are unavailable, ensuring business continuity.
• Scalability: Efficiently handle the growth of participants without degrading performance, which is critical as DLT applications grow.
• Reduced transaction size and cost: Generate lightweight transactions that enable faster verification times and lower fees.
• Easily change key shares: Enables distributed key management without complicated on-chain transactions, improving security.
• Operational flexibility: Allow configurations to be adjusted without exposing the private key, making it easier to add new signatories.
• Interoperability: Integrate with multiple platforms and protocols, extending their functionality and usefulness within the distributed ledger technology ecosystem.
• Resistance to censorship attacks: They require the cooperation of multiple participants, making it difficult for a malicious actor to censor transactions.
• Improved key management: Private key distribution increases resilience to loss while maintaining security.
• Auditing and transparency: Facilitates audits and enables tracking of participation in transactions, which builds trust.

Practical applications

• Distributed consensus: Optimizes consensus mechanisms by allowing a subset to jointly sign and validate transactions.
• Multiparty Computation (MPC): Ensures the integrity and authenticity of shared computations without revealing private inputs.
• Decentralized Autonomous Organizations (DAOs): Secures voting processes, promoting transparency and accountability in decision making.
• Cross-chain transactions: Enhances the security of transactions between networks by requiring validations in both, ensuring integrity and trust in the transfer.
• MEV mitigation: Ensures transactions are executed fairly by preventing manipulation by validators.
• Enhanced Multisig wallets: Replaces traditional multisig applications, providing greater efficiency and lower costs when performing operations outside the main system.
• Trusted configurations: Facilitates the creation of standard parameters with a Distributed Key Generation (DKG) phase.
• Electronic voting: Provides a secure and cost-effective approach to anonymous vote tabulation
• Distributed Identity Management systems: Allows multiple issuers to collaborate on credential issuance, enhancing security and privacy.
• Product approvals: Facilitates collaborative validation of critical products in regulated industries.

Challenges and considerations

• Complexity: Implementation can be complicated and requires secure cryptographic protocols, which can introduce vulnerabilities.
• Performance: Can introduce overhead in high-transaction environments, and optimization without compromising security is essential.
• Key management: The security of the system depends on the secure management of key components, which must be properly stored.
• Trust assumptions: Effectiveness depends on the honesty of a subset of participants, which can be difficult to guarantee.
• Standardization and interoperability: Lack of standards can make integration with existing platforms and services difficult.
• Evolving security landscape: Must adapt to new threats and vulnerabilities to remain secure and reliable.

Attacks and exploit history of Threshold Signature Schemes

Threshold Signature Schemes (TSS) have proven to be vulnerable to various types of attacks over time. Some of the most prominent attacks are presented below.

The Forget-And-Forgive attack targets the multiparty re-sharing protocol added to a key generation and Threshold Signature Schemes implementation of the Fast Multiparty Threshold ECDSA (Elliptic Curve Digital Signature Algorithm) with fast, trustless setup. The key update operation is primarily intended to prevent an attacker from successively compromising all systems and ultimately recovering the entire private key. The associated protocol is run periodically to maintain access to the funds locked under the shared public key.

The Lather, Rinse, Repeat attack focuses on the two-part implementation of ECDSA designed for commercial deployment and production use. Similar to Threshold Signature Schemes in general, secure deployment of wallets using two-part signatures requires periodic updates of shares, such as after each transaction. This attack is conceptually similar to the Forget-And-Forgive scenario, although the underlying protocol is different.

The Golden Shoe attack targets the threshold ECDSA scheme implementation of the Fast Multiparty Threshold ECDSA method, but focuses on a different subprotocol than the one attacked in Forget-And-Forgive. The vulnerability is in the multiplicative-to-additive (MtA) subprotocol, which converts secret multiplicative entries into secret additive entries. In this scenario, if Mary owns a and David owns b, such that the shared secret is x=ab modq , the protocol determines α and β that satisfy α+β=x . This type of protocol is commonly referred to as “MtA” in specifications and implementations. In addition, the MtA protocol requires zero-knowledge proofs, which means that each party must prove the validity of its message without revealing any additional information.

These attacks highlight the need to secure Threshold Signature Schemes protocols and to continuously improve security practices in their implementation. Although Threshold Signature Schemes offer significant advantages, they also require constant attention to mitigate risks and vulnerabilities.

TSS-based wallets with MPC

Wallets using Threshold Signature Schemes combined with Multiparty Computation (MPC) provide an advanced distributed security architecture.

General operation

Key generation in these wallets is done using Distributed Key Generation (DKG). Instead of being generated centrally, each participant holds a portion of the key. To derive the public key and sign transactions, the number of participants defined by the threshold must cooperate.

A unique feature of TSS wallets is private key rotation. This process allows private keys to be changed without having to change public keys or addresses in distributed systems, thanks to a proactive secret sharing protocol. This provides an additional layer of security as old keys can be deleted without affecting the functionality of the system.

From a temporal security perspective, an attacker would have to compromise multiple locations or devices simultaneously to gain access to the private keys. Since the combination of the pre- and post-rotation secrets would provide no additional advantage, the protection against attack attempts is strengthened.

Possible architectures

• TSS outsourcing: In this model, key generation and management are outsourced to servers that perform the computations on behalf of the user. While this approach alleviates the computational burden, it also introduces the risk of collusion between servers.
• Multiple proprietary devices: The user distributes pieces of the key among multiple owned devices, such as cell phones, laptops or IoT devices. While this approach increases security, it requires multiple devices to be online for transactions.
• Hybrid model: Combines parts distributed between external servers and user devices, offering a balance between control and ease of use.

Recoverability and adaptability

MPC-based TSS wallets can incorporate robust recovery mechanisms that allow users to regain access to their funds in the event of loss. These solutions are adaptable to different security and usability configurations, depending on the user’s needs.

Threshold Signature Schemes (TSS) and their variants: TRS, Schnorr and FROST.

Within the MPC-based wallet ecosystem, Threshold Signature Schemes (TSS) play a key role in allowing multiple parties to collaborate on signature transactions without exposing full private keys. However, recent innovations in cryptography have taken this concept to a new level, including Threshold Ring Signatures (TRS), as well as optimizations through Schnorr signatures and the FROST protocol, paving the way for more efficient and secure implementations.

Threshold Ring Signatures (TRS)

Threshold Ring Signatures (TRS), discussed in the paper “Threshold Ring Signatures: New Definitions and Post-Quantum Security“, represent an evolution of the threshold signature concept by incorporating an anonymity layer. Unlike standard ring signatures, where any member of the group can sign, TRSs require the participation of a minimal (threshold) subset of signers in the generation of the signature. This approach provides anonymity within the group (ring) while ensuring that at least a minimum number of parties participate in generating the signature. This is useful in applications where both anonymity and distributed participation are required. However, unlike MPC schemes, the focus of TRSs is less on secure collaborative computation and more on signer privacy. Therefore, TRSs could complement self-custodial solutions where multiple parties need to collaborate without compromising their anonymity, although they do not perform exactly the same cryptographic security function as MPC wallets.

Integration with Schnorr Signatures: Optimization for Privacy

Schnorr signatures have gained popularity due to their simplicity, efficiency, and ability to generate more compact signatures than other traditional schemes such as ECDSA. When integrated with TSS, Schnorr signatures provide a higher level of privacy by allowing multiple parties to generate a unified signature without revealing the identities of the signers involved.This combination is particularly valuable in the MPC wallet arena, as it reduces the transaction footprint of distributed ledger technologies and enhances the privacy of participants. In addition, Schnorr signatures are ideal for implementing signature aggregation, which allows the signatures of multiple parties to be combined into a single signature.This not only optimizes the use of system resources, but also makes it more difficult to trace the identities of signers, significantly improving privacy in collaborative transactions. For TSS-based wallets, this combination provides a robust and private solution that integrates seamlessly into platforms that require high efficiency and security.

FROST: A more flexible approach to threshold signatures

The Flexible Round-Optimized Schnorr Threshold Signatures (FROST) protocol is a recent innovation that optimizes the implementation of Schnorr-based threshold signatures. Unlike traditional Threshold Signature Schemes, FROST allows threshold signatures to be performed more efficiently and with fewer rounds of communication between participants. This feature is particularly relevant in the context of MPC wallets, where the speed of signature generation is critical for the storage and management of digital assets. Key benefits of FROST include:

• Reduced interactions: By minimizing communication rounds, FROST reduces latency and improves scalability, which is essential for fast and secure transactions.
• Flexibility: FROST adapts to different escrow scenarios, from MPC wallets to smart contracts, providing a versatile solution for distributed key management.

This ability to coordinate signatures with less interaction between parties is key to improving the usability of MPC-based wallets, providing a better user experience without compromising security.

Conclusion

Threshold Signature Schemes (TSS) and multiparty computation (MPC) have emerged as fundamental elements for advanced security in digital asset management. Unlike traditional wallets, these technologies distribute key generation and control among multiple participants, eliminating the risk of a single point of failure. The use of Threshold Secret Sharing ensures that sensitive information can only be accessed when a minimum number of participants collaborate, while Distributed Key Generation ensures that no single party has full access to the private key, enhancing confidentiality.

In addition, recent innovations such as Threshold Ring Signatures (TRS) provide additional anonymity by requiring the participation of a subset of signers, which is critical in systems that value both privacy and distributed collaboration. Schnorr signatures, meanwhile, improve efficiency and privacy by allowing multiple parties to create a single signature without revealing the signers’ identities. The FROST protocol further optimizes signatures per threshold, reducing latency and improving scalability in distributed systems.

The evolution of these schemes not only enhances security, but also improves the usability of MPC-based wallets by providing flexible solutions for key rotation, failover protection, and secure recovery in the event of loss. This modular and resilient approach is essential for the efficient and secure storage of digital assets in an ever-evolving distributed environment.

In the next articles we will look at the secret sharing schemes: Shamir’s Secret Sharing (SSS) and Blakley’s Secret Sharing (BSS), which share a secret, such as a private key, between multiple parties using different methods.

Resources:
[1] Mmasmoudi (medium) –  An overview of multy party computation, threshold signatures wallets
[2] Immunebytes – The power of threshold signatures
[3] Panther protocol – Tthreshold cryptography an overview
[4] Scryplatform (medium) – Threshold signatures
[5] Blockandcapital – MPC wallets
[6] Threshold Signatures Schemes with Private Accountability
[7] Threshold Ring Signatures
[8] Schnorr signatures
[9] FROST
[10] BLS (Boneh-Lynn-Shacham)

FAQs

At Block&Capital, we strive to create an environment where growth and success are accessible to all. If you’re ready to take your career to the next level, we encourage you to join us.