Tampering with Shamir's subshares

Question

Suppose a set of Shamir's redistributable-secret-sharing participants issue a redistribution of subshares.

I envision this as a series of points on a line (2 of N, is planar, easy to think about). Redistribution appears to create new lines that point to the heights of the original shares - but when the vectors are transposed they now can be used to derive points on a line that intersects the original key.

During redistribution, new indices can be chosen instead of re-using the same, there is no effect on the final values. Imagine the actual indices chosen are not redistributed however, and instead a fixed value W is secretly added to each of the x-indices before transmission of the subshares.

Now the recipients reassemble the sub-shares, producing shares. These shares will all lie on the same line, and will pass permutation based consistency checks.

But they will point to a different, essentially random, but consistent "secret".

The question is... can the recipient of these modified subshares determine what the original secret is? From what I can tell, the effect of adding W depends on the random coefficients used during subshare redistribution, and should not be recoverable.

Normally the recipient could reconstruct... but with the fixed addition of W the recipient should receive... in essence ... the computation of a distributed hash function on W.

But I'm not sure. If I graph this using 2 of 2, it seems like the recipient of the final shares, in order to deduce the original secret, would have to know the random coefficients used during each shareholder's redistribution.

Essentially I'm trying to create a distributed hash function. I haven't found one that is "redistributable" the way shamir's secrets are. Using a shamir secret, I can create a function ... and then add new members of the group and remove members of the group without re-rolling the original discarded secret.

Answer 1

Let $J$ be the set of conspirators and $S$ the total set of shareholders.

In general you are correct, provided the polynomial $A'(x)-A(x)$ is not zero at $x=0$, where

$$A'(x)=\sum_{j \in J} y_j \prod_{k \in J:k \neq j} \frac{ (x+W- x_k)}{(x_j+W-x_k)} \prod_{k \in S \setminus J} \frac{ (x-x_k)}{(x_j-x_k)}, $$ and $$A(x)=\sum_{j \in J} y_j \prod_{k \in J:k \neq j} \frac{ (x- x_k)}{(x_j-x_k)} \prod_{k \in S \setminus J} \frac{ (x-x_k)}{(x_j-x_k)}. $$

The equation can be simplified into $$A'(0)-A(0)=0$$ by letting $x=0,$ into a polynomial in $W$ whose roots you have to avoid if you want to obscure the secret from the innocent shareholders.

Since the difference is a Lagrange polynomial it is as secure as ordinary secret sharing so if you aren't in possession of $W$, its effect is uniformly distributed over the finite field.