listen to this article:

Additional Properties of Threshold Signing – MPC for Cryptocurrency Protection - Unbound Security Blog

This is the third Cryptocurrency Protection blog in a series aimed at explaining the growing use of MPC and threshold signing to protect cryptocurrencies.

In the first two blog posts in this series (Shamir Secret Shaing and Quorums and Threshold Signature Schemes), I described why key protection alone is not enough for protecting cryptocurrencies, and why the real problem which needs to be solved is protection against fraudulent key usage.

I then described what secret sharing and threshold signatures are, and how they can be used to enforce quorum authorization so that only an authorized set of parties can generate a signature.

In this blog post, I will describe additional important properties of threshold signing.

Preventing Adversary Breach of Authorized Quorum

As we have seen, in a threshold signature scheme, each party holds a share of the private key, and an MPC protocol is used to compute the signature itself. Recall that any authorized quorum can compute a signature, and thus the combination of the shares of any authorized quorum defines the private key (although the shares are never brought together, even for signing).

Given the above, if an adversary slowly breaches (or corrupts) parties holding shares, then over time it can steal enough shares to reconstruct the private key. The aim of refresh is to achieve proactive security, which means that an adversary has to simultaneously breach an authorized quorum in order to learn anything. To be more exact, a fixed interval of time is defined (e.g., every hour) and the adversary has to breach a full authorized quorum within the interval, or it will learn nothing.

In particular, if the adversary breaches a full quorum, but only half in one interval and the other half in the next interval (or even 90% in one interval and 90% in a later interval, with overlap), then it will still learn nothing about the private key. This is an important feature of threshold signature schemes, as it is much harder to breach a full quorum in a single interval than to slowly steal shares over time.

How is Refresh Carried Out?

It seems difficult, since how can we annul the value of a share from a previous interval?

Well, it is actually quite simple. Lets make a brief recap.

Recall that an m-out-of-n secret sharing of a private key k is generated by defining a random degree-(m-1) polynomial f such that f(0) = k, and the i’th party (for i = 1,…,n) receives the share f(i). Recall also that any m points on a degree-(m-1) polynomial suffice for reconstructing the polynomial and thus the secret. This implies that if the parties hold the same shares over time, then an attacker slowly stealing share after share would be able to obtain the secret.

In order to prevent this, we want the parties to generate a new sharing of the same secret with a new polynomial at the end of each interval, so that previous shares are useless (since previous shares belong to a different polynomial, they are meaningless after this operation).

Without going into exactly how, the most elegant method for generating this new sharing with a different polynomial is for the parties to jointly generate a sharing of a random degree-(m-1) polynomial g such that g(0) = 0. Then, given g(i) and f(i), the i’th party locally computes its new share to be f’(i) = f(i) + g(i).

The reason that this works is that the new sharing is via the polynomial f’(x) = f(x) + g(x), and by definition it holds that f’(0) = f(0) + g(0) = k + 0 = k. We remark that generation of the polynomial g requires an MPC protocol run between the parties, but this can be done efficiently.

Managing Quorums with Employee Turnover

Threshold signing is a powerful tool, but deploying it in practice requires considering many functional issues that are sometimes missed.

One example of this is that in a business environment, the parties holding the key shares (who are employees) may change over time. New employees join the company and need to be added to quorums, and existing employees leave the company and their key shares need to be somehow revoked (since we don’t want such a person to be able to approve transactions anymore). This functionality is necessary since transferring cryptocurrency to new addresses (protected by new keys) every time an employee joins or leaves the company would be operationally unacceptable.

Given the tools that we have used above, these operations are actually really easy. First, adding a new employee to an existing threshold group involves simply providing them with their share f(j), where j denotes their identity (or number). This can be done quite easily in MPC using Lagrange interpolation to f(j).

Likewise, removing an employee can be easily achieved by just running the above-described refresh operation amongst the other employees. After this operation, the removed employee’s share is completely meaningless, and thus their authorization rights are effectively revoked.

In the next blog post, I will compare the threshold signing / MPC approach to multi-sig and hardware-based approaches for protecting cryptocurrency.

More blog posts in this Cryptocurrency Protection series: