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$?
$\begingroup$
$\endgroup$
-
$\begingroup$ Is it a requirement that the secret $S$ be the same no matter which $t$ of the $n$ parties participate to create $S$? $\endgroup$ – mikeazo Nov 1 '11 at 22:16
-
$\begingroup$ 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" $\endgroup$ – Hamouid Nov 1 '11 at 22:24
-
1$\begingroup$ 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? $\endgroup$ – Dilip Sarwate Nov 3 '11 at 13:27
$\begingroup$
$\endgroup$
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.)
answered Nov 4 '11 at 19:40
-
2$\begingroup$ 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. $\endgroup$ – PulpSpy Nov 14 '11 at 22:58
-
$\begingroup$ 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. $\endgroup$ – Ilmari Karonen Nov 15 '11 at 5:05
$\begingroup$
$\endgroup$
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.
answered Nov 1 '11 at 22:25
-
$\begingroup$ 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. $\endgroup$ – Hamouid Nov 2 '11 at 4:17
-
$\begingroup$ 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$. $\endgroup$ – Thomas Pornin Nov 2 '11 at 12:07
$\begingroup$
$\endgroup$
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".
-
$\begingroup$ 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? $\endgroup$ – Hamouid Nov 2 '11 at 4:09
-
$\begingroup$ 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. $\endgroup$ – user991 Nov 2 '11 at 5:50
-
1$\begingroup$ 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. $\endgroup$ – mikeazo Nov 5 '11 at 14:28
-
$\begingroup$ What else is secret sharing when t=1 ? $\hspace{1 in}$ $\endgroup$ – user991 Nov 5 '11 at 21:22
-
2$\begingroup$ 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. $\endgroup$ – mikeazo Nov 5 '11 at 22:56
