I am trying to find an implementation or variant of a (k, n) threshold cryptosystem (as described here Shamir's Secret Sharing) where we can fix at least one of the k key parts, i.e., instead of ANY k key parts able to decrypt the ciphertext I want at least one of the k key parts to be a certain/fixed key part. So sort of a joint account cheque where k out of n signatures are required but the signature of the accountant should always be there. Any ideas?

  • 1
    $\begingroup$ You might find the more general question on arbitrary sharing structures useful $\endgroup$ – Cryptographeur Nov 5 '13 at 14:31
  • $\begingroup$ There's a naive solution which might be acceptable: If you have $b$ committee members and one accountant, create $2b$ and give $b$ of them to the accountant? Then, set the threshold accordingly. $\endgroup$ – Cryptographeur Nov 12 '13 at 15:22

Here's an easy way to do it:

  • Take your secret $S$, and select a random value $R$ of the same size, and compute $T = S \oplus R$

  • Give the accountant the value $R$

  • Use a $(k-1, n-1)$ secret sharing method to share $T$ to the other parties.

The accountant plus any set of $k-1$ other parties can reconstruct the secret. And, any smaller subset cannot get any information on the secret $S$.

  • $\begingroup$ You can think of this method as applying Shamir Secret sharing amongst n-1 people, then a two-person xor share between them and the accountant. $\endgroup$ – Cryptographeur Nov 5 '13 at 14:15
  • $\begingroup$ But doesn't this add a problem with the order of the operation? I mean that in order for (lets say the bank) to recover the secret, first you will have to do the Shamir reconstruction with k - 1 and after that you will get T and then the accountant will share R so that the bank can get S. So am I right in understanding that in this scheme the accountant is not even part of the secret sharing parties, rather he acts more like a signing authority? To be more clear about my original question, what I had in mind was that the accountant is part of the group, a sort of first among equals. $\endgroup$ – xkcd Nov 12 '13 at 14:19
  • $\begingroup$ @xkcd: actually, you don't have to recombine things in precisely that exact order. If you prefer (and assuming $S$ and $R$ are combined with the field addition), an alternative implementation of the reconstructure is to do a field subtraction of $R$ from each share, and then the standard Shamir Secret Sharing reconstruction (and "field subtraction" == "exclusive or" if you're using $GF(2^n)$ in your Secret Sharing). $\endgroup$ – poncho Nov 12 '13 at 15:41
  • $\begingroup$ Assuming you do it in a relatively intuitive way, whoever actually goes about reconstructing the secret is going to learn something about the other inputs. This sounds like it might be an issue for your situation? $\endgroup$ – Cryptographeur Nov 12 '13 at 16:44
  • 1
    $\begingroup$ @user8911: I believe that is true for any secret sharing scheme; if you do it in the obvious way, whoever is doing the reconstruction sees everyone else's shares. $\endgroup$ – poncho Nov 12 '13 at 18:23

As pointed out in the comments, this is a poor choice since it does not maintain the security level of the secret sharing on which it is based.

For just one person, you can use Shamir except instead of storing the secret as point $f(0)$ use the point $f(t)$, where you give $t$ to the required person.

So, set up the scheme as $(k-1,n-1)$ for the other players. Then, between $k-1$ of them they can reconstruct the polynomail, but they require person $t$ to know where to evaluate it.

  • 3
    $\begingroup$ The problem with this idea is that $k-1$ people (not including the required person) can get some partial information on the secret; at the least, they can exclude those values which never occur as outputs of their reconstructed polynomial. This is probably not fatal; however we can do better. $\endgroup$ – poncho Nov 5 '13 at 14:01
  • $\begingroup$ True, at which point you risk significantly reducing the range of possible outputs (unless you've managed to hit an automorphism!). Certainly the xor is the more sensible solution $\endgroup$ – Cryptographeur Nov 5 '13 at 14:04
  • $\begingroup$ Hi @user8911, wouldnt $f(t)$ just create one more point in the polynomial, same as all the others? And the order problem I mentioned in the answer above will be applicable here too, as the accountant will have to be the last party to share its $t$. $\endgroup$ – xkcd Nov 12 '13 at 14:37
  • $\begingroup$ $f(t)$ is just a particular point calculated by evaluating the polynomial. The way SSS works is that using the shares you recalculate the polynomial, then the secret is the point $f(0)$. My suggestion was to store the secret as $f(t)$, but as poncho pointed out this doesn't work since you leak information about the solution space. $\endgroup$ – Cryptographeur Nov 12 '13 at 15:20

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.