Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
If I understand your question right, you have:
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).
