Threshold Secret sharing - How to create a shared secret from pre existing secret parts?

Question

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$?

Answer 1

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

Answer 2

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.

Answer 3

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