Condition in Shamir Secret Sharing Scheme

Question

For Shamir's secret sharing scheme (doi 10.1145/359168.359176), one obtains a random polynomial $q$ of degree at most $n-1$ (over $\mathbb{Z}_p[x]$). The constant coefficient of this polynomial is defined to be the key. Then the scheme sends to player $i$ the value $q(i)$ (for $i \leq k$ for some fixed $k$). The interpolation theorem says that if $n$ players come together, then I can use interpolation to reconstruct the polynomial (there is a unique polynomial $p$ of degree at most $n-1$ such that $p(i)=q(i)$ .. in otherwords $p=q$. So that I can grab the constant coefficient of $p$ and it must be the same as the constant coefficient of $q$, and hence must be the key).

The question I have, is that what if the polynomial is degree less than $n-1$. There seems to be nothing in the construction as described by Shamir that prevents this. However, Shamir states that $n-1$ players cannot reconstruct the polynomial.

The problem I am having is that there seems to be a "most of the time" clause missing. If I happen to pick a degree one polynomial then any two players can reconstruct the polynomial. So is it that the players do not know the degree of the polynomial, or that the probability of picking a small degree polynomial is low enough that the probability of two participants guessing the key is still the same as random guessing, or am I missing something else.

Answer 1

I am not sure if this will completely answer the question, but I have a couple observations that might help.

First, note that for the random polynomial $q$, $q(0) = a_0$ is the key -- this is from the way that polynomial interpolation works. So it is important that the value $q(0)$ is never sent to a participant; $q(i)$ is sent for $0 < i < n$. This is also why it is important that the prime $p > k$ (where $k$ is the number of participants) -- it is to ensure that I can obtain $k$ "shares" without revealing the key.

Second, the polynomial $q$ is not just random, but also secret. The fact that the degree of the polynomial $q$ is unknown matters. When $n-1$ participants come together, they can do anything they want -- they are super clever. They claim that the key is $w$. However, there is a unique polynomial $g$ of degree $n-1$ such that $$g(i) = q(i)$$ and $$g(0) = w$$ However, this would be true for any $w$. Since we know that the secret is given by a polynomial of degree less than $n$, and from the data that the pool of $n-1$ participants have, any value of key supposed is as likely ... no value of key can be ruled out. **Note however, that this is not true if the participants know the degree of the polynomial.

Answer 2

There is no problem. True, if the polynomial you pick is of degree 1, then two parties can find the secret. However, they don't know that fact (without learning the other shares).

For instance, assume that the secret is 0, and you picked the polynomial $x$. Thus party 1 gets $q(1)=1$ and party 2 gets $q(2)=2$.

Had they known that the other shares are {3,4,5, ....}, they would've been able to realize that $q(x)=x$ and learn $q(0)$. But they don't. For each other selection of shares $\{q(3),q(4),...\}$ there exists a unique polynomial, and a different secret. Without knowing $\{q(3),q(4),...\}$, any value in $\mathbb{Z}_p$ has the same probability of being $q(0)$, and thus the two users have no information about $q(0)$ prior to learning the other shares.