Allow signers to change group threshold by updating shares

[conduition]

There is this interesting protocol which allows a group of at least $t$ shamir shareholders (or FROST signers) to compute updated shares which correspond to a new threshold $t'$.

It requires that only $t$ signers be online, but all $n$ signers must at least be able to receive messages asynchronously while offline, to update their shares to have threshold $t'$. Of course it wouldn't stop a malicious subset of shareholders from holding onto their old shares which are valid for the original threshold $t$.

Is this of interest? Would love to work on this.

Here's a short description, omitting verifiable commitments.

• Let $f(x)$ be the joint secret polynomial. In the FROST paper this is referred to as $F_1(x)$.
• Let $P_i$ be the participant at index $i$. Each $P_i$ knows a secret share $z_i = f(i)$.
• Let $S$ be a set of $t$ or more share indexes, held by online participants.
• Let $\gamma_i^X$ be the lagrange coefficients for a set of inputs $X$, used to evaluate a polynomial at $0$:

$$\gamma_i^X = \prod_{\substack{j \in X \\ j \ne i}} \frac{0 - j}{i - j}$$

1. Each online participant $P_i : i \in S$ samples $t' - 1$ random coefficients $\{a_1, a_2, ..., a_{t' - 1}\}$. This defines the polynomial

$$g_i(x) = z_i + \sum_{j=1}^{t'-1} a_j x^j$$

In other words, each $g_i(x)$ is a random degree $t' - 1$ polynomial with $z_i = f(i)$ as the constant term.

2. Online participant $P_i$ sends $g_i(j)$ to every participant $P_j$ for every $j \in \{1...n\}$. It is important that the offline participants can receive these messages asynchronously, as they will need to update their shares before their next interaction with any shareholders in $S$.

3. $P_i$ receives all $\{g_j(i)\}_{j \in S}$.

4. $P_i$ computes his new share $z_i'$ as:

$$z_i' = \sum_{j \in S} \gamma_j^S g_j(i)$$

...and erases his old share $z_i$.

5. At recovery time, the shareholders now need a subset $R$ of at least $t'$ shares to recover $f(0)$.

$$ \begin{align} f(0) &= \sum_{i \in R} \gamma_i^R z_i' \\\ &= \sum_{i \in R} \gamma_i^R \left( \sum_{j \in S} \gamma_j^S g_j(i) \right) \\\ &= \sum_{i \in R} \sum_{j \in S} \gamma_i^R \gamma_j^S g_j(i) \\\ &= \sum_{j \in S} \sum_{i \in R} \gamma_i^R \gamma_j^S g_j(i) \\\ &= \sum_{j \in S} \gamma_j^S \left( \sum_{i \in R} \gamma_i^R g_j(i) \right) \\\ &= \sum_{j \in S} \gamma_j^S \cdot g_j(0) \\\ &= \sum_{j \in S} \gamma_j^S \cdot f(j) \\\ &= f(0) \end{align}$$

Effectively, $P_i$ has securely updated their share to an evaluation $f'(i)$ of a new degree $t' - 1$ polynomial $f'(x)$, which maintains the same constant term as $f(x)$ (i.e. $f'(0) = f(0)$ ).

Cost/Benefit

• 🟢 works to increase or decrease the threshold, or even as a way to invalidate old shares without changing the threshold (for proactive secret sharing approaches).
• 🟢 can be repeated indefinitely
• 🟢 requires no cooperation from a trusted dealer
• 🟢 could be modified to be verifiable with the addition of a commitment round using the relevant prime order group generator.
• 🔴 impossible to verify if the old shares were erased
• 🔴 requires asynchronous message queues for offline signers, or requires all signers to be online.

[conradoplg]

This seems pretty cool! But glancing at the reference, wouldn't it be better to protect against active adversaries, and thus use public evaluation / zero addition? (Note that we were already considering implementing zero addition in #245 but I didn't realize it also allowed increasing the threshold).

In any case thanks for opening this, I'll bring this up for discussion with the team

[conduition]

But glancing at the reference, wouldn't it be better to protect against active adversaries, and thus use public evaluation / zero addition?

This section of the paper discusses a specific insecure resharing method which seems different from the one i detailed in OP, which is the method discussed in this section. Need to do some more detailed reading to see if the insecurity proof relates to the protocol i suggested.

Implementing both public evaluation and zero addition would require implementing two separate protocols to enact threshold changes, which would double the work (and complexity). I suspect we could protect against active adversaries by adding a round of commitments and verification. I need to do some more research to see if someone else has already devised a variation of the Lagrange threshold change method which has been proven secure for active adversaries. In the meantime, I'll take a stab at a simple design which might fit the bill and post it here later.

Thanks for the eyes! 😄 Whatever protocol you end up choosing, i'd be happy to help out with the implementation.

[conduition]

