This is the third 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 Sharing and Quorums and Threshold Signature Schemes), I described why key protection alone is not enough for protecting cryptocurrencies, and why the real problem that 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.
Refresh or proactive security – preventing gradual theft
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.
We now briefly describe how refresh can be carried out. It seems difficult, since how can we annul the value of a share from a previous interval? However, it is actually quite simple. (I just learned that in American English “quite simple” would mean “very simple”, whereas in Australian and British English it would mean “fairly simple” or “moderately simple”. Given my Australian roots, I mean the latter.) 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 grequires an MPC protocol run between the parties, but this can be done efficiently.
User replacement – threshold signing in business environments
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 any more). 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.
Coming up next
In the next blog post, I will compare the threshold signing / MPC approach to multisig and hardware-based approaches for protecting cryptocurrency. I note that there will still be a few more posts describing the technology. However, after that, I will pull it all together to show how one can use this approach to build a general platform for cryptocurrency protection that answers current business and security needs.