How to reshare a secret

tl;dr: A $t$-out-of-$n$ sharing of $s$ can be reshared as a $t^{\prime }$-out-of-$n^{\prime }$. How? Each old player $t^{\prime }$-out-of-$n^{\prime }$ reshares their share with the new players. Let $H$ denote an agreed-upon set of $\ge t$ old players who (re)shared correctly. Then, each new player’s $t^{\prime }$-out-of-$n^{\prime }$ share of $s$ will be the Lagrange interpolation (w.r.t. $H$) across all the shares received from the old players.

Preliminaries: How to share a secret

This article assumes familiarity with Shamir secret sharing[^Shamir79], a technique that allows a dealer to “split up” a secret $s$ amongst $n$ players such that any subset of size $\ge t$ can reconstruct $s$ yet no subset of size $<t$ learns anything about the secret.

Shamir secret sharing

Recall that a secret $s\in {\mathbb{Z}}_p$ is $t$-out-of-$n$ secret-shared as follows:

1. The dealer encodes $s$ as the 0th coefficient in a random degree-$(t-1)$ polynomial $f(X)$: $$\begin{array}{}\text{(2)}& f(X)& =s+\sum _{k=1}^{t-1}{f}_k{X}^k,\text{where each}{f}_k\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p\end{array}$$

2. The dealer gives each player $i\in [n]$, their share $s_i$ of $s$ as: $$\begin{array}{}\text{(3)}& s_i& =f(i)\text{(4)}& & =s+\sum _{k=1}^{t-1}{f}_k\cdot i^k\end{array}$$

3. The shares $[s_1,s_2,\dots ,s_n]$ define the $t$-out-of-$n$ sharing of $s$.

Lagrange polynomials

Recall the definition of a Lagrange polynomial w.r.t. to a set of evaluation points $T$. $$\begin{array}{}\text{(5)}& \mathrm{\forall }i\in [n],{\mathcal{L}}_i(X)& =\prod _{k\in T,k\ne i}\frac{X-k}{i-k}\end{array}$$ The relevant properties of $L_i^T(X)$ are that: $$\begin{array}{}\text{(6)}& L_i(i)& =1,\mathrm{\forall }i\in T\text{(7)}& L_i(j)& =0,\mathrm{\forall }i,j\in T,i\ne j\end{array}$$

Shamir secret reconstruction

Any subset $T\subseteq [n]$ of $t$ or more players can reconstruct $s$ by combining their shares as follows: $$\begin{array}{}\text{(8)}& \sum _{i\in T}{\mathcal{L}}_i^T(0)s_i& =\sum _{i\in T}{\mathcal{L}}_i^T(0)f(i)=f(0)=s\end{array}$$

How to reshare a secret

Suppose the old players, who have a $t$-out-of-$n$ sharing of $s$, want to reshare s with a set of $n^{\prime }$ new players such that any $t^{\prime }$ players can reconstruct $s$.

In other words, they want to $t^{\prime }$-out-of-$n^{\prime }$ reshare $s$.

Importantly, they want to do this without leaking $s$ or any info about the current $t$-out-of-$n$ sharing of $s$. A technique for this, whose origins are (likely?) in the BGW paper¹, is described by Cachin et al.² and involves four steps:

1. Each old player $i$ first “shares their share” with the new $n^{\prime }$ players: i.e., randomly sample a degree-$(t^{\prime }-1)$ polynomial $r_i(X)$ that shares their $s_i$: $$\begin{array}{}\text{(9)}& r_i(X)& =s_i+\sum _{k=1}^{t^{\prime }-1}{r}_{i,k}{X}^k,\text{where each}{r}_{i,k}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p\end{array}$$

2. Let $z_{i,j}$ denote the share of $s_i$ for player $j\in [n^{\prime }]$. $$\begin{array}{}\text{(10)}& z_{i,j}=r_i(j)\end{array}$$ Then, each old player $i$ will send $z_{i,j}$ to each new player $j\in [n^{\prime }]$.

3. The new players agree³ on a set $H$ of old players who correctly-shared their share $s_i$ with all $n^{\prime }$ new players.
   • This is certainly sufficient and easily achievable via PVSS³, but may not be necessary.
4. Each new player $j\in [n^{\prime }]$ interpolates their share $z_j$ of $s$ as: $$\begin{array}{}\text{(11)}& z_j& =\sum _{i\in H}{\mathcal{L}}_i^H(0)z_{i,j}\text{(12)}& & =\sum _{i\in H}{\mathcal{L}}_i^H(0)r_i(j)\end{array}$$

And voilà: SUCH A BEAUTIFUL, SIMPLE PROTOCOL for secret resharing.

Why does this work?

It’s easy to see why if we reason about the underlying polynomial defined by the new players’ shares $z_j$. Specifically, the degree-$(t^{\prime }-1)$ polynomial $r(X)$ where $r(0)=s$: $$\begin{array}{}\text{(13)}& r(x)& =\sum _{i\in H}{\mathcal{L}}_i^H(0)r_i(X)\text{(14)}& & =\sum _{i\in H}{\mathcal{L}}_i^H(0)(s_i+\sum _{k=1}^{t^{\prime }-1}{r}_{i,k}\cdot X^k)\text{(15)}& & =(\sum _{i\in H}{\mathcal{L}}_i^H(0)f(i))+(\sum _{i\in H}{\mathcal{L}}_i^H(0)(\sum _{k=1}^{t^{\prime }-1}{r}_{i,k}\cdot X^k))\text{(16)}& & =s+\sum _{i\in H}{\mathcal{L}}_i^H(0)(\sum _{k=1}^{t^{\prime }-1}{r}_{i,k}\cdot X^k)\text{(17)}& & \stackrel{\mathsf{def}}{=}s+\sum _{k=1}^{t^{\prime }-1}{r}_k{X}^k\end{array}$$

In other words, $[s,r_1,r_2,\dots ,r_{t^{\prime }-1}]$ are the coefficients of the polynomial obtained from the linear combination of the $r_i(X)$’s by the Lagrange coefficients ${\mathcal{L}}_i^H(0)$.

In more detail: $$\begin{array}{}\text{(18)}& r(x)& =s+\left(\begin{array}{cc}& {\mathcal{L}}_{i_1}^H(0)(\sum _{k=1}^{t^{\prime }-1}{r}_{i_1,k}\cdot X^k)+\\ & {\mathcal{L}}_{i_2}^H(0)(\sum _{k=1}^{t^{\prime }-1}{r}_{i_2,k}\cdot X^k)+\\ & \dots \\ & {\mathcal{L}}_{i_{|H|}}^H(0)(\sum _{k=1}^{t^{\prime }-1}{r}_{i_{|H|},k}\cdot X^k)\end{array}\right)\end{array}$$

Let $c_{i_j,k}\stackrel{\mathsf{def}}{=}{\mathcal{L}}_{i_j}^H(0)\cdot r_{i_j,k}$. Then, we can rewrite the above as: $$\begin{array}{}\text{(19)}& r(x)& =s+\left(\begin{array}{cc}& \sum _{k=1}^{t^{\prime }-1}{c}_{i_1,k}\cdot X^k+\\ & \sum _{k=1}^{t^{\prime }-1}{c}_{i_2,k}\cdot X^k+\\ & \dots \\ & \sum _{k=1}^{t^{\prime }-1}{c}_{i_{|H|},k}\cdot X^k\end{array}\right)\end{array}$$ Let $r_k\stackrel{\mathsf{def}}{=}\sum _{i_j\in H}{c}_{i_j,k}$. Then, we can rewrite the above as: $$\begin{array}{}\text{(20)}& r(x)& \stackrel{\mathsf{def}}{=}s+\sum _{k=1}^{t^{\prime }-1}{r}_k{X}^k\end{array}$$

And, as we saw in Equation $\text{11}$ above, any new player $j\in [n^{\prime }]$ can get their share of $r(X)$ via: $$\begin{array}{}\text{(21)}& z_j& =\sum _{i\in H}{\mathcal{L}}_i^H(0)r_i(j)\text{(22)}& & =r(j)\end{array}$$

Acknowledgements

Big thanks to Benny Pinkas for pointing me to the BGW paper¹ and for pointing out subtleties in what it means for an old player to correctly share their share.