Can you update a (k,n) scheme to a (k+t, n+t) scheme (assuming old keys can be deleted)?

Question

I know that $(k,n)$ can increased to $(k+t,n-s)$ one, by generating a random polynomial $p(x)$ of degree $k+t$ with constant term $0$, and then ordering each agent $a$ to add $p(a_x)$ (where $a_x$ is an agent's public x-coordinate) to their share (if $k$ old shares are compromised, the secret is compromised, but we are assuming enough old shares are destroyed to prevent this) (we get $n-s$ by either ordering $s$ agents them to destroy their share, or, if it is already compromised, not sending an update to that agent.)

Also, I know a $(n,n)$ XORing secret sharing scheme can be increased to $(n+t,n+t)$, by generating $n+t$ bit strings that XOR to $0$, and sending the first $n$ to each agent to XOR with their current share (and send the rest to $t$ new agents). This in particular means there exists a secret sharing scheme $(k,n)$ can be updated to $(k+t, n+t)$ via this.

---

Can a $(k,n)$ shamir secret sharing scheme can be updated to a $(k+t, n+t)$, without any agents having to reveal their share?

Note: Remember, we are assuming that enough old keys can be destroyed to prevent the secret from being reconstructed from old keys alone (which is why this doesn't apply.)

Answer 1

You can use a variant of the standard "degree reduction" trick from secret-sharing-based MPC protocols, but use it to increase the degree instead.

You start out with a $(k,n)$-sharing of a value $s$. Denote the collective object by $[s]_k$, meaning that party $i$ has private value $p(i)$ where $\deg(p) < k$ and $p(0) = s$. Just so we're on the same page:

• $s$ can be expressed as a linear combination of these shares via $s = p(0) = \sum_{i=1}^n c_i p(i)$. The coefficients $c_i$ in this case are public.

• if everyone locally multiplies their share of a value $[v]_k$ by a public $\alpha$, the result is $[\alpha v]_k$ -- i.e., shares of $\alpha v$.

• if everyone locally adds shares of $[v_1]_k$ and $[v_2]_k$ the result is $[v_1 + v_2]_k$.

Back to our $(k,n)$ sharing of $s$, we want to make it a $(k+t,n+t)$ sharing. To do this, let all of the original $n$ parties make shares of shares. Party $i$ acts as dealer, distributing $(k+t,n+t)$-shares of the value $p(i)$ to create the object $[p(i)]_{k+t}$. Using local computation, everyone computes the desired object $[s]_{k+t} = \sum_{i=1}^n c_i [p(i)]_{k+t}$. They can throw away the old shares of $[s]_k$ now.

Note: all of this assumes honest behavior by the parties. If some are corrupt, then verifiable secret sharing tricks would be needed.

Answer 2

Agents do not have to reveal their shares if they run Shamir secret sharing algorithm with new parameters and their old shares as the input. Each one would send the output to new recipients. Having exchange done, everyone recovers new shares according to old parameters.