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.

Here's a scenario I want to handle with a secret sharing scheme:

  1. Alice wants to share the secret $S$ with Bob, Charlie and Dave. Alice generates private shares based on $S$ for Bob, Charlie and Dave, and communicates them to their intended recipients via a secure channel.
  2. Alice generates a parameter $P$ based on $S$ and publishes it.
  3. Each of Bob, Charlie and Dave can reconstruct the secret using $P$ and their personal share. Eve can't reconstruct it, even if she knows $P$.
  4. Alice needs to change the secret. Alice recomputes only a new $P$. All private shares of the participants stay the same.
  5. Each of Bob, Charlie and Dave can reconstruct the new secret using the new public parameter $P$.
  6. Alice wants to add a new participant Fred and remove participant Bob from the group. Alice recomputes a new $P$ and a new private share for Fred.
  7. Each of Charlie, Dave and Fred can reconstruct the secret using their shares and the new $P$. Bob can't reconstruct the secret using the new $P$.

Is there some secret sharing scheme that can handle such a scenario? I found myself some secret sharing schemes like Shamir's secret sharing or secret sharing using the Chinese remainder theorem, but those do no satisfy all my requirements.

share|improve this question

migrated from stackoverflow.com Jul 18 '13 at 15:11

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

add comment

3 Answers 3

up vote 1 down vote accepted

Basically, use a bunch of independent one-time pads.


I will use array slicing, where array[x:y] returns the length y-x subarray
consisting of the entries from x inclusive to y exclusive.

