4
$\begingroup$

EDIT: Ilmari Karonen's answer below well not exactly what I want, gives a very good idea of what I am trying to accomplish.

Are there any known secret sharing schemes that allow new parties to be read in on a portion secret, preferably without all parties having to be online at the same time? I don't want to have to keep the original trusted authority around. The question is, is this possible without reconstructing the original secret?

My idea is that I divide a secret between $N$ of $k$ people at time $T$. At time $T+1$, I want to change it to $n$ of $k'$ people. This may or may not be strictly possible, but is there something possible along those lines?

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Read in by whom? Someone who knows the entire secret? Or must it be possible to read them in without anyone learning or using the entire secret? $\endgroup$ – David Schwartz Oct 20 '11 at 22:01
  • 1
    $\begingroup$ Are the $n$ and $N$ in the last paragraph the same number, or one smaller/bigger than the other? $\endgroup$ – Paŭlo Ebermann Oct 20 '11 at 23:50
  • $\begingroup$ I know this is an older question, but I found some thing recently then came across your question. Thought you might be interested. csis.gmu.edu/faculty/desmedt%207-25-97.pdf and cs.cmu.edu/~wing/publications/CMU-CS-01-155.pdf $\endgroup$ – mikeazo Mar 6 '13 at 14:04
4
$\begingroup$

A trivial example showing that this is possible, at least in some cases, is the $n$-out-of-$n$ secret sharing scheme based on modular addition. Let $s \in \mathbb Z / m \mathbb Z$ be the secret, and construct $n$ shares of it by picking $x_1, \dotsc, x_{n-1}$ randomly from $\mathbb Z / m \mathbb Z$ and letting $x_n = s - (x_1 + \dotsm + x_{n-1}) \mod m$. Thus, the secret can be reconstructed by calculating $s = x_1 + \dotsm + x_n \mod m$.

In this scheme, anyone who holds a share $x_i$ can further split their share into $j$ subshares $\xi_1, \dotsc, \xi_j$ in the same way, such that $x_i = \xi_1 + \dotsm + \xi_j \mod m$. If they then discard the original share $x_i$, they'll have expanded the number of shares from $n$ to $n+j-1$. Further, this expansion is completely transparent to the other participants, in that reconstructing the original secret still requires merely adding up all the $n+j-1$ shares modulo $m$.

I can't right now think of any obvious way to devise an $k$-out-of-$n$ secret sharing scheme that could be similarly expanded into an $(k+j)$-out-of-$(n+j)$ scheme by some subset of less than $k$ participants, but I wouldn't be surprised if one did exist.

Addendum: Now that I'm not quite as tired as I was when I first wrote the answer above, I see that the trick I used does not generalize the way the OP apparently wants. In particular, we can prove the following:

Lemma 1: It is not possible to expand an effective $(k,n)$ threshold secret sharing scheme into an effective $(j,m)$ threshold scheme, where $m-j > n-k$, without access to at least $k$ shares.

Proof: Already given by Dilip Sarwate. Essentially, if the holders of $k-1$ shares could do this, they could assign all the $m-n$ new shares to themselves, and so obtain $k+m-n-1 \ge j$ new shares, which would let them recover the secret under the expanded scheme and thus break the original scheme.

Lemma 2: It is not possible to expand an effective $(k,n)$ threshold secret sharing scheme into an effective $(j,m)$ threshold scheme, where $j > k$, without access to at least $n-k+1$ shares.

Proof: As above, if the holders of $n-k$ shares could do this, then the holders of the remaining $k$ shares could still recover the secret, thus breaking the new scheme.

Put together, these lemmata yield the following theorem:

Theorem: It is not possible to expand an effective $(k,n)$ threshold secret sharing scheme into an effective $(j,m)$ threshold scheme, where $m > n$, without access to at least $k$ or $n-k+1$ shares.

For lemma 1, the lower bound of $k$ shares is tight, as shown by poncho. For lemma 2, my example above shows the tightness of the lower bound for the specific case of $k=n$; I'm not sure whether or not it can be tightened further for $k < n$.

Of course, if you're willing to allow more general secret sharing schemes, where not all shares are equivalent, then various kinds of expansion are indeed possible. In particular, it's always possible for any shareholder(s) to further share their own shares with any number of people using any secret sharing scheme of their choosing. These derived shares will not, however, generally be equivalent to the original ones.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. This is along the lines of what I was looking for. The question of course is can it work for non n out of n schemes? $\endgroup$ – imichaelmiers Oct 24 '11 at 16:33
  • $\begingroup$ This scheme gives the holder of any share the power to unilaterally change the scheme. Now more shares have to be present before the secret can be recovered by the group, and the other group members (who did not participate in the share splitting) may well object. If the $i$-th share holder splits his share but retains his original share in addition to his portion of the split share, then the $k$ original share holders can still recover the secret while the new holders of the split shares essentially become second-class citizens. Just something for the OP to think about. $\endgroup$ – Dilip Sarwate Oct 24 '11 at 21:38
  • $\begingroup$ I changed a $j$ into a $k$ in the Proof of Lemma 1, which is what I think was intended. Please roll back if you did mean to say $j$. $\endgroup$ – Dilip Sarwate Dec 4 '12 at 11:43
  • $\begingroup$ @Dilip: I did mean to say $j$. The hypothetical expanded scheme requires $j$ shares to reconstruct the secret, while the original scheme is supposed to require $k$. If the holders of $k-1$ shares under the original scheme could somehow obtain $j$ or more shares under the new scheme, that would break the original scheme, contradicting the assumption that the original scheme was secure. $\endgroup$ – Ilmari Karonen Dec 4 '12 at 14:18
  • $\begingroup$ But if the holders of $k-1$ shares can get together and construct just one additional share (instead of $j > 1$) without knowing the secret, they have broken the original scheme which has the property that knowledge of $k-1$ or fewer shares is insufficient to reconstruct the secret but $k$ (or more) shares suffice to reconstruct the secret. Yes, getting more than one new share also breaks the original scheme, and indeed the expanded scheme is also broken in that any $k-1$ shareholders can construct more shares and break the new scheme. $\endgroup$ – Dilip Sarwate Dec 4 '12 at 14:25
6
$\begingroup$

