Why is the Threshold Signature Scheme better than Multi-Sig and Shamir’s Secret?

Dr. Jay Prakash

by

April 15, 2024

A challenge in the usage of digital signatures is the management of private keys whose leakage to malicious parties could harm the validity of the current platforms. Therefore, the storage and management of the key should be maintained carefully. Delegating the key management to a trusted party does not overcome the problem. Although the trusted party provides a better protection mechanism, a single point of failure is still an issue.

Recently, researchers proposed a solution to the key management problem in using an old cryptographic technique, secure multiparty computation. The concept was first introduced by Andrew Yao as a secure computation between two parties. In this work, Yao uses the Millionaires’ problem as an example to explain how the two parties can decide who is richer without revealing their wealth to each other. MPC enables a group of parties who do not necessarily trust each other to perform operations on their private data without revealing any information about their data.

What is TSS?

Threshold cryptography is an area of MPC which allows the sharing of a private key among multiple parties. In a threshold cryptography scheme, the private key can be revealed only when a specific subset of parties combines their key shares. Usage of a threshold signature scheme thwarts the single point of failure attacks in key management.

Threshold signatures are not the only available solution for the key management problem. An alternative mechanism is the multi-signature approach, where a transaction is signed by multiple parties individually using their signing keys. Similar to threshold signatures, multi-signature prevents the single point of failure attack.

Currently the most common signing scheme (in transaction volume) in blockchain applications is ECDSA secp256k1, followed by Ed25519, recent works lead to more efficient threshold signing schemes for Schnorr-like signatures (such as EdDSA) and even ECDSA signatures. Some recent projects, including ETH 2.0, are using BLS signatures, which make TSS relatively easy to construct thanks to their aggregation properties.

Multi-sig

As we mentioned : Threshold signatures are not the only available solution for the key management problem. An alternative mechanism is the multi-signature approach, where a transaction is signed by multiple parties individually using their signing keys.

However, the multi-signature approach requires to perform signature verification multiple times since each signer party’s signature needs to be validated. On the contrary, using threshold signing, multiple parties can produce a single signature that can be validated efficiently. Another drawback of the multi-signature approach is that it should be performed on-chain while threshold signatures can be operated off-chain.

But a clever trick: We can use a multi-signature method with aggregated signatures. Signature methods such as BLS enable you to merge n signatures into a single signature. It should be noted that it is currently substantially slower than common signature systems like ECDSA and EdDSA, implying that there must be a trade-off between performance and size.

So far, maintaining a set of n public keys is required in order to verify a signature. Distributed Key Generation (DKG) allows a group of participants to work together to create a key pair and perform signing procedures. This is similar to SSS, however there is never a single point of failure. DKG is therefore a Multi-Party Computation (MPC) algorithm.

Shamir’s Secret Sharing

An essential primitive to perform MPC among a set of parties is secret sharing. In secret sharing, secret data can be shared among n parties such that any subset of at least t + 1 parties can reconstruct the secret, but the subsets with t and fewer parties cannot learn anything about the secret. Such a scheme is called (t, n)-threshold scheme. Shamir’s scheme is a well- known scheme for secret sharing, which is based on polynomials.

Note that SSS has many many variants, for example VSSS allows participants to verify that malicious shares are not being used, and PSSS allows participants to proactively rotate their shares.This is not ideal, as there is a limited time in which Alice will be the single point of failure once more.

Attacks/ Exploits History of TSS

The Forget-And-Forgive Attack

This attack targets (Multi-Party Reshare) the reshare protocol added to an implementation of the key generation and threshold signature from Fast multiparty threshold ECDSA with fast trustless setup.

Such key share refresh operation primarily aims to prevent an attacker to consecutively compromise all systems and ultimately recover the full private key.The associated protocol would be run at regular time intervals, while maintaining access to the funds locked under the joint public key.

The Lather, Rinse, Repeat Attack

This attack targets ( Two-Party Reshare) an implementation of two-party ECDSA aimed for commercial deployment and thus production usage. As in general TSS, a secure deployment of wallets with two-party signature requires period share refresh, for example after every transaction. This is conceptually similar to our first scenario (that of the Forget-and-Forgive attack), but the underlying protocol is different.

The Golden Shoe Attack

This attack targets (MtA Share Conversion) an implementation of the threshold ECDSA scheme from Fast multiparty threshold ECDSA with fast trustless setup. but a different one than the one attacked in The Forget-And-Forgive Attack, and a different subprotocol.

The vulnerability lies in the share conversion subprotocol, a two-party protocol that transforms secret multiplicative inputs to secret additive inputs. That is, if Alice holds a and Bob holds b such that the shared secret is x=ab modq ,the protocol determines α,β that satisfy α + β = x. This kind of protocol is commonly referred to as “MtA” (multiplicative to additive) in specifications and implementations.

Furthermore, the MtA protocol requires zero-knowledge proofs, so that each party demonstrates the validity of its message.

And what is the correct way to implement & integrate?

In addition to potential protocol attacks, TSS deployments may suffer from implementation flaws, be it logical bugs coming from a misimplementation of the protocol, or software flaws resulting for example from parsing bugs. The software used in real applications can be an in-house implementation, potentially relying on existing open-source code, or a commercial solution.

In order to minimise the risk, an organisation creating and deploying such protocols may consider the following recommendations:

  • Create implementations whose code closely follows the specifications on paper, referring to specific sections or lines via source code comments, and using similar notation and variable names. This facilitates validation, testing, and auditing of the code.
  • Closely pay attention to all the constraints described in the paper, especially when it’s about proofs of correctness. Sometimes such constraints are only loosely defined, and another paper is referred to. Sometimes the constraints are implicit and considered “obvious” by the authors, or mentioned somewhere else in the paper.
  • Identify any gaps between on-paper and real deployment, in terms of adversarial model, trust assumptions, communication synchronicity, and so on.
  • Ensure that there are controls to validate proper execution of the protocol and correct- ness of the values received.
  • Upon aborting the protocol, make sure that it gracefully fails and that no data is leaked (unlike in our second attack).
  • Be careful when composing different protocols, either sequentially or as subprotocols
  • When performing security audits, you may consider hiring different teams for the pure cryptographic/protocol aspects, and for the code safety. Prefer teams demonstrating concrete experience with the protocol to be audited, and ideally people who already wrote similar code.

Dr. Jay Prakash

CEO, Co-Founder

Twitter
Linkedn
Follow us on