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.

In usual $(t, n)$ secret sharing schemes, a secret $S$ is split into $n$ parts so that any $t$ out of $n$ parts reconstruct the original secret. So, suppose that there is a group of $n$ participants each one has a secret $x_i$ ($x_i$ may be its private key). My question is, is it possible to create a secret $S$ using the prexisting secrets $x_i$ ($i=1...n$) so that with any $t$ out of $n$ from these secrets ($x_i$) we can find the secret $S$?

share|improve this question
    
Is it a requirement that the secret $S$ be the same no matter which $t$ of the $n$ parties participate to create $S$? –  mikeazo Nov 1 '11 at 22:16
    
Yes, it is the same. At the beginning, the secret S does not exist, it will be generated by the "n" pre-existing secrets "xi", then, the resulting secret S (the same) may be found from any t out of n secret "xi" –  Hamouid Nov 1 '11 at 22:24
1  
The use of the word "split" in "a secret $S$ is split into $n$ parts" leaves the impression that the parts are smaller than $S$ by a factor of $n$. In a secret-sharing scheme, $n$ shares are constructed from $S$ such that any $t$ shares suffice to reconstruct $S$. In Shamir's secret-sharing scheme, each share is exactly the same size as $S$. So what the OP wants is a created secret $S$ (same size as the pre-determined shares $x_i$) such that any $t$ shares can recover the secret? It doesn't matter what the created secret is as long as it is recoverable? Why is it of any interest? –  Dilip Sarwate Nov 3 '11 at 13:27
add comment

3 Answers 3

up vote 6 down vote accepted

I'd like to suggest a potentially interesting reformulation (or variant) of the problem as a form of secure multi-party computation:

Given $k$, $n$ and $m$, is there a protocol by which $n$ participants $i \in \lbrace 1, \dotsc, n \rbrace$ may, without the help of a trusted external party, each compute a share $s_i$ such that

  • there exists a secret $S \in \mathbb Z / m \mathbb Z$ that is uniquely determined by any subset of $k$ shares (and can be efficiently calculated from them), and
  • during the course of the protocol, no group of $k-1$ colluding participants can learn sufficient information to allow them to guess $S$ with probability higher than $1/m$?

Further, if such a protocol does exist, does it require assumptions about the computational capacity of the participants, or can it be made information-theoretically secure like conventional secret sharing schemes?

As Thomas Pornin's answer shows, such a protocol does exist when $k = n$: each participant simply selects $s_i$ independently and uniformly from $\mathbb Z / m \mathbb Z$, with $S \equiv s_1 + \dotsb + s_n \mod m$. Thomas's answer also shows that, for $1 < k < n$, at least some communication between the participants must be necessary to establish the shares.

Addendum:

There's actually a very simple way to do this. Each participant $i$ chooses a random element $x_i$ of a finite field $\mathbf F_m$, generates $n$ subshares $y_{i,1}$ to $y_{i,n}$ of it using Shamir's scheme of order $k$, and sends each subshare $y_{i,j}$ to participant $j$. Each participant $j$ then adds the subshares they receive together to obtain their share $s_j = y_{1,j} + \dotsb + y_{n,j}$. By the linearity of Shamir's secret sharing, interpolating any $k$ of the shares $s_j$ then yields the secret $S = x_1 + \dotsb + x_n$.

(Edited to incorporate PulpSpy's space-saving suggestion; see comments.)

share|improve this answer
2  
Actually due to the homomorphism of Shamir secret sharing, each participant can add together all the subshares they receive and just remember the sum. If you interpolate k of them, you will get the sum of the xi's which is S in this case. –  PulpSpy Nov 14 '11 at 22:58
    
Excellent point, thanks! It does seem to require that $m$ is a prime power (which my original version does not), but that's usually the case anyway. –  Ilmari Karonen Nov 15 '11 at 5:05
add comment

On a general basis, no. If $t \lt n$, then the first $t$ values $x_1$ to $x_t$ are sufficient to rebuild the secret $S$, regardless of the values of $x_{t+1}$ to $x_n$. Therefore, those last values have no influence whatsoever on $S$. On the other hand, values $x_{n-t+1}$ to $x_n$ should be sufficient to also rebuild the secret, and since the last $t$ of them have no influence whatsoever, you can rebuild the secret with $x_{n-t+1}$ to $x_t$, i.e. less than $t$ values, possible no value at all if $t \leq n/2$. In other words, it cannot possibly work.

(The intuitive way is the following: if the secret values $x_i$ are pre-existing, then they do not have the redundancy on which sharing schemes strive.)

If $t = n$ (all shares $x_i$ are needed to rebuild the secret) then it becomes easy: just XOR all of them together. Possibly, hash all $x_i$ with SHA-256 to get "random looking" 256-bit strings, and XOR these together: this will work better if the $x_i$ do not all have the same size, or have some common structure.


If you can have some extra public storage, then you can use regular Shamir's Secret Sharing, which, for a secret $S$ you can choose, yields shares $v_i$. Then, have each participant symmetrically encrypt $v_i$, with a key derived from (the SHA-256 of) his $x_i$; the resulting ciphertexts are then stored in the public storage area. That's an extra requirement (a storage area) but not as big a requirement than having each participant store a new confidential value somewhere.

share|improve this answer
    
Thank you for your answer, it's very interested, but about the shamir's secret sharing, to my knowledge, we cannot create a secret from n pre-existing secrets (xi) where any t<n of theme are sufficient to find the generated secret. –  Hamouid Nov 2 '11 at 4:17
    
That's the point. If you use Shamir's scheme, you get a whole new set of secret values to store (which I call $v_i$); but that storage can be a public shared disk (as opposed to, say, a smartcard per participant) because each participant already has a secret value $x_i$ and can use it as a symmetric key to encrypt his $v_i$. –  Thomas Pornin Nov 2 '11 at 12:07
add comment

EDIT: $\,$ This only works when t=1, as your previous question makes me believe you are most interested in.

Yes, see Can one generalize the Diffie-Hellman key exchange to three or more parties?.
The security of that is based on the difficulty of the "generalized Diffie-Hellman problem".

share|improve this answer
    
Thank you for the answer. Yes of course, I'm interested in my previous question. The Diffie-Hellman key exchange is a good idea to create and share a secret from a set of other pre-existing secrets, but I do not understand why you say that "this only works when t=1" Please, can you explain me what do you mean by that? –  Hamouid Nov 2 '11 at 4:09
    
Well, as described, each person could calculate the secret on their own (after all the messages have been sent), and I can't think of any way to modify the procedure to avoid that. –  Ricky Demer Nov 2 '11 at 5:50
1  
I think you are confused on the definition of secret sharing. Secret sharing means at long as $t$ out of $n$ people get together, they can reconstruct the secret. What you seem to be saying is that the $n$ people get together and exchange messages, then each individual can reconstruct the secret. That is not the same. –  mikeazo Nov 5 '11 at 14:28
    
What else is secret sharing when t=1 ? $\hspace{1 in}$ –  Ricky Demer Nov 5 '11 at 21:22
2  
To me, secret sharing is when there is initially a secret, which is somehow shared so that the parties (or some subset) can reconstruct the original secret. What you are advocating is more of a secret (or key) distribution. There is no "original" secret, the parties run Diffie-Hellman to distribute a secret which was, prior to the protocol, unknown to all parties. –  mikeazo Nov 5 '11 at 22:56
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.