FROST's distributed key generation involves N parties each creating a secret polynomial, and sharing evaluations of this polynomial with other parties to create a distributed FROST key.
The final FROST key is described by a joint polynomial, where the x=0 intercept is the jointly shared secret s=f(0). Each participant controls a single point on this polynomial at their participant index.
The degree T-1 of the polynomials determines the threshold T of the multisignature - as this sets the number of points required to interpolate the joint polynomial and compute evaluations under the joint secret.
T parties can interact in order to interpolate evaluations using the secret f[0] without ever actually reconstructing this secret in isolation (unlike Shamir Secret Sharing where you have to reconstruct the secret).
We wonder, is it possible to change the number of signers N, and change the threshold T after keygen has been completed? And importantly, can these changes be made by with a threshold number of signers, as opposed to requiring the consent of all N signers? (Imagine losing a FROST secret keyshare and wanting to reissue another!).
Much of our investigation has led to ideas which have already been fleshed out in the secret sharing literature.
Note the following methods mentioned here are not explicit, and we still need to read into which are proven secure and most appropriate for our purpose, each may come with caveats.
- Decreasing N: Removing a Signer
- Decreasing T: Reducing the Threshold
- Increasing N: Adding a Signer
- Increasing T: Larger Signing Threshold
We can turn a t of n into a t of (n-1) if we can trust one user to delete their secret keyshare (make sure n>t!).
If we can not reliably trust the party to delete their secret keyshare, we can further render the revoked secret keyshares incompatible with future multisignature participants.
We can do this using some form of proactive secret sharing:
Shares are periodically renewed (without changing the secret) in such a way that information gained by the adversary in one time period is useless for attacking the secret after the shares are renewed
See Proactive Secret Sharing Or: How to Cope With Perpetual Leakage and Proactive Secret Sharing on Wikipedia.
Overview - we can create a new joint polynomial with the same joint secret, and then ask all n-1 participants to delete their old secret keyshare (point on that particular old joint polynomial). If t-1 parties of n-1 feign deletion and collude then they could still sign with the removed party.
To create a new joint polynomial with the same public key and joint-secret we redo keygen with n-1 parties. Each participant uses the same first coefficient in their original keygen polynomial, and other terms random. This will produce a polynomial with the same joint secret, but all other points different and incompatible with previous keyshares.
We can decrease the threshold by sharing a secret of a single party to all other signers, allowing every other party to produce signature shares using that secret keyshare.
This effectively turns a t of n into a (t-1) of (n-1). We can keep n the same if we also know how to increase the number of signers (below), as we can issue a brand new secret keyshare and distribute it to all the other signers; going from a t of n to a (t-1) of n.
In more adversarial multisig scenarios, steps could be taken to manage some fair exchange of this secret to ensure it reaches all participants.
Backing up each individual secret keyshares is advised -- but backups are certainly not the same as issuing an additional party who has the power to contribute an independent signature share towards the threshold. Issuing new signers is slightly more involved.
The idea is that we can securely evaluate the joint polynomial at further indexes for additional participants. We do not want to rely on all n participants being present since this is useless in the case of a lost signer.
We can use an enrollment protocol to add a new party without redoing keygen.
See Novel Secret Sharing and Commitment Schemes for Cryptographic Applications and A Survey and Refinement of Repairable Threshold Schemes - Section 4.1.3
Enrollment protocols allow us to repair (recover) or add a new party without redoing keygen. A threshold number of parties collaborate to evaluate the joint polynomial at a new participant index, and securely share this new secret keyshare to the new participant.
Whenever we want to add a new party at some new participant index, T parties each use their secret keyshare point to evaluate the joint polynomial at some new index. Each party contributes evaluation shares from their basis polynomial, and weighs them using the appropriate lagrange factor to ensure the sum of these pieces will lie on the joint polynomial. By securely sharing these with the new party, the new party sums them to form a secret keyshare and can now participate in FROST signing.
If provided with the original commitment polynomials used during keygen, this new party can also verify that their received point does indeed lie on the joint polynomial (though perhaps there could be some trickery with lying about commitment polynomials).
Proof of concept recovery of a signer, and enrollment of a new signer (without MPC communication)
This method may be more complex and less flexible than an enrollment protocol, though perhaps easier to implement and prove secure. Suppose we want the option of later issuing K extra signers to join the multisig.
Following standard keygen where each P_i evaluates their secret scalar polynomial f_i from 1 to n, we use a a modification where each party also evaluates from n+1 to n+k. Each party calculates k extra secret shares which can later be used to issue a new signer.
To add a new signer to the FROST multisignature later on, they must receive these secret shares from every other keygen participant. Meaning that we require all N signers to be available and agree to add the new signer. This is of no use in the scenario of a lost FROST device or uncooperative signer!
So why not distribute these secret shares for redundancy? We can not trivially share these secret shares around, since we may risk prematurely creating additional signers if one party were to obtain shares at some index from all signers.
Instead, we can shamir secret share the secret shares -- reintroducing our threshold T! Let's call these shamir shares "fragments" of secret shares, rather than shamir shares-of-shares.
The procedure would look like this:
- Each party evaluates their scalar polynomial at K extra indexes, creating K extra secret shares.
- Each party then takes these K scalars and uses shamir-secret-sharing to fragment them up into
Npieces with recovery thresholdT. This gives a K by N array of fragments.- As each party P_i goes to send share
jto partyj, they additionally send thejth column of their fragment array for storage.
To issue a new signer (party n+1), we need to do is get T signers to send all the fragments they hold which belong to index n+1. We recover at least T x N fragments allowing us to recreate N secret shares which we then collect into a long lived secret keyshare, resulting in a new signer with their own point on the joint polynomial.
Exploratory implementation (without shamir sharing)
Increasing the threshold seems more difficult than redoing keygen, it would require the group the somehow increase the degree of the polynomial, and trust everyone to delete the old one.
Thanks for reading, hope this makes you as excited about FROST as we are!
Please leave any comments/ideas/whatever below.
Thanks, as always, to @LLFourn for his feedback, ideas, and knowledge of existing literature!
I've recently been researching an interesting security issue with this technique (i.e. Herzberg PSS). Herzberg relies on the adjacent assumption (i.e. if a party is corrupted during an update phase, it is corrupted in both time periods adjacent to that update phase). However, subsequent papers have looked at the consequences of removing this assumption.
When we remove the adjacent assumption, there's an issue when we secret share polynomials with a constant coefficient of 0. The issue is that we are giving all the participants an extra share, namely, the point at (0,0). So an attacker that controls t-1 signers can compute the update polynomial, and with that polynomial, the attacker can update any share from the previous time period to a share in the new time period. This allows an attacker who controls t-1 signers in the update phase, and also has 1 share from another signer in the previous time period, to compute the secret.
This issue was first identified by Nikov and Nikova in their paper "On Proactive Secret Sharing Schemes," however, they did not provide a solution. An interesting solution to this issue was published by Xia et al. in their paper "Provably Secure Proactive Secret Sharing Without the Adjacent Assumption."
The Xia solution involves creating a higher degree update polynomial (so that the (0,0) point is no longer sufficient for a t-1 attacker), and then after aggregating the shares, truncating the polynomial back down to t-1. Polynomial truncation might also provide a method for reducing the threshold generally, although that application is not discussed in the paper.
The truncation protocol builds on a scheme by Ben-Or et al. There's a paper called "Dealer-Free Dynamic Secret Sharing Schemes with Unconditional Security" that walks through an example of the Ben-Or scheme (see Example 2, steps 8-11 in Section 5.2).
The Xia paper modifies the scheme such that the projection matrix includes some random vectors, and it demonstrates a security issue if this modification is not made. However, the Xia paper is extremely terse in describing how to generate the random vectors: "generated in a distributed fashion and shared among the parties," citing to Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. J. Cryptol. 1, 51–83 (2007), which defines a DKG scheme similar to FROST.
However, I haven't been able to figure out precisely how to use a DKG to produce the random vectors. Unlike the Ben-Or scheme, it seems like the projection matrix should not be fully public, otherwise why use a DKG to produce the random vectors? The parties can compute T = B^-1 * P * B without revealing P but since B is public, P can be derived from T. It seems like their must be a way to compute R = S * T without revealing T, but I'm not sure if this is the right approach and I haven't been able to figure out how to get that to work.