As last year I’m lecturing our 3rd year / 4th year / M.Sc. course on cipher systems. As part of the M.Sc. course I cover the Shamir Secret Sharing Scheme. Here is Shamir’s idea generalized to arbitrary commutative rings, with an application to secret sharing in a hierarchical organization. The idea is very obvious, so no originality is expected or claimed.
For a practical example, imagine that I have a critically important 20GB file. Using a secret-sharing scheme with threshold , I issue shares of the file (each most probably still of size 20GB) to Amazon, Degoo (who promise a ‘top secret cloud drive’) Dropbox and Microsoft. If any single provider goes out of business, or maliciously corrupts the share, the file can still be reconstructed from the remaining three shares. Depending on how much I trust them (and the computational resources available on the various platforms), the reconstruction could be done in the cloud, or on my own machine. In the latter case, a provider can learn the secret only if three of them collude by pooling their shares: this would presumably be a serious breach of all their terms of service.
Fix and let . Fix a commutative ring and distinct ideals , of . The secret is an element of . We suppose that has a subset such that
- if is a -set then the composition is injective;
- if is a -set then the composition is surjective.
In particular (2) implies that is surjective.
To share a secret , pick such that mod ; the share for algebraist is then . By hypothesis, for each such that , the unique element of congruent to modulo for each is itself. Therefore any (or more) algebraists can pool their shares and determine , and hence .
Fix a prime and distinct . Take , , and and . (Thus the secret is , and the share for algebraist is .) Property (1) holds because a polynomial of degree is uniquely determined by its values at the distinct points for . Moreover, since the map
is a linear isomorphism whenever , we have (2) in the strongest possible form.
For another special case, fix a prime , a parameter (of which more later) and consecutive primes with . Let . Take , , and
Since each is uniquely determined by its residues modulo any of the , we have (1). Suppose the algebraists numbered pool their shares. They can learn modulo . Now contains ‘candidate secrets’ of the form where . Provided is sufficiently large,
Therefore the ‘candidate secrets’ cover all residue classes modulo , and so (2) holds. Moreover, the sizes of the fibres over each vary by at most with , and have mean size . Provided is large, all the primes have about the same size, and the mean fibre size is approximately .
Provided is large, this variation in the fibre leaks very little information. For small is it a problem. For example, take , , , and , , , . Thus . For the secret we choose , lifting it to
The shares are then . If algebraists and cooperate they can learn modulo . This leaves
possibilities for . The mean fibre size is and since , there are fibres of size and of size (namely those for , , and ). Choosing one of these at random gives them a chance of guessing the secret.
Choosing a small fibre is a good heuristic, but not infallible: it is possible that the secret corresponds to a large fibre—for example if algebraists and pool their shares then the fibres for and have size , and the rest have size .
What other rings are amenable to the generalized Shamir scheme?
Secret sharing in a hierarchy
One possible answer to this question is ‘multivariable polynomial rings’. Here is an idea along these lines.
Let . Fix and thresholds , with and . Let be the set of polynomials with and . Fix distinct non-zero and distinct . The aim is to share a secret between teams where team consists of people . For this, choose such that . For each , let . For each and each , let . Issue as the share to person .
The shares are the shares in a normal Shamir Secret Sharing Scheme for . By the linear isomorphism in the first example above, when people in the team cooperate to learn , they in fact learn itself. Suppose that teams learn . Then since , they can cooperate to learn , and hence . Given a -subset of , when the teams numbered in pool their shares they learn nothing useful, since for each , there is a unique polynomial with such that and for each . Explicitly,
This polynomial is consistent with the secret being ; since takes each value in equally often as varies over the polynomials in of degree at most no useful information is learned.
It should be admitted that one can arrive at essentially the same situation, more simply, by sharing the secret between teams, and then sharing each 'team-share' between the people in each team, each time using the normal Shamir Scheme.