Shamir Secret Sharing: Why cannot we recover polynomial's root if we have $t-1$ shares?

Imagine we have $t-1$ shares in $(t,n)$ shamir secret sharing. So at least $t$ shares are needed.

Question: Why cannot we use $t-1$ shares to find a root of the polynomial and then recover the secret?

• Related question: crypto.stackexchange.com/questions/19332/… – mikeazo Aug 26 '15 at 17:05
• @mikeazo shall I remove this? – user13676 Aug 26 '15 at 17:07
• Definitely don't remove this. If that answers your question, let me know and we can mark this as a duplicate. I, however, don't think this is an exact duplicate and that we can leave it open. – mikeazo Aug 26 '15 at 17:10
• @mikeazo If you had a time, could you have a look at the last question I put in the comment, please. I do appreciate for that. – user13676 Aug 26 '15 at 17:12
• My guess is that unless $(\beta, 0)$ is one of the shares, then the probability would be very small, something like $1/p$. But I'm not sure on that. That question in the comments would be a good question to ask on Math.SE. – mikeazo Aug 26 '15 at 17:16

Take a linear polynomial: $y=mx+b$. If I tell you that the point $(1,5)$ is on the line, can you tell me $m$ and $b$? No, because in fact there are infinitely many lines that pass through the point $(1,5)$. It takes 2 points to uniquely identify a line. In general it takes $t$ points to uniquely identify a degree $t-1$ polynomial. Furthermore, given $t-1$ points, there are infinitely many degree $t$ polynomials that have those $t-1$ points.

In practice, since we use finite fields in Shamir secret sharing, there are not infinitely many polynomials, but you get the point.

Now, as detailed here, you can potentially get roots of the polynomial from the shares. In particular, any share with a $0$ y value reveals a root. Even with all roots, however, you may not be able to correctly get the secret as there may be a common divisor among all coefficients that you could not recover with the roots. Assuming that is not the case, you would need all roots in order to reconstruct the polynomial to reveal the secret. So, for a degree $t-1$ polynomial (which has $t-1$ roots), all $t-1$ shares would have to have $0$ y values. The chances of that happening purely by chance is very small. If even one of the shares has a non-zero y value, then you have gained no information on the secret.

• Thank you both for the answers. My question is " What is the probability that given $t-1$ shares, one can find a root of the polynomial? – user13676 Aug 26 '15 at 15:54
• @user13676 You are missing the point: with $t-1$ shares there are infinite polynomials, so all values are equally possible roots. In other words, with $t-1$ shares you still know nothing. – cygnusv Aug 26 '15 at 16:15
• @user13676 Which is what you meant? The former or the latter? – mikeazo Aug 26 '15 at 16:15
• @user13676 : $\:$ How is that related to cryptography? $\;\;\;\;$ – user991 Aug 26 '15 at 16:46
• @mikeazo You forgot about the highest order coefficient. $k(x-2)(x-1)(x+1)$ has the same roots for any value of $k$. And if you don't know $k$, you can't calculate the constant term. – Henrick Hellström Aug 26 '15 at 18:27

Shamir Secret Sharing (SSS) is based on constructing a polynomial of degree $t-1$, whose independent term is the secret $S$. Each share is actually a point of the polynomial.

The security of SSS is based on the fact that, when one wants to interpolate a polynomial of degree $t-1$, one needs at least $t$ points of the polynomial. It can be seen graphically that trying to interpolate with less points (e.g., with $t-1$ points) is impossible since infinite polynomials can be drawn through those points. The Wikipedia article for SSS illustrates this very well.

In cryptographic applications you will not have "infinite" polynomials, but all the possible polynomials of degree $t$ for the given field. That means that knowing $t-1$ points is useless as all possible polynomials are equally plausible. This is called "perfect secrecy".

Shamir's $(t,n)$ secret sharing scheme involves picking a random polynomial $p$ (over a finite field) of degree $t-1$, such that $p(0) = s$ is the secret value to be shared (this is easy to do, since $p(0)$ is just the constant term of the polynomial), and then evaluating the polynomial at $n$ distinct non-zero points $x_1, \dotsc, x_n$ to construct $n$ shares $(x_i, y_i)$, where $y_i = p(x_i)$. Any $t$ of these shares can then be used to reconstruct the polynomial $p$ using Lagrange interpolation, and thus to reveal the secret $s$.

An immediate corollary of this definition is that, for any set of $t-1$ shares $(x_i, y_i$) and any possible secret $s'$, there is a (unique) polynomial $p'$ of order $t-1$ such that $p'(0) = s'$ and $p'(x_i) = y_i$. (To find $p'$, just treat $(0, s')$ as an extra share and use Lagrange interpolation.)

Thus, given only $t-1$ shares, it's impossible to rule out any possible value of the secret, since there's a valid polynomial of degree $t-1$ that could yield that secret. Whether or not you can learn anything about the roots of the polynomial is really irrelevant here.

Ps. It takes just a bit more work to complete the security proof by showing that, if the $t-1$ non-constant coefficients of $p$ have been chosen independently and uniformly at random, then the $y$-values of any set of $t-1$ shares are also uniformly distributed and independent of both each other and of the secret $s$, and thus that possession of $t-1$ shares does not yield even any probabilistic information about $s$. Even this doesn't require any non-trivial probability theory — it's basically just a counting argument, showing that, for each value of $s$, the set of all possible $y$-values and the set of possible random coefficients are in one-to-one correspondence. This is, however, the part that requires the underlying field to be finite — otherwise there is no uniform distribution over the field, and the whole argument falls apart.

This is because $t$ shares uniquely defines the polynomial of degree $t-1$. $t-1$ shares still leaves $k$ possible and equally likely polynomials, for $k$ the size of the field, so the secret is information theoretically hidden.

Think of a degree 1 polynomial, essentially a line. If you know just one point on the line, you cannot say anything about the root (drawing this situation, should make that clear). But with one more point you get a unique line going through the first point, and can find all points on the line including the root.