Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
k=1 doesn't require a sharing scheme? –  emboss Jun 14 '12 at 17:21
    
If I have a secret S, and I want 4 people to have access to it, then I can make k=1. Each person then has their own 'password' to the secret. Maybe not a likely scenario but a valid one. –  grieve Jun 14 '12 at 18:32
    
But to my understanding k=1 means having one share alone allows you to reconstruct the secret directly, without needing another share. In SSS, this results in handing S to the 4 people directly, because a_0 = S and there are no random coefficients to be chosen. –  emboss Jun 15 '12 at 13:38
    
I just set K=1 as an example, my question still applies where k > 1. I think focusing on that is not productive, so I am editing the question. –  grieve Jun 18 '12 at 20:13
    
Is there a way to move it there? –  grieve Jun 18 '12 at 21:02
show 2 more comments

migrated from stackoverflow.com Jun 18 '12 at 21:05

This question came from our site for professional and enthusiast programmers.

3 Answers

up vote 3 down vote accepted

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.)

share|improve this answer
add comment

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.

share|improve this answer
add comment

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?

share|improve this answer
    
I have a client/server architecture, where each client can have multiple username/passwords pairs. I wanted to encrypt data on the server side such that any client user logging in would be able to decrypt it. The server would randomly generate the encryption key, and then use a combination of the passwords of the users and Samir's Secret Sharing to allow the users to decrypt the encryption key, and then the data. I actually found a completely different way to do this, after posting this question, but was still interested to see if it was possible. –  grieve Jun 20 '12 at 19:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.