1
$\begingroup$

I am learning about Shamir's secret sharing scheme and I've come across this problem:

Let's suppose we have a combination of a (3, 6) and (1, 2) Shamir's schemes, where participants $P_1$ and $P_2$ get shares in both schemes and others in the first scheme only. The shared secret is the sum of the two shared secrets. Is such a scheme perfect? My guess is that it is, because I can't see how some unprivileged group would learn anything about the secret.

$\endgroup$
  • 2
    $\begingroup$ Can you explain (or re-write) the sentence "The shared secret is the sum of the two shared secrets"? For a variant and expanded version of such ideas, see this question and its answers. $\endgroup$ – Dilip Sarwate Jan 10 '18 at 17:37
  • 1
    $\begingroup$ How are the two component parts (the two secrets that are shared whose sum is equal to the real secret) generated? Uniformly random from the finite-field? $\endgroup$ – mikeazo Feb 9 '18 at 19:21
1
$\begingroup$

It depends on the access structure. It is perfect for the structure on $\{P_1, P_2\}$. However no subsets of players from $Q=\{P_3,..,P_6\}$ have any information on the secret since they only now one part of the sum.

$\endgroup$
  • $\begingroup$ So does that mean it's perfect for the whole access structure? $\endgroup$ – Gogis Jan 10 '18 at 23:24
1
$\begingroup$

From your description, the second secret is only known to $P_1$ and $P_2$. To get the first secret, we need at least 3 of $\{P_1,\ldots,P_6\}$. Shamir's secret sharing scheme itself is secure. But I am not sure what is your definition of a perfect scheme. Btw, why do you use a $(1,n)$ threshold scheme? This basically tells the secret to everyone who has a share.

$\endgroup$
1
$\begingroup$

If I understand your question right, you have:

  • A secret $S$, which is the sum of two sub-secrets $S_1 + S_2 = S$.
  • Six participants (whom I'll call $\rm A$, $\rm B$, $\rm C$, $\rm D$, $\rm E$ and $\rm F$) who the secret is to be shared among.
  • A scheme wherein:
    • $S_1$ is shared between $\rm A$ and $\rm B$ using Shamir's secret sharing with a reconstruction threshold of $1$ share (which really just amounts to giving $S_1$ to both of those participants), and
    • $S_2$ is shared among all six participants using Shamir's secret sharing with a threshold of $3$.

You want to know whether the scheme described above is a perfect secret sharing scheme for $S$, i.e. whether any set of participants not authorized to recover $S$ can learn any information about it from their shares.


First of all, I should note that you haven't actually specified which sets of participants are supposed to be authorized to recover $S$ under your scheme, and so it's impossible to tell whether the scheme is perfect or not.

Obviously, under your scheme, any set of three or more participants that includes at least one of $\rm A$ and $\rm B$ can recover both $S_1$ and $S_2$, and thus also their sum $S$. If we take this as an implicit definition of the access structure for your scheme, i.e. if we assume that these are exactly the sets of participants who are supposed to be able to reconstruct $S$, then we can check whether or not your scheme leaks any information about $S$ to any other sets of participants. But that's a big unstated assumption.


In any case, there's another, subtler ambiguity in the definition of your scheme: what, exactly, do you mean by saying that $S$ is the "sum" of $S_1$ and $S_2$?

If you mean an ordinary sum of natural numbers, then no, your scheme is not perfect. In particular, if $S_1$ and $S_2$ are both non-negative, then it's guaranteed that $S \ge S_1$, and thus either of $\rm A$ and $\rm B$ alone can learn a non-trivial lower bound on $S$ just based on their shares alone. Similarly, any three of the six participants can learn the non-trivial lower bound $S \ge S_2$, even if none of them are $\rm A$ or $\rm B$.

More generally, even if $S_1$ and $S_2$ can be negative, learning the value of one of them still gives statistical information about their sum. This makes your scheme non-perfect, for the same reason why Shamir's secret sharing over the real numbers is not a perfect secret sharing scheme.


On the other hand, if $S_1$ and $S_2$ are arbitrary elements of some finite group, both chosen independently and uniformly at random from the entire set of group elements, and if we take $S$ to be their sum using the group addition law, then it can be shown that $S$ is pairwise independent of both $S_1$ and $S_2$. Thus, knowing either of the sub-secrets gives no information about $S$, making your scheme perfect (for the implicit access structure described above).

In fact, it's not hard to show that we can also achieve the same result by choosing $S$ from the group according to any distribution, not necessarily uniformly, choosing one of the sub-secrets (e.g. $S_1$) uniformly at random from the whole group, and letting $S_2 = S - S_1$ (where the minus sign denotes subtraction according to the group law). This still obviously makes $S$ and $S_1$ pairwise independent, and it's not too hard to show that the same is, in fact, true of $S$ and $S_2$ as well!

What we're really doing here is improvising a perfect 2-out-of-2 (or, more generally, $n$-out-of-$n$) threshold sharing scheme using finite group addition, using this scheme to create two shares $S_1$ and $S_2$ of the master secret $S$, and then further sharing these two shares using Shamir's scheme (which is also perfect). The general result here, which you may wish to prove, is that such hierarchical composition of perfect secret sharing schemes is itself perfect (for the access structure matching the share hierarchy).

$\endgroup$

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.