here is a description of the resharing protocol with verifiable commitments. That article is effectively a collection of my notes on the subject so take it with a grain of salt (i'm not an expert just a nerd). I'll try to do some more research soon to see if anyone has already done a proof of security that applies to this protocol.

[conduition]

hey all, posting the results of my research here for your consideration. Hope it comes in handy making a choice. As expected, I was definitely not the first to think of this idea, and there is ample support in the literature for using share resharing (with a commitment round) against active adversaries.

I checked into the sources cited by Nojoumian in the paper where he describes the unverifiable version of the resharing protocol (the one i outlined in OP). Looks like although Nojoumian cites a paper on threshold RSA as where he heard about resharing, the idea of redistributing shares using shares-of-shares in this way was first introduced in this paper. The authors of that paper note in Section 6 that the resharing protocol can be extended to be verifiable.

Due to the linear nature, our results easily extend to robust threshold cryptography which is discrete
log based. In several verifiable secret sharing schemes and their application to robust
threshold cryptography based on discrete log, what is being communicated to verify the share
is $f(s_i)$ where f is a homomorphism from $S_i$ to an appropriate group, in general $f$ is applied on
each subshare. This implies that we can talk about a more general share consisting of the secret $s$
and the public $f(s_i)$, i.e. regard the share as $(s_i, f(s_i))$. Due to the linearity of our schemes and
the fact that $f$ is a homomorphism, all formulas apply. This implies that the shareholders in the
redistribution algorithm can give verifable shares $\hat{s}_{i,j}$ of the verifable shares $s_i$. Since $s_j'$
is a linear combination of $\hat{s}_{i,j}$ this results in verifiable shares $s_j'$ or the new access structure $\Gamma'$.
In the limited context of verifiable secret sharing, the results are not restricted to a discrete log setting.

This paper on threshold RSA (specifically sections 3.2 and 4.1) was cited by Nojoumian, and they seem to represent a verifiable secret resharing protocol. They split the resharing conceptually into two steps, which they call 'sum-to-poly' and 'poly-to-sum', in which the $t$ shares are first rendered into shamir shares with the new threshold $t'$ (sum-to-poly), and then those shares are additively combined (poly-to-sum) to give players their new shares.

There is a short note in Section 5 of this paper which also summarizes this. To explain further i would basically be parroting them so let me just quote directly.

The approach of re-sharing the players shares is well known is SSS and it
could be applied to change dynamically the access structure associated with the
scheme. For example let $f(x)$ be $k$-degree polynomial such that $f (0) = s$ and
let every player $P_u$ has a share $s_u = f (α_u)$. Then every player $P_u$ chooses an $\ell$-
degree polynomial $g_u(x)$ such that $g_u(0) = s_u$, i.e. he re-shares his share sending
auxiliary shares $g_u(α_v )$ to player $P_v$ . A set $A$ of at least $k + 1$ good players is
determined. For such a set $A$ there exist constants $r_w$ (which depends only on
$A$, but not on player’s shares) such that $\sum w \in A r_w s_w = s$. Now every player
$P_v$ combines the auxiliary shares he has received to compute his new share,
i.e. $\tilde{s}_u = \sum w \in A r_w g_w(α_v )$. It is easy to check that the new shares correspond to
the same secret $s$ and that the access structure is changed from $(k, n)$ to $(\ell, n)$.
Nearly the same protocol works in the computational secure VSS setting, e.g.
Feldman’s VSS

But by far the most helpful paper was this one by Wong, Wang, and Wing (best trio of names on a paper I've ever seen), which calls the process a verifiable secret redistribution (VSR) scheme. Their VSR scheme is almost exactly the same as the protocol i described on my blog with a few minor adjustments.

This article describes some drawbacks of Wang's scheme:

1. During redistributing the secret from an old $(t, n)$-threshold access structure to a new $(t', n')$-threshold access structure, $\binom{n}{t} - \binom{n-t+1}{t}$ restarts of the secret redistribution phase, in the worst case, are required to eliminate faulty shareholders and complete the secret redistribution phase.

2. The honesty of the dealer and shareholders cannot be verified publicly. Therefore, if an external verifier wants to verify the honesty of the dealer or shareholder, then he must know the produced shares and sub-shares by interacting with the dealer and shareholders. This is not a secure method, because the external verifier may be corrupted by an adversary.

3. Receiver shareholders are assumed to be honest, while they can be corrupted in real-life scenarios.

This paper describes an improvement to Wang's protocol which fixes item (3) by adding a complaint-lodging mechanism.

I'd propose we implement Wang's scheme. We could also consider implementing Gupta's complaint mechanism.

[conduition]

Also worth reading are these slides regarding the "Forget & Forgive" attack on any secret sharing redistribution scheme, namely that at least $t$ shareholders must ACK that they received and computed valid new shares before deleting their old shares, otherwise a griefing attack is possible by a single malicious party.

[conduition]

Just opened a draft PR which implements Wang's VSR scheme: #570 - feedback would be appreciated 🙏

[canewsin]

@conduition testing pr. in a 3(min)/4(max) signers enviroment, if a person's key is compromised is it safe to reduce min signers to 2?

[conduition]

@canewsin It should be, depending on your threat model.

If a signing group has $t = 3$ and $n = 4$, and one signing share is exposed publicly, then in practical terms, $t$ is decreased to $2$ for most signers, since every signer is assumed to know the exposed share. The exception is the one signer whose share was exposed: She still needs the cooperation of at least 2 other signers in order to create a signature (i.e. for her, $t = 3$ still)

If the group then lowered the threshold to $t' = 2$ using VSR, the threshold situation doesn't change for most signers. The old exposed signing share cannot be used with the new signing shares, so the threshold is still 2. However for the person whose share was exposed, she now has a new and safe signing share which is valid for $t' = 2$.

[conduition]

See #570 (comment) for why this was closed as not planned