In cryptography, secret sharing is a technique to distribute trust among a group of participants. Shamir and Blakley independently invented it in 1979.
In a secret sharing scheme, there is one dealer and n players. The dealer has a secret which he must distribute to the players. He does 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. (Note that some call it an (n, t) threshold scheme.)
What secret sharing is not
A true secret sharing scheme distributes the secret in such a way that someone with fewer than t shares has no more information about the secret than someone with no shares. Consider a dealer who divides the word "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 268 = 208 billion possible combinations. A person with one share, however, would have to guess only six letters; he would face only 266 = 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 information about the content of the secret. Under a true scheme, a person with three shares would still face 268 = 208 billion combinations, while a person with four shares would face only one, i.e. he would know the password completely. A true secret sharing scheme is said to be information theoretically secure.
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 integer s. Give to each player i (except one) a random integer ri. Give to the last player the number (s - r1 - r2 - ... - rn-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 bi. Give to the last player the byte (s XOR b1 XOR b2 XOR ... XOR bi) where XOR is bitwise XOR. The secret is the bitwise XOR of the player's shares.
Shamir's scheme
Just as two points uniquely define a line, three points define a parabola, four define a cubic curve, etc. More generally, n coordinate pairs (xi, yi) uniquely define a polynomial of degree n-1. The dealer encodes the secret as the curve's y-intercept and gives each player the coordiantes 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 refreshed. 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 could only recover the secret from them 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.
It is also possible to change the threshold number while distributing updates, but the dealer must always be vigilant of players' keeping old shares even after they expire.
Verifiable secret sharing (VSS)
A player might lie about his own share to gain access to other shares. A verifiable secret sharing scheme (VSS) 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.
Problems common to all secret sharing schemes
- 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
The players need not necessarily be different people. The dealer may give himself several shares of a secret and store them on several servers such that an attacker cannot easily steal the entire secret, but the dealer may recover it even if several servers break down. A dealer could also 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 no longer wish to fully trust a slip of paper in a big safe, they might consider storing the formula in a computer. Assuming the computer is not prone to hardware or software failure (big assumptions both), we must ensure that the formula is not available to just anyone with an account on it. Further more it might be that the Board doesn't want any single person to have access. We could store the formula in a file, encrypted by (say) the one time pad encryption algorithm, the only provably unbreakable cypher. so far so good, but who gets a copy of the key? An appropriate secret sharing scheme could protect access to decrypted file (the formula) 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.