Suppose we have a $(k, n)$ threshold scheme meaning that there are $n$ shares of a secret distributed to different parties, and any $k$ shares can be used to re-create the secret. A new person joins the club and wants to have a share of the secret too. I contend that the secret must be available to a trusted party who can create the extra share. Because if someone with little knowledge of the secret (or even as much knowledge as a cabal of $k-1$ shareholders trying to break the scheme) could create a new share of the secret, then this someone could repeat the process many times until $k$ shares are available, and thus recover the secret via the standard reconstruction technique. Now, it is possible to have a mathematical algorithm or computer program that will take $k$ (or more shares) and create new shares without the secret being explicitly reconstructed, that is, none of the quantities used internally or stored anywhere (register or memory cell or disk or tape drive) will actually be the secret itself and so the new share creation process is safe from the casual eavesdropper. However, a savvy opponent who can view the process or get a core dump from the processor will be able to recreate the secret.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Agreed. Hence why I said along those lines. Obviously if a subset of k people can generate a fresh full (1/n) secret share, then they could colude and beat the system. However, what if they could create a share that didn't have a full share of the information (b/c they don't have it themselves).But when combined with others ( issued by a different subset), could reconstruct the full share. It seems that we certainly would have left the realm of information theoretically secure schemes, but it still might be possible from a computationally secure standpoint. $\endgroup$ – imichaelmiers Oct 23 '11 at 21:15
  • $\begingroup$ For a $(k,n)$ threshold scheme, $k$ people can re-create the secret; in fact they recover not just the secret but also the polynomial $f(x)$ with randomly chosen coefficients for $x$, $x^2, \ldots, x^{k-1}$. Remember that $f_0$ is the secret and that $(\alpha_i, f(\alpha_i))$ are the shares. So once $k$ people have recovered $f(x)$, they can create additional shares. They might even (possibly inadvertently) re-create shares $(\alpha_j, f(\alpha_i)$ that are in the possession of other people not currently present and hand them out to their friends waiting outside the meeting room. $\endgroup$ – Dilip Sarwate Oct 24 '11 at 17:33
4
$\begingroup$

Actually, this appears to be quite straight-forward.

I'll give you an example of this using Shamir's original method: in Shamir's method, the trusted party which generates the shares picks a random polynomial, with the secret as the constant element, and then evaluates that polynomial over various nonzero element, and distributes the pairs $(e, P(e))$ as the shares. Now, to implement what you are requesting, and trusted party wouldn't discard the polynomial, but instead store it somewhere secret. When a request comes in for another share, he'd pick a fresh nonzero element $f$, and generate a fresh share $(f, P(f))$.

Obviously, this is just extending the share distribution task over time, and so it can be done by any secret sharing method. In addition, we don't even need the trusted party to do this (at least, with Shamir's method); if we can get people with $N$ separate shares, those shares are enough to allow us to reconstruct the polynomial, and create fresh shares. The only tricky part might be finding shares that haven't already been distributed; one obvious way around this is to use a large field (say, one with $\ge 2^{128}$ elements), and pick fresh shares randomly.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Yeah that obviously works. I wanted to do this without having any trusted authorities around or anyone learning the secret. $\endgroup$ – imichaelmiers Oct 20 '11 at 22:40
  • 2
    $\begingroup$ Well, someone who can generate fresh shares obviously can get the secret (by the simple expedient of generating N distinct fresh shares, and use the newly minted shares to recover the secret). Hence, I don't see any alternative to either keeping the secret around explicitly (that is, keeping the parameters that the trusted party used), or doing it implicitly by having N people with shares cooperate to generate fresh ones. $\endgroup$ – poncho Oct 21 '11 at 3:34
  • 2
    $\begingroup$ "Now, to implement what you are requesting, and trusted party wouldn't discard the polynomial, but instead store it somewhere secret." Perhaps it is worth pointing out that by storing the coefficients of the polynomial, the trusted party is actually storing the secret itself "in the clear" as the constant term of the polynomial being stored. If the anticipated number of future requests for shares is fairly small compared to the number who must be present for the secret to be recovered, storing a few $(f, P(f)$ to meet sucg future requests needs might be a better solution. $\endgroup$ – Dilip Sarwate Oct 22 '11 at 1:03
2
$\begingroup$

The Lagrange interpolation polynomial $L(x)$ is evaluated at $x=0$ to get the secret (the constant term). It can just as easily be evaluated at any $x$ to get another share. This requires that the threshold $k$ number of shares are present, just as they would be required to evaluate $L(0)$ to get the secret.

This approach does not require one to store the polynomial or re-construct the secret. As others have pointed out, however, there is a possibility that this will generate shares that have already been distributed, unless the $x_i$ of each distributed share is recorded and not repeated. This may or may not be important, depending on your security needs, as it can sometimes be ok to distribute identical shares.

(Edit: This clearly does not meet the OP's requirement that not all original parties have to be online at the same time. The threshold number of parties need to be present to make a new share. However, this does away with the original trusted authority.

From the standpoint that the secret must never be calculated or visible, this works only if the threshold number of parties calculate $L(x_i)$ for share $x_i$. The obvious caveat is that there is nothing stopping these parties from calculating $L(0)$ while they're at it, so it's not 100% secure.

Just another way to think about the problem.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ How is the Lagrange interpolation polynomial created in order to evaluate it at some $x_i$? $\endgroup$ – Dilip Sarwate Dec 8 '12 at 23:23
  • $\begingroup$ In the typical programming scenario, it wouldn't be created then evaluated. It would just be evaluated at xi by summing the values of the basis polynomials evaluated at xi. The same programming construct the parties use to evaluate L(0) can be used to evaluate L(xi). Not sure if you need me to recreate the steps or the polynomial here, or if you are getting at something else? $\endgroup$ – ampersand Dec 9 '12 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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