k = computational_security_parameter
L = length_of_the_secret
n = number_of_changes_at_which_you_lose_information-theoretic_security
userinfo = [["Bob",Bob's_share],["Charlie",Charlie's_share],["Dave",Dave's_share]]

define makeparameterfor(m,userinfo,secret):
 P = [m]
 if m < n:
  for [name,share] in userinfo:
   append [name,(share[m*L:(m+1)*L] xor secret)] to P
 else:
  for [name,share] in userinfo:
   append [name,enc(share[n*L:(n*L)+k],secret)] to P
 return P

countervalue = 0

define generateparameter(userinfo,secret):
 return makeparameterfor(0,userinfo,newsecret)

define reconstruct(username,usershare,parameter):
 namefound = False
 for entry in parameter:
  if entry[0] == username and length(entry) != 1:
   [name,ctext] = entry
   namefound = True
  break
 if namefound == False:
  throwexception("invalid reconstruction attempt")
 else:
  cv = parameter[0]
  if cv < n:
   return ctext xor share[cv*L:(cv+1)*L]
  else:
   return dec(share[n*L:(n*L)+k],ctext)

define changesecret(userinfo,newsecret):
 countervalue = max(n,countervalue+1)
 return makeparameterfor(countervalue,userinfo,secret)

define addnewuser(oldparam,secret,name,share):
 append [name,share] to userinfo
 cv = oldparam[0]
 newP = oldparam
 if cv < n:
  append [name,(share[cv*L:(cv+1)*L] xor secret)] to newP
 else:
  append [name,enc(share[n*L:(n*L)+k],secret)] to newP
 return newP

define removeuser(username,oldparam):
 for [name,share] in userinfo:
  if name == username:
   remove [name,share] from userinfo
 newP = [oldparam[0]]
 for [name,ctext] in oldparam:
  if name != username:
   append [name,ctext] to newP
 return newP
share|improve this answer
    
Looks very interesting, can you explain the used variables a bit more? I must confess, I don't understand completely what you do. –  LostAvatar Jul 19 '13 at 10:26
    
The core idea is that Alice gives each user a bunch of one-time pads, and has the public parameter indicate which ciphertext is for which user and which pad they should decrypt with. However, since one can only achieve information-theoretic security for an a-priori bounded number of changes in the secret, one would use a computational encryption scheme after running out of one-time pads. $\hspace{.62 in}$ –  Ricky Demer Jul 19 '13 at 19:54
add comment

An obvious solution that handles steps 1–5 (changing the secret) would be for Alice to generate a random encryption key $K$ (of, say, 128 bits), encrypt $S$ with $K$ to generate $P$, and then share $K$ with the other participants using a conventional secret sharing scheme such as Shamir's.

Indeed, if all the shareholders (other than Alice) are always needed to reconstruct the secret, you don't even need to use Shamir's scheme: trivial XOR secret sharing (where Alice gives all but one of the shareholders a random bitstring, and gives the last one the XOR of all the other shares plus the secret) will do the job just as well.

Indeed, with XOR secret sharing, steps 6 and 7 (adding and removing participants) can also be achieved: Alice simply sends random bitstrings to the new participants, computes a new key $K$ by XORing together the shares of all the active participants, and encrypts the secret $S$ with the new $K$ to obtain the new $P$.

In fact, if the key $K$ is (at least) as long as the secret $S$, you don't even really need a separate encryption step: as long as $K$ is random, you can simply XOR $K$ with $S$ to obtain $P$, making this an instance of one-time pad encryption.

This also works with Shamir's scheme, as long the reconstruction threshold equals the number of shareholders; Alice can just send random shares to all the shareholders, reconstruct a (random) key $K$ by applying Shamir's reconstruction algorithm to the shares of the active participants, and use that key to encrypt the secret.

However, note that all these protocols suffer from some fundamentally unavoidable flaws:

  • if the shareholders can remember old $P$ values, they will be able to reconstruct old secrets even after Alice has changed them, and

  • if removed shareholders can remember their old shares (and the old $P$), they can still reconstruct the secret (assuming the other old shareholders cooperate) as it was before they were removed. However, if the secret $S$ is changed whenever participants are removed, the remove participants won't be able to contribute anything useful to reconstructing the new secret.


Edit: Based on the comment below, it seems I misunderstood the question: you want each of Bob, Charlie and Dave alone to be able to reconstruct the secret using $P$.

A simple way to achieve this would be for Alice to distribute different random keys $K_i$ to each of the other participants $i$, encrypt her own key $K$ with each of $K_i$, and combine the ciphertexts into $P$.

Of course, the down side to this method is that the length of $P$ would be proportional to the number of participants, which could be a problem if that number is large. However, I'm not sure if it's possible to do any better, and I suspect it may not be.

share|improve this answer
    
I might was unclear at this point, I don't want all shareholders to be needed. I actually think of a (2,n) treshold, where every shareholder other than Alice can reconstruct the secret only with Alice's share (P). –  LostAvatar Jul 18 '13 at 14:43
    
I also thought about something similar to your edited answer. You are right with the mentioned donwside, but I think, there is something more dangerous in it. Someone who knows one or more $K$ (because he had permission to encrypt them before) can use the other parts of $P$ in a known plaintext attack and could maybe get knowledge about the other $K_i$ and can get the secret, even if Alice has chosen not to give him permission to do so. –  LostAvatar Jul 18 '13 at 17:52
    
If the encryption method used is secure, it should not be vulnerable to known-plaintext attacks. –  Ilmari Karonen Jul 18 '13 at 18:36
    
@user1541458 : $\:$ Do you want information-theoretic security? $\;\;\;$ –  Ricky Demer Jul 18 '13 at 19:27
    
@Ricky Demer. Would be desirable. I had found a solution to my problem by myself using chinese remainder theorem, but this was rejected out of exactly this reason. I tried to give each participant a secret prime number $p_i$ and calculate a public parameter for the congruence system $X \equiv p_i \oplus S~mod~p_i$ for all $i$ with permission ($p_i \oplus S < p_i$ as a requirement to get the chance to reconstruct S unambigously). That was rejected because I could not prove the theoretic security of this approach. –  LostAvatar Jul 19 '13 at 5:41
add comment

I actually have a patent on a technique that can be used here -- or rather, I put in an application and then left that employer, and I don't know whether the patent issued; it seems based on this Google patents link that it's still an application, 12 years on.

Here's the idea. Shamir m-of-n secret sharing is a series of pairs $(x_i, y_i)$ such that

  1. All pairs (x, y) satisfy Equation E: $a_m x^m + a_{m-1} x^{m-1} + ... + a_0 = y$
  2. There are in total n pairs with n > m (obviously)

Now, say the x values are drawn from a series. Maybe $x_i = i$, or $3i$, or $i^2$. This series is a system parameter; all participants know it, and it doesn't matter if it's also known to non-participants.

Say also that m > n/2. This is a reasonable assumption as it means a majority of participants is required to recover the secret.

Say also that the secret is unstructured, such as a 128-bit random number. This is reasonable, you can do a lot of things with a 128-bit random number.

Say I get a group of $m$ people together to change the secret. These people are the participants, and I'll use "sharers" to mean everyone who knows a share. The first thing we do is work out the existing secret. The novel steps are:

  1. As part of calculating the secret, we have calculated the coefficients of Equation E. That means that we know the shares of those sharers in the group who haven't participated in this transaction.
  2. We calculate those shares. There are n-m < m of these.
  3. We select (2m-n) of the participants in the current transaction and pick their new shares randomly. We now know (2m - n) + (n-m) = m shares of a new secret -- the shares of the non-participating sharers, which we've just calculated, and the shares of the (2m-n) participants, which we've just assigned randomly.
  4. This is enough to calculated the new secret, so we calculate that secret and its equation E
  5. We use the new equation E to calculate the shares of the other (n-m) participants.
  6. All the participants store their newly calculated shares; the other sharers don't need to be notified.

This means that we've been able to update the shared secret without having to contact the other sharers and without them having to update their shares. Which is quite cute.

I don't know if this exactly meets your requirements. As other answerers have noted, if Alice is just worried about a series of pairwise relationships, she can do everything with XOR or similar. But this approach has a nice flexibility to it and I think works in the same trust model as standard secret sharing.

I'm not sure of the patent situation -- Baltimore were eventually bought by Verizon Business but I think this application lapsed. If you think this technique might be helpful to you, I'll reach out to find the owners and see if there's anything we can do to put it in the public domain.

share|improve this answer
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.