Secret sharing

In cryptography, a secret sharing scheme is a method for distributing a secret amongst a group of participants, each of which is allocated a share of the secret. The secret can only be reconstructed when the shares are combined together; individual shares are of no use on their own.

More formally, in a secret sharing scheme there is one dealer and n players. The dealer gives a secret to the players, but only when specific conditions are fulfilled. The dealer accomplishes this by giving each player a share in such a way that any group of t (for threshold) or more players can together reconstruct the secret but no group of less than t players can. Such a system is called a (t, n)-threshold scheme (sometimes it is written as an (n, t)-threshold scheme).

Secret sharing was invented by both Adi Shamir and George Blakley independently in 1979.

A flawed secret sharing scheme

A true secret sharing scheme distributes the secret so that anyone with fewer than t shares has no more information about the secret than someone with no shares. As a simplistic example, consider a dealer who divides the secret "password" into the four shares "pa------," "--ss----," "----wo--," and "------rd," all of which are required to recover the original secret. A person with zero shares might know that the password consists of eight letters, but would not have any idea what those letters are. He would have to guess the password from 26⁸ = 208 billion possible combinations. A person with one share, however, would have to guess only six letters; he would face only 26⁶ = 308 million combinations. A person with three shares would only have to guess from 676 possibilities. This system is not a true secret sharing scheme because each share provides significant information about the content of the secret. Under an unconditionally secure secret sharing scheme, a person with three shares would still face 26⁸ = 208 billion combinations, while a person with four shares would face only one, i.e. he would know the secret completely. Several secret sharing schemes are said to be information theoretically secure and can be proved to be so, while others give up this unconditional security for improved efficiency while maintaining enough security to be considered as secure as other common cryptographic primitives. For example, they might allow arbitrarily large secrets to be protected by 128-bit shares, since the 2¹²⁸ possible shares are generally considered enough to stymie any conceivable present-day adversary.

Trivial secret sharing

There are several (t, n) secret sharing schemes for t = n, when all shares are necessary to recover the secret:

• Encode the secret as an integer s. Give to each player i (except one) a random integer r_i. Give to the last player the number (s - r₁ - r₂ - ... - r_n-1). The secret is the sum of the players' shares.
• Encode the secret as a byte s. Give to each player i (except one) a random byte b_i. Give to the last player the byte (s XOR b₁ XOR b₂ XOR ... XOR b_i) where XOR is bitwise XOR. The secret is the bitwise XOR of the players' shares.

Shamir's scheme

Two points uniquely define a line, three points define a parabola, four define a cubic curve, etc. More generally, n coordinate pairs (x_i, y_i) uniquely define a polynomial of degree n-1. The dealer encodes the secret as the curve's y-intercept and gives each player the coordinates of a point on this curve. When the players pool together enough shares, they can interpolate to find the y-intercept and thus recover the secret.

It would be impractical to use this scheme with conventional polynomials; the secret and the shares would generally be complex fractions that are difficult to store in a typical file. Consequently, the polynomial is typically defined over a finite field instead.

Shamir's scheme is space-efficient; each share is the same size as the original secret because the x-coordinates of each share can be known to all the players. This scheme also minimizes the need for random numbers; for every bit in the secret, the dealer must generate t random bits, where t is the threshold number of people.

Blakley's scheme

Two nonparallel lines in the same plane intersect at exactly one point. Three "nonparallel" planes in space intersect at exactly one point. More generally, any n n-dimensional hyperplanes intersect at a specific point. The secret may be encoded as any single coordinate of the point of intersection. The other coordinates must be random. Each player is given enough information to define a hyperplane; the secret is recovered by calculating the planes' point of intersection.

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 identical to Shamir's polynomial system.

Proactive secret sharing

If the players store their shares on insecure computer servers, an attacker could hack in and steal the shares. If it is not practical to change the secret, the uncompromised (Shamir-style) shares can be renewed. The dealer generates a new random polynomial with constant term zero and calculates for each remaining player a new ordered pair, where the x-coordinates of the old and new pairs are the same. Each player then adds the old and new y-coordinates to each other and keeps the result as the new y-coordinate of the secret.

