Can you update a (k,n) scheme to a (k+t, n+t) scheme (assuming old keys can be deleted)? 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.)
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) &lt; 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.