Can I pre-define the points in Shamir's Secret Sharing algorithm

Question

With Shamir's secret sharing is it possible to pre-define the points returned by the algorithm?

For simplicity if I have (k, n) where k=2, and n=4, and I have the points X,Y,Z, and Q. Can I create the coefficients so that X,Y,Z, and Q are the points returned from the algorithm.

If yes will it still be secure (or secure enough)?

Edit:

Change my example to k=2 instead of k=1 to keep the comments from degenerating into a discussion on the merits of only needing a single piece of knowledge to access the secret.

Answer 1

As poncho and Maeher have noted, this isn't possible with straightforward Shamir's secret sharing.

In fact, it's pretty obvious, once you think about it, that there's no way to choose more than $k$ shares independently in advance and get a consistent secret out of them with any unconditionally secure $k$-out-of-$n$ threshold secret sharing scheme, even if you allow the secret to be random.

In particular, imagine you have $k+1$ independently chosen shares $s_1, s_2, \dotsc, s_{k+1}$. By definition, either of the $k$-tuples $(s_1, s_2, \dotsc, s_k)$ and $(s_2, s_3, \dotsc, s_{k+1})$ are enough to fully reconstruct the secret, whereas the $k-1$-tuple $(s_2, s_3, \dotsc, s_k)$ alone provides no information about the share. This means that, for every pair of secrets $S$ and $S'$ and any given $k-1$ shares $s_2, s_3, \dotsc, s_k$, there must exist shares $s_1$ and $s_{k+1}$ such that $(s_1, s_2, \dotsc, s_k)$ yields the secret $S$ while $(s_2, s_3, \dotsc, s_{k+1})$ yields $S'$.

All that said, however, there is a simple way to modify Shamir's secret sharing scheme so that the shares can be chosen independently in advance.

Namely, let $s_1, s_2, \dotsc, s_n$ denote the shares chosen in advance, and let $S$ be the secret you wish to share. Now compute $n$ "auxiliary" shares $a_1, a_2, \dotsc, a_n$ using ordinary Shamir's secret sharing on $S$, and add them to the corresponding pre-chosen shares to get $$p_i := a_i \oplus s_i$$ for all $i \in \{1, 2, \dotsc, n\}$, where $\oplus$ denotes addition in the finite field the shares belong to.

Finally, publish the results $p_1, p_2, \dotsc, p_n$.

Now, to reconstruct the secret $S$, any $k$ participants may each subtract their share $s_i$ from the public $p_i$ (or just reveal their $s_i$ and let others combine it with $p_i$) to obtain the corresponding auxiliary shares $a_i$ and reconstruct $S$ from them.

Meanwhile, assuming that the shares $s_1, s_2, \dotsc, s_n$ are randomly chosen from the finite field used, merely knowing $p_i$ but not $s_i$ for any $i$ provides no information about the corresponding auxiliary share $a_i$. Thus, knowing less than $k$ of the shares will not reveal any information about the secret.

(Of course, if the pre-chosen shares are not uniformly chosen random values, then the unconditional security property will not hold. One may still obtain at least computational security, up to the limits set by brute force guessing attacks, by feeding the pre-chosen shares through a secure cryptographic hash function before combining them with the auxiliary shares.)

Answer 2

With Shamir's secret sharing for the case of $k$ out of $n$, you construct a random polynomial of degree $k-1$, because $l$ points uniquely identify a polynomial of degree $k-1$.

The usual way to construct said polynomial is to uniformly choose coefficients $a_1$ through $a_{k-1}$ and setting $a_0=s$.

There is an alternative to that, where you choose $k-1$ points uniformly at random. The $k$th point is then $(0,s)$, you can compute the polynomial defined by those points and then compute the remaining $n-(k-1)$ points. There is absolutely no difference between the two approaches.

So in summary: No that is not possible. You can freely choose at most $k-1$ shares. And also for the security to hold, those must be chosen uniformly at random.

Answer 3

Well, no, in general, you won't be able to select arbitrary points $X, Y, Z$ and $Q$ that would work in a Shamir secret sharing scheme (unless $k\ge4$).

Here's why; Shamir's scheme assumes that the points are on some polynomial of degree $k-1$ or less; for $k=2$, this means that the points all must be solutions of a linear equation $y = a_1 x + a_0$ for some constants $a_1, a_0$. There will usually not be any such constants that will simultaneously work for all four points, and so Shamir's scheme will not work.

BTW: what problem are you trying to solve? You mention "security"; what do you mean by that? If you want to prevent someone from doing something, what is that something?