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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ You might find the more general question on arbitrary sharing structures useful $\endgroup$– CryptographeurCommented Nov 5, 2013 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$– CryptographeurCommented Nov 12, 2013 at 15:22
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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$ Commented Nov 5, 2013 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$– xkcdCommented Nov 12, 2013 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$– ponchoCommented Nov 12, 2013 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$ Commented Nov 12, 2013 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$– ponchoCommented Nov 12, 2013 at 18:23
$\begingroup$
$\endgroup$
4
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.
answered Nov 5, 2013 at 13:54
-
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$– ponchoCommented Nov 5, 2013 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$ Commented Nov 5, 2013 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$– xkcdCommented Nov 12, 2013 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$ Commented Nov 12, 2013 at 15:20