Secret sharing (also called secret splitting) refers to methods for distributing a secret among a group, in such a way that no individual holds any intelligible information about the secret, but when a sufficient number of individuals combine their 'shares', the secret may be reconstructed. Whereas insecure secret sharing allows an attacker to gain more information with each share, secure secret sharing is 'all or nothing' (where 'all' means the necessary number of shares).
In one type of secret sharing scheme there is one dealer and n players. The dealer gives a share of the secret to the players, but only when specific conditions are fulfilled will the players be able to reconstruct the secret from their shares. 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 -threshold scheme (sometimes it is written as an -threshold scheme).
Secret sharing was invented independently by Adi Shamir and George Blakley in 1979.
Importance
Secret sharing schemes are ideal for storing information that is highly sensitive and highly important. Examples include: encryption keys, missile launch codes, and numbered bank accounts. Each of these pieces of information must be kept highly confidential, as their exposure could be disastrous; however, it is also critical that they should not be lost. Traditional methods for encryption are ill-suited for simultaneously achieving high levels of confidentiality and reliability. This is because when storing the encryption key, one must choose between keeping a single copy of the key in one location for maximum secrecy, or keeping multiple copies of the key in different locations for greater reliability. Increasing reliability of the key by storing multiple copies lowers confidentiality by creating additional attack vectors; there are more opportunities for a copy to fall into the wrong hands. Secret sharing schemes address this problem, and allow arbitrarily high levels of confidentiality and reliability to be achieved. (also available at )
Secret sharing also allows the distributor of the secret to trust a group 'in aggregate'. Traditionally, giving a secret to a group for safekeeping would require that the distributor completely trust all members of the group. Secret sharing schemes allow the distributor to securely store the secret with the group even if not all members can be trusted all the time. So long as the number of traitors is never more than the critical number needed to reconstruct the secret, the secret is safe.
Secret sharing schemes are important in cloud computing environments. Thus a key can be distributed over many servers by a threshold secret sharing mechanism. The key is then reconstructed when needed.
Secret sharing has also been suggested for sensor networks where the links are liable to be tapped, by sending the data in shares which makes the task of the eavesdropper harder. The security in such environments can be made greater by continuous changing of the way the shares are constructed.
"Secure" versus "insecure" secret sharing A secure secret sharing scheme distributes shares so that anyone with fewer than t shares has no more information about the secret than someone with 0 shares.
Consider for example the 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, and thus 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, and so on as more persons collude. Consequently, this system is not a "secure" secret sharing scheme, because a player with fewer than t secret shares is able to reduce the problem of obtaining the inner secret without first needing to obtain all of the necessary shares.
In contrast, consider the secret sharing scheme where X is the secret to be shared, Pi are public asymmetric encryption keys and Qi their corresponding private keys. Each player J is provided with In this scheme, any player with private key 1 can remove the outer layer of encryption, a player with keys 1 and 2 can remove the first and second layer, and so on. A player with fewer than N keys can never fully reach the secret X without first needing to decrypt a public-key-encrypted blob for which he does not have the corresponding private key – a problem that is currently believed to be computationally infeasible. Additionally we can see that any user with all N private keys is able to decrypt all of the outer layers to obtain X, the secret, and consequently this system is a secure secret distribution system.
Limitations Several secret-sharing schemes are said to be information-theoretically secure and can be proven 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 secrets to be protected by shares with entropy of 128 bits each, since each share would be considered enough to stymie any conceivable present-day adversary, requiring a brute force attack of average size 2127.
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 shares, no information whatsoever can be determined about the secret. Thus, the final share must contain as much information as the secret itself. There is sometimes a workaround for this limitation by first compressing the secret before sharing it, but this is often not possible because many secrets (keys for example) look like high-quality random data and thus are hard to compress. All secret-sharing schemes use random bits for constructing the shares. Otherwise, with a deterministic scheme, a player could deduce information about the secret by brute-forcing all possible secrets and running the deterministic scheme. To distribute a one-bit secret shares with a threshold of t shares, random bits are needed. To distribute a secret of b bits, entropy of bits is necessary.
Trivial secret sharing Note: n is the total number of 'players', among whom the shares are distributed, and t is the minimum number of players required to reveal the secret.
t = 1 t = 1 secret sharing is trivial. The secret can simply be distributed to all n participants.
t = n There are several secret-sharing schemes for , when all shares are necessary to recover the secret:
Encode the secret as a binary number s of any length. For each player i, where i is one fewer than the total number of players, give a random binary number pi of the same length as s. To the player without a share, give the share calculated as , where ⊕ denotes bitwise exclusive or. The secret is the bitwise exclusive-or of all the players' numbers (pi, for 1 ≤ i ≤ n). Instead, (1) can be performed using the binary operation in any group. For example, take the cyclic group of integers with addition modulo 232, which corresponds to 32-bit integers with addition defined with the binary overflow being discarded. The secret s can be partitioned into a vector of M 32-bit integers, which we call vsecret. Then of the players are each given a vector of M 32-bit integers that is drawn independently from a uniform probability distribution, with player i receiving vi. The remaining player is given vn = vsecret − v1 − v2 − ... − vn−1. The secret vector can then be recovered by summing across all the players' vectors.
1 < t < n The difficulty lies in creating schemes that are still secure, but do not require all n shares.
When space efficiency is not a concern, trivial 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 secret shares for s, giving the three sets of two shares to Alice and Bob, Alice and Carol, and Bob and Carol.
t belonging to any desired subset of {1, 2, ..., n} For example, imagine that the board of directors of a company would like to protect their 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. One of the ways this can be accomplished is by a secret-sharing scheme with and , where 3 shares are given to the president, and one share is given to each board member.
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 schemes to be created and each player to maintain 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.
Ramp schemes A ramp secret sharing scheme is a secret-sharing scheme with two thresholds: groups below the lower threshold learn no information about the secret, groups at or above the upper threshold can reconstruct it, and intermediate-size groups may obtain partial information. This relaxation can reduce the size of shares. Hirosuke Yamamoto's threshold scheme is an early information-theoretic formulation of this trade-off.
Shamir's scheme
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 , 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 . The method is to create a polynomial of degree 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 th degree polynomial to them, the first coefficient being the secret.
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 nonparallel -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 -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 (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.