6
$\begingroup$

If I am decoding a key by applying shares, is it possible to know when the threshold has been reached, and the secret revealed, without having to be told what the threshold is?

Also, is it possible to determine if a share is a "valid" share (ie originally generated by SSS for a given secret)?

$\endgroup$
5
$\begingroup$

Yes. If all of the shares you have are valid, you can tell when you have reached the threshold. Reconstructing the secret from $t+1$ shares will yield the same result as reconstructing the secret from $t+2$ shares. Reconstructing it from $t-1$ will however (always) yield a completely different result. Reconstructing the secret from $t-2$ or fewer shares will yield a different result with probability $1-1/q$, provided that all of the coefficients (except order $0$ and order $t-1$) are selected uniformly from $\mathbb{Z_q}$ and the high order coefficient uniformly from $\mathbb{Z_q^*}$. If "weak sharings" are avoided by selecting all coefficients to be non-zero, the probability will be slightly off.

For instance, if you are using Lagrange basis polynomials for reconstructing the original polynomial, adding more shares over the threshold will not increase the degree of the resulting polynomial and the zero degree term will remain constant.

There exist variants of Secret Sharing that will allow you to verify if a share is valid or invalid, such as Pedersen Verifiable Secret Sharing.

$\endgroup$
  • 1
    $\begingroup$ +1, but do note that you can't ever be sure that you've collected enough shares; assuming that the original polynomial coefficients have been chosen randomly, for every set of $k < t$ shares there's a $1/q$ chance that adding one more share to a set of $k$ shares will not change the reconstructed polynomial, where $q$ is the number of elements in the field you're using. (You can tweak the coefficients to avoid this, at least to some extent, but this introduces bias and can thus potentially leak information about the secret to groups with less than $t$ shares.) $\endgroup$ – Ilmari Karonen Dec 28 '15 at 8:09
  • $\begingroup$ @IlmariKaronen Are you sure the probability is exactly $1/q$? I agree with the approximation, but would presume that two polynomials of degree $k+1$ and $t-1$, with $k+1 < t-1$, might intersect in up to $t-1$ different points; not $k+1$ points. $\endgroup$ – Henrick Hellström Dec 28 '15 at 11:27
  • $\begingroup$ Take the interpolated polynomial for the $k$ shares, and evaluate it at the $x$-coordinate of the new share. There's a $1/q$ chance that the result will match the $y$-coordinate of the share, in which case adding the extra share will not alter the polynomial. $\endgroup$ – Ilmari Karonen Dec 28 '15 at 11:32
  • $\begingroup$ @IlmariKaronen I understand, but shouldn't the fact that we are dealing with polynomials and not random functions affect that probability? $\endgroup$ – Henrick Hellström Dec 28 '15 at 11:36
  • $\begingroup$ Not as far as I can see. But maybe we're thinking of different scenarios. I was talking about adding one extra share to a set of $k$ shares, i.e. going from a polynomial of order (at most) $k-1$ to one of order (at most) $k$. By construction, these polynomials intersect at the $k$ original shares; if they intersect anywhere else, they must be identical. $\endgroup$ – Ilmari Karonen Dec 28 '15 at 12:01
1
$\begingroup$

No, you don't know when the threshold has been reached unless you encode it into your share's format.

To understand this, I'll quickly revise how SSS works:
The person to share a secret constructs / chooses a random (large) prime and chooses $k$ random numbers (the coefficients), where $k$ is the threshold. From the coefficients he constructs a polynomial. For each share, he picks a random $x$ and evaluates the polynomial of the $x$ to receivce a random $y$ in return. A pure share is just the pair $(x,y)$.

Obviously, you can't learn the degree of the polynomial from a bunch of (random) points so there's no way to recover the threshold (which is the degree + 1). You can however define a format for your shares that includes a) the prime generating the needed field, b) the threshold, c) the $x$ value of your share and d) the $y$ value of your share. In this case you can recover the threshold from your shares.

Is it possible to determine if a share is a "valid" share?

No.
As explained above, a share is (maybe) some general parameters (threshold, prime) and a point. As the x-coordinate of the point should be completely random, the y-coordinate will also be random and so there's always a polynomial going through that point.

$\endgroup$
  • 2
    $\begingroup$ The $x$-coordinates of the shares need not be random, all that is needed is that they be distinct and non-zero. $\endgroup$ – fkraiem Dec 27 '15 at 23:07

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.