Editing Secret sharing (section)

== Efficient secret sharing ==
The trivial approach quickly becomes impractical as the number of subsets increases, for example when revealing a secret to any 50 of 100 players, which would require <math>\binom{100}{50} \approx 1.009\times 10^{29}</math> schemes to be created and each player to maintain <math>\binom{99}{49} \approx 5.04\times 10^{28}</math> distinct sets of shares for each scheme. In the worst case, the increase is exponential. This has led to the search for schemes that allow secrets to be shared efficiently with a threshold of players.

===Shamir's scheme===
{{main|Shamir's secret sharing}}

In this scheme, any ''t'' out of ''n'' shares may be used to recover the secret.  The system relies on the idea that one can construct a unique [[polynomial]] of degree {{nowrap|''t'' − 1}}, such that each of the ''t'' points lies on the polynomial.  It takes two points to define a straight line, three points to fully define a quadratic, four points to define a cubic curve, and so on. That is, it takes ''t'' points to define a polynomial of degree {{nowrap|''t'' − 1}}.   The method is to create a polynomial of degree {{nowrap|''t'' − 1}} with the secret as the first coefficient and the remaining coefficients picked at random.  Next find ''n'' points on the curve and give one to each of the players.  When at least ''t'' out of the ''n'' players reveal their points, there is sufficient information to fit a {{nowrap|(''t'' − 1)}}th degree polynomial to them, the first coefficient being the secret.

===Blakley's scheme===
Two [[Parallel (geometry)|nonparallel]] lines in the same [[plane (mathematics)|plane]] intersect at exactly one point. Three nonparallel planes in space intersect at exactly one point. More generally, any ''n'' nonparallel [[dimension|{{nowrap|(''n'' − 1)}}-dimensional]] [[hyperplane]]s intersect at a specific point. The secret may be encoded as any single coordinate of the point of intersection.  If the secret is encoded using all the coordinates, even if they are random, then an insider (someone in possession of one or more of the [[dimension|{{nowrap|(''n'' − 1)}}-dimensional]] [[hyperplane]]s) gains information about the secret since he knows it must lie on his plane.  If an insider can gain any more knowledge about the secret than an outsider can, then the system no longer has [[information theoretic security]].  If only one of the ''n'' coordinates is used, then the insider knows no more than an outsider (i.e., that the secret must lie on the ''x''-axis for a 2-dimensional system).  Each player is given enough information to define a hyperplane; the secret is recovered by calculating the planes' point of intersection and then taking a specified coordinate of that intersection.

<div align="center">
{| border="0" cellspacing="2px" style="margin-left: auto; margin-right:auto;" width="600px"
| [[File:Secretsharing 1.svg|250px|One share]]
| [[File:Intersecting Planes 2.svg|250px|Two shares intersecting on a line]]
| [[File:Secretsharing 3-point.svg|250px|Three shares intersecting at a point]]
|-
| colspan="3" | ''Blakley's scheme in three dimensions: each share is a [[plane (mathematics)|plane]], and the secret is the point at which three shares intersect. Two shares are insufficient to determine the secret, although they do provide enough information to narrow it down to the [[line (mathematics)|line]] where both planes intersect.''
|}
</div>

Blakley's scheme is less space-efficient than Shamir's; while Shamir's shares are each only as large as the original secret, Blakley's shares are ''t'' times larger, where ''t'' is the threshold number of players. Blakley's scheme can be tightened by adding restrictions on which planes are usable as shares. The resulting scheme is equivalent to Shamir's polynomial system.

=== Using the Chinese remainder theorem ===
{{main|Secret sharing using the Chinese remainder theorem}}

The [[Chinese remainder theorem]] can also be used in secret sharing, for it provides us with a method to uniquely determine a number ''S'' modulo ''k'' many [[pairwise coprime]] integers <math>m_1, m_2, ..., m_k</math>, given that <math>S < \prod_{i=1}^k m_i</math>. There are two secret sharing schemes that make use of the Chinese remainder theorem, Mignotte's and Asmuth-Bloom's Schemes. They are threshold secret sharing schemes, in which the shares are generated by reduction modulo the integers <math>m_i</math>, and the secret is recovered by essentially solving the system of congruences using the Chinese remainder theorem.