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?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
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.
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.