Secret sharing

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

Jump to: navigation, search
For when the whole secret is known by all participants, see shared secret.
Each secret share is a plane, and the secret is the point at which three shares intersect. Two shares yield only a line intersection.

In cryptography, secret sharing refers to any 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 fewer 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.

Contents

Motivation - A flawed secret sharing scheme

A secure secret sharing scheme distributes shares so that anyone with fewer than t shares has no extra information about the secret than someone with 0 shares. Consider the naive secret sharing scheme in which the secret phrase "password" is divided into the shares "pa------," "--ss----," "----wo--," and "------rd,". A person with 0 shares knows only that the password consists of eight letters. He would have to guess the password from 268 = 208 billion possible combinations. A person with one share, however, would have to guess only the six letters, from 266 = 308 million combinations. This system is not a secure secret sharing scheme, because a player with less than t shares gains significant information about the content of the secret. In a secure scheme, even a player missing only one share should still face 268 = 208 billion combinations.

Limitations of secret sharing schemes

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 2128 possible shares are generally considered enough to stymie any conceivable present-day adversary.

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.

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 ri. Give to the last player the number <math>(s - r_1 - r_2 - ... - r_{n-1})</math>. 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 players' shares.

When space efficiency is not a concern, these schemes can be used to reveal a secret to any desired subsets of the players simply by applying the scheme for each subset. For example, to reveal a secret s to any two of the three players Alice, Bob and Carol, create three different (2,2) secret shares for s, giving the three sets of two shares to Alice and Bob, Alice and Carol, and Bob and Carol. This approach quickly becomes impractical as the number of subsets increases, for example when revealing a secret to any 50 of 100 players, whereas the schemes described below allow secrets to efficiently be shared with a threshold of players.

A t ≠ n example

The difficulty lies in creating schemes that are still secure, but do not require all n shares. For example, imagine that the Board of Directors of Coca-Cola would like to protect Coke's secret formula. The president of the company should be able to access the formula when needed, but in an emergency any 3 of the 12 board members would be able to unlock the secret formula together. This can be accomplished by a secret sharing scheme with t = 3 and n = 15, where 3 shares are given to the president, and 1 is given to each board member.

Shamir's scheme

Shamir's Secret Sharing Template:Sect-stub

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. 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 n-dimensional hyperplanes) 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 (ie, 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.

One share Two shares intersecting on a line Three shares intersecting at a point
Blakley's scheme in three dimensions: each share is a 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 where both planes intersect.

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.

Proactive secret sharing

If the players store their shares on insecure computer servers, an attacker could crack 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

Main article: 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.

Other 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, crackers 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 is more difficult than intercepting a single file, especially if the shares are sent using different media (e.g. some over the Internet, some mailed on CD's).

For exceptionally large secrets, it may be more worthwhile to encrypt the secret and then distribute the key using secret sharing.

The ideas behind Secret Sharing Schemes were originally implemented against the "Silver Fish" attack. This was literally an attack on computer punch cards by Silver Fish. The problems created were similar to the problem of several servers breaking down.

See also

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].
  • Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Page 505.

External links


Template:Crypto navbox