All of the non-updated shares the attacker accumulated become useless. An attacker can only recover the secret if he can find enough other non-updated shares to reach the threshold. This situation should not happen because the players deleted their old shares. Additionally, an attacker cannot recover any information about the original secret from the update files because they contain only random information.

The dealer can change the threshold number while distributing updates, but must always remain vigilant of players keeping expired shares.

Verifiable secret sharing

A player might lie about his own share to gain access to other shares. A verifiable secret sharing (VSS) scheme allows players to be certain that no other players are lying about the contents of their shares, up to a reasonable probability of error. Such schemes cannot be computed conventionally; the players must collectively add and multiply numbers without any individual's knowing what exactly is being added and multiplied. Tal Rabin and Michael Ben-Or devised a multiparty computing (MPC) system that allows players to detect dishonesty on the part of the dealer or on part of up to one third of the threshold number of players, even if those players are coordinated by an "adaptive" attacker who can change strategies in realtime depending on what information has been revealed.

Limitations of schemes

Common to all unconditionally secure secret sharing schemes, there are limitations:

• Each share of the secret must be at least as large as the secret itself. This result is based in information theory, but can be understood intuitively. Given t-1 shares, no information whatsoever can be determined about the secret. Thus, the final share must contain as much information as the secret itself.
• All secret sharing schemes use random bits. To distribute a one-bit secret among threshold t people, t-1 random bits are necessary. The final share contains as much information as the secret, but the other t-1 shares still provide relevant information individually. This information cannot be the secret, so it must be random.

Uses and applications

A secret sharing scheme can secure a secret over multiple servers and remain recoverable despite multiple server failures. The dealer may treat himself as several distinct participants, distributing the shares between himself. Each share may be stored on a different server, but the dealer can recover the secret even if several servers break down as long as he can recover at least t shares; however, hackers that break into one server would still not know the secret as long as less than t shares are stored on each server.

A dealer could send t shares, all of which are necessary to recover the original secret, to a single recipient. An attacker would have to intercept all t shares to recover the secret, a task which may be more difficult than intercepting a single file.

Consider the following example. We will use the canonical example of secret information, the formula for Coke. If the Board of Directors of Coca-Cola decide they wish to protect the formula but still be able recover it in some circumstances (it's supposed to be in a big vault or safe, so whoever has the combination has access to it now), they might consider storing the formula in a computer. Assuming the computer is not prone to hardware or software failure (both big assumptions), the formula (or access to it, via the combination to the safe) must not be available to just anyone with an account. Furthermore, it might be that the Board doesn't want any single person to have access. The formula (or the combination to the safe containing it) can be stored in a file, but encrypted by (say) the one-time pad encryption algorithm, the only provably unbreakable cipher. So far so good, but who gets a copy of the key? An appropriate secret sharing scheme could protect access to the decrypted file (the formula/combination) by ensuring that, say, any five out of the seven directors could together get to the formula, but no group smaller than five could do so.

See also

• Byzantine fault tolerance
• Visual cryptography
• Tontine

References

• G. R. Blakley, "Safeguarding cryptographic keys", in proceedings of the National Computer Conference, 48, pp 313–317, 1979.
• Adi Shamir, "How to share a secret", Communications of the ACM, 22(1), pp612–613, 1979 [1] (http://www.cs.tau.ac.il/~bchor/Shamir.html).

External links

• ssss: A free (GPL) implementation of Shamir's Scheme (http://www.point-at-infinity.org/ssss/) with online demo (http://www.point-at-infinity.org/ssss/demo.html).
• Description of Shamir's and Blakley's schemes (http://www.rsasecurity.com/rsalabs/node.asp?id=2259)
• Patent for use of secret sharing for recovering PGP (and other?) pass phrases (http://www.pgp.com/company/pr/keyreconpatent.html) Template:US patent
• A bibliography on secret-sharing schemes (http://www.cacr.math.uwaterloo.ca/~dstinson/ssbib.html)