Are the shares of Shamir secret sharing uniformly distributed random numbers?

Let $t$ be a threshold in the Shamir secret sharing (SSS) scheme.

Assume we know $t'<t$ shares. Assume we are given some random values picked uniformly from the same field as the one used in SSS.

Question: can we distinguish the random values from the shares with a non-negligible probability?

Assume we know $t'<t$ shares. Assume we are given some random values picked uniformly from the same field as the one used in SSS.

Question: can we distinguish the random values from the shares with a non-negligible probability?

It depends.

Now, there are two possible ways to interpret your question (and while the answer is the same for both, the logic differs slightly). Here are the ways I see:

• These $r$ 'random values' are to be considered all at once as potential shares; that is, the adversary was given a total of $t' + r$ shares, $t'$ of which are true shares, and $r$ of which might be random values, or (as far as the adversary was concerned) might also be true shares. If that's the case, follow the logic below.

• These $r$ 'random values' are all possibilities of the missing share. That is, $r-1$ of them are random values (and the adversary knows that), that last value might also be a random value, or it might be a true value - the adversary doesn't know which, and he also doesn't know which might be the true value. If that's the case, follow the logic below, but with $r=1$, and iterate through the various possibilities for the honest share.

I'll also assume that the attacker has some knowledge of what the shared secret might be; he might not know the exact value, but he might know the value to be one of a small set of possibilities (or at least, know that there are a large set of values that it can't be).

In that case, if $t' + r < t$, then the adversary cannot determine anything; all these shares look random. That is, for any values of the known shares, and any value of the shared secret, there are possible coefficients to the unknown polynomial that would make that lead to the observed values (and it turns out that there's an equal number of possibilities independent of the observed values, hence the adversary can't even get any probabilistic information).

On the other hand, if $t' + r \ge t$, then the adversary does have an approach; he can take the shares he has (both the known good ones, and the ones with questionable providence), and reconstruct what shared secret they would imply; he would then check to see if that shared secret was possible. If it's not one of the possible values, he knows that some of the shares he used were incorrect.

Each value of the degree $t-1$ full SSS polynomial $P$ evaluated at any $x$ in the finite field $F$ it is defined over is uniformly distributed in $F$. See this answer for example.

Now assume $t’<t$ shares are revealed, say they are $S’=\{(x_1,P(x_1)),\ldots,(x_{t’},P(x_{t’}))\}.$

If the original set of shares was $S$ the nonempty set $T=S\setminus S’$ now uniquely determines in the usual way a valid Lagrange interpolation polynomial of degree $t-t’-1$ given any $t-t’$ points $x$ in $K \setminus \{x_1,\ldots,x_{t’}\}$.

Distinguishing Algorithm: Let $k>t-t’$ and let claimed shares $$C=\{(x_j,y_j):1\leq j \leq k\}$$ be given. If these are genuine shares any $t-t’$ of them will give the same Lagrange Interpolation polynomial as any other such subset of the same size. If the $y_j$ are random, two distinct Lagrange interpolations say two supported on $$A=\{x_1,\ldots,x_{t-t’}\}$$ and on $$A’=\{x_2,\ldots,x_{t-t’},x_{t-t’+1}\}$$ will give different Lagrange interpolation polynomials with probability $$1-\frac{1}{q}$$ where $q$ is the size of the field we are using.

In fact even if only one share in $A \bigcup A’$ is random, this property will hold since at least one of the interpolations will yield a random polynomial.

No we can't. We know that SSS is perfect that means knowledge of (t-1) or fewer shares provides no information about s -therefore about other shares-