Secret sharing questions

Question

I would like to make a few questions about Shamir's secret sharing scheme and. To begin with, I am starting with the next theorem that determines the intuition of the whole theorem.

$\textbf{Theorem:}$ Let $p$ be a prime, and let $\{(x_1,y_1), . . . ,(x_{t+1},y_{t+1})\}\subseteq\mathbb{Z}_p$ to be a set of points whose $x_i$ values are all distinct. Then there is a unique degree-$t$ polynomial $f$ with coefficients from $\mathbb{Z}_p$ that satisfies $y_i \equiv_p f(x_i)$ for all $i$ (I would add to the theorem where $s=f(0)$).

As we already know in a $k$ out of $n$ secret sharing scheme, each agent splits the secret in $n$ parts however only $k=t+1$ parts (of a polynomial of degree $t$) are needed if we want to compute the secret. Suppose that $f$ is the polynomial function such that

$$f(x)=a_tx^t+a_{t-1}x^{t-1}+\cdots+a_1x+a_0=s+\sum_{i=1}^ta_ix^i,\quad\text{such that $y_i \equiv_p f(x_i)$ and $s=f(0)$}\quad (1)$$

1. When we say that a dealer shares the secret does this mean that every player takes a pair of $(x_i,f(x_i))$ such that $y_i \equiv_p f(x_i)$ from the $n$-pairs, namely $i=1,2,3...,n$? If we have more pairs of points of those needed by the theorem to construct the polynomial function $(1)$ what becomes with the rest of them? I don't get it.
2. All these $t+1$ pairs are chosen randomly to reconstruct the secret in the reconstruction phase or they collude? Could anybody show the mathematical formulations form the point that $f$ is chosen to the reconstruct $s$ based on the theorem?

Answer 1

If you want $k$ users to be able to reconstruct $s$ and no smaller number of users to be able to learn anything about the secret, you must have a polynomial $f$ of degree $k-1.$

The dealer gives exactly one share $(x_i,f(x_i))$ to user $i,$ for $i=1,2,\ldots,n$.

That is all that user gets. It doesn't really matter which user gets which share.

As long as $p-1\geq n,$ $n$ users can be supported. Let $S=\{x_1,\ldots,x_n\}$ be the points that determine the currently used shares.

The "leftover shares" can be used later if new people join, so it may not be a bad idea to have $p$ appreciably bigger than $n,$ the current number of users.

Note that we assume that the dealer is a trusted third party and that the users will actually supply the correct share when asked by the dealer, otherwise things won't work, and more sophisticated schemes are needed.

This also applies if $k$ users can themselves get together to reconstruct, they must not lie about their shares and if exactly one of $k$ users is dishonest, he/she can learn the shares of the rest of the users, which means the rest cannot compute the secret correctly but he/she can if the remaining $k-1$ users are honest.

Answer 2

Although I am not sure for this and this is not a complete asnwer and I hope if anybody sees what I am writing he/she could verify it, If the players are $n$, the $(k,n)$ secret sharing scheme means that I will split $s$ in $n$ parts, such that the polynomial $f$ is a polynomial function of degree $t$ that takes as input $s$ and the $t$ and with the process $y_i\equiv_p f(x_i)$ gives back t+1 pairs. In equivalent terms

$$\left\{f(s,t)|\text{$s=f(0)$ and $y_i\equiv_p f(x_i)$ for $i=\{1,2,...,t+1\}$}\right\}$$

But thre rest of the splitting parts of $s$ that are accounted to be $j=n-(t+1)$ where $t<2n-1$ I do get it also how are they used. I mean there is a reason behinf it...that I can not figure it out....