2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not quite sure I'm following your description. It sounds like you are saying that the $x$ indices used in sharing are not known and you want to keep them secret. Is that correct? Where does $W$ come from? What is the goal here? $\endgroup$ – mikeazo Mar 20 '18 at 19:35
  • $\begingroup$ @mikeazo I edited the question. I'm taking a value W and modifying the X indices used which are also not known. The shards are then delivered. The receiver reconstructs a value which is A) not the secret and B) not W. Is the original secret secure from the recipient of the modified shards secure? $\endgroup$ – Erik Aronesty Mar 21 '18 at 10:54
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. This is a way of using SSS as a "hash". You could also raise pow(g, r) where g is a large prime, or you could use ECC but that introduces the security of discrete logs in what was a system that didn't rely on that. $\endgroup$ – Erik Aronesty Apr 17 '18 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.