4
$\begingroup$

I have studied Sharmir's scheme as well as the multiple assignment scheme proposed by M. Ito. My question is if anyone can tell me if the following scheme is theoretically secure:

Terms:

P = set of participants

B = Access structure

A = Access set (authorised set within access structure)

t = cardinality of Access structure (|B|)

d = cardinality of Access set (|A|)

S = the secret

So the scheme is extremely inefficient in that it involves creating exactly t different (d,d) Shamir schemes, such that there will be t different randomly chosen polynomials that all share the same secret s

Edit:
So the scheme is an access structure secret sharing scheme, basically it defines certain subgroups of a group of participants that are valid and can therefore reconstruct a secret.

For instance if there was a group of people p1,p2,p3 and an access structure of {p1p2, p1p3} then only the combination of p1 and p2 or p1 and p3 should be able to uncover the secret. so p1p2 and p1p3 are valid subgroups and p2p3 is an invalid subgroup and should therefore not be able to uncover the secret.

This scheme is theoretically insecure if an invalid group can uncover any information.This includes uncovering or computing a number that is NOT S (the secret) and knowing that this number is not the secret. so if p2p3 compute their shares and find a number S' that they know is not the secret then the scheme is insecure!

Example:

Let S = 6, P = {P1,P2,P3}, B = {P1-P2,P1-P3) such that P1 and P2 can find the secret as well as P1 and P3

Now we generate 2 shamir schemes with the same secret:

f1(x) = 6 + 4x

f2(x) = 6 + 7x

so we need two shares from each scheme:

s1, s2 = (1,10) and (2,14)

s'1, s'2 = (1,13) and (2,20)

P1 gets s1 and s'2

P2 gets s2

P3 gets s'2

Can anyone think of any reason as to why this scheme is not theoretically secure, it is very inefficient but as far as i know it is secure, i just don't know how to prove or disprove it.

many thanks

$\endgroup$
  • $\begingroup$ I've tried various different sized groups of both participants, access structures and access sets. I'm almost certain that this method is in fact secure, just terribly inefficient. If anyone finds anything please let me know $\endgroup$ – Louis Dec 24 '15 at 10:46
  • $\begingroup$ It might be easier to understand (and answer) your question if you started it by telling us just what, exactly, your scheme is supposed to accomplish (i.e. allow legitimate users to do, and prevent attackers from doing). $\endgroup$ – Ilmari Karonen Dec 28 '15 at 7:58
  • $\begingroup$ So the scheme is an access structure secret sharing scheme, basically it defines certain subgroups of a group of participants that are valid and can therefore reconstruct a secret. For instance if there was a group of people p1,p2,p3 and an access structure of {p1p2, p1p3} then only the combination of p1 and p2 or p1 and p3 should be able to uncover the secret. so p1p2 and p1p3 are valid subgroups and p2p3 is an invalid subgroup and should therefore not be able to uncover the secret. This scheme is theoretically insecure if an invalid group can uncover any information. $\endgroup$ – Louis Dec 28 '15 at 8:05
  • $\begingroup$ This includes uncovering or computing a number that is NOT S (the secret) and knowing that this number is not the secret. so if p2p3 compute their shares and find a number S' that they know is not the secret then the scheme is insecure! hope this makes it more clear @IlmariKaronen $\endgroup$ – Louis Dec 28 '15 at 8:09
  • $\begingroup$ OK, I think I can follow your notation now. You might want to edit that information into the question itself, though. $\endgroup$ – Ilmari Karonen Dec 28 '15 at 8:13
1
$\begingroup$

Yes, your scheme is trivially correct and secure. This follows from the fact that:

  1. Shamir's secret sharing is correct: any group of participants with at least the threshold number of shares can reliably reconstruct the secret; and

  2. Shamir's secret sharing is perfectly secure: no group of participants with less than the threshold number of shares can learn any information about the secret.

Since your subschemes are constructed independently except for having the same secret, the only way in which knowledge learned from one subscheme could help in breaking another subscheme is if this knowledge somehow involved the secret. But since Shamir's secret sharing, by construction, reveals no information about the secret without access to the threshold number of shares, this is not possible.

Another way to show this is to assume that a group already has, for each subscheme, access to just one less share than the threshold number for that subscheme. (We can do this without loss of generality, since giving an attacker access to more shares never hurts their chances of recovering the secret.) Then show that, for any possible secret value, there exists a unique assignment of the missing shares for each subscheme that will reconstruct that secret. (This is basically the standard proof for the security of basic Shamir's secret sharing, just with multiple sets of shares and polynomials.)

Also note that, since your subschemes are always $(n,n)$ schemes (i.e. they always require all shares to reconstruct the secret), you don't actually need the full power of Shamir's scheme. In particular, trivial secret sharing, e.g. based on XOR or modular addition, would work just as well.

$\endgroup$
  • $\begingroup$ Thank you so much, you've summed it up nicely and in an easy to understand manner! And yeah if it was up to me I would have used something like additive secret sharing as opposed to the more lengthy Shamir scheme. Once again thanks! @IlmariKaronen $\endgroup$ – Louis Dec 28 '15 at 9:15

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.