Secret sharing refers to method for distributing a
secretSecrecy is the practice of hiding information from certain individuals or groups, perhaps while sharing it with other individuals...
amongst a group of participants, each of whom is allocated a
share of the secret. The secret can be reconstructed only when a sufficient number of 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 ShamirAdi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
and
George BlakleyGeorge Robert Blakley Jr. is an American cryptographer and a professor of mathematics at Texas A&M University, best known for inventing a secret sharing scheme in 1979.-Biography:...
, independent of each other, in 1979.
Importance of Secret Sharing Schemes
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 accountA numbered bank account is a type of bank account where the name of the account holder is kept secret, and he identifies himself to the bank by means of a code word known only by the account holder and a restricted number of bank employees, thus providing the holder with a degree of bank privacy in...
s. Each of these pieces of information must be kept highly confidential, as their exposure could be disastrous, however, it is also critical that they 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.
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 26
8 = 208 billion possible combinations. A person with one share, however, would have to guess only the six letters, from 26
6 = 308 million combinations, and so on as more persons collude. This system is not a secure secret sharing scheme, because a player with fewer 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 26
8 = 208 billion combinations.
Limitations of secret sharing schemes
Several secret sharing schemes are said to be
information theoretically secureA cryptosystem is information-theoretically secure if its security derives purely from information theory. That is, it is secure even when the adversary has unlimited computing power. The adversary simply does not have enough information to break the security...
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 secrets to be protected by shares with 128-bits of entropy each, since each share would be considered enough to stymie any conceivable present-day adversary, requiring a brute force attack of average size 2
127.
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
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
, 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 bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s. To distribute a one-bit secret among threshold t people, t-1 random bits are necessary. To distribute a secret of arbitrary length entropy of (t-1)*length is necessary.
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
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s. Give to each player i (except one) a randomRandomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
integer ri. Give to the last player the number 
. The secret is the sum of the players' shares.
- Encode the secret as an arbitrary length binary
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
number s. Give to each player i (except one) a random number pi with the same length as s. Give to the last player the result of (s XOR p1 XOR p2 XOR ... XOR pi) where XOR is bitwise exclusive or. The secret is the bitwise XOR of all the players' numbers (p).
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 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. 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
In this scheme, any
t out of
n shares may be used to recover the secret. The system relies on the idea that you can fit a unique polynomial of degree
(t-1) to any set of
t points that lie 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
t-1. The method is to create a polynomial of degree
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
(t-1)th degree polynomial to them, the first coefficient being the secret.
Blakley's scheme
Two
nonparallelParallelism is a term in geometry and in everyday life that refers to a property in Euclidean space of two or more lines or planes, or a combination of these. The assumed existence and properties of parallel lines are the basis of Euclid's parallel postulate. Two lines in a plane that do not...
lines in the same
planeIn mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...
intersect at exactly one point. Three "nonparallel" planes in space intersect at exactly one point. More generally, any
n nonparallel
n-dimensionalIn physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
hyperplaneA hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions.A hyperplane of an n-dimensional space is a flat subset with dimension n − 1...
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
n-dimensionalIn physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
hyperplaneA hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions.A hyperplane of an n-dimensional space is a flat subset with dimension n − 1...
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 securityA cryptosystem is information-theoretically secure if its security derives purely from information theory. That is, it is secure even when the adversary has unlimited computing power. The adversary simply does not have enough information to break the 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.
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.
Secret Sharing using the Chinese Remainder Theorem
The
Chinese Remainder TheoremThe Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
can also be used in secret sharing, for it provides us with a method to uniquely determine a number
S modulo
k many relatively prime integers
, given that
. There are two secret sharing schemes that make use of the
Chinese Remainder TheoremThe Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
, Mignotte's and Asmuth-Bloom's Schemes. They are threshold secret sharing schemes, in which the shares are generated by reduction modulo the integers
, and the secret is recovered by essentially solving the system of congruences using the
Chinese Remainder TheoremThe Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
.
Proactive secret sharing
If the players store their shares on insecure computer servers, an
attackerIn some sports, an attacker is a specific type of player, usually one whose role involves aggressive play. Heavy attackers are usually placed up front so they can score some points for the team.In football, attackers are also referred to as strikers....
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
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 computingSecure multi-party computation is a sub field of cryptography. The goal of methods for secure multi-party computation is to enable parties to jointly compute a function over their inputs, while at the same time keeping these inputs private...
(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.
Computationally Secure Secret Sharing
The disadvantage of unconditionally secure secret sharing schemes is that the storage and transmission of the shares requires an amount of storage and bandwidth resources equivalent to the size of the secret times the number of shares. If the size of the secret were significant, say 1 GB, and the number of shares were 10, then 10 GB of data must be stored by the shareholders. Alternate techniques have been proposed for greatly increasing the efficiency of secret sharing schemes, by giving up the requirement of unconditional security.
One of these techniques, known as
secret sharing made short, combines Rabin's information dispersal algorithm (IDA) with Shamir's secret sharing. Data is first encrypted with a randomly generated key, using a symmetric encryption algorithm. Next this data is split into N pieces using Rabin's IDA. This IDA is configured with a threshold, in a manner similar to secret sharing schemes, but unlike secret sharing schemes the size of the resulting data grows by a factor of (number of fragments / threshold). For example, if the threshold were 10, and the number of IDA-produced fragments were 15, the total size of all the fragments would be (15/10) or 1.5 times the size of the original input. In this case, this scheme is 10 times more efficient than if Shamir's scheme had been applied directly on the data. The final step in secret sharing made short is to use Shamir secret sharing to produce shares of the randomly generated symmetric key (which is typically on the order of 16 - 32 bytes) and then give one share and one fragment to each shareholder.
A related approach, known as AONT-RS, applies an
All-or-nothing transformIn cryptography, an all-or-nothing transform , also known as an all-or-nothing protocol, is an encryption mode which allows the data to be understood only if all of it is known. AONTs are not encryption, but frequently make use of symmetric ciphers and may be applied before encryption...
to the data as a pre-processing step to an IDA. The All-or-nothing transform guarantees that any number of shares less than the threshold is insufficient to decrypt the data.
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.
This is one of the major concepts behind the
VanishVanish is a project at the University of Washington which endeavors to "give users control over the lifetime of personal data stored on the web." The project proposes to allow a user to enter information that he or she will send out across the internet, thereby relinquishing control of it...
computer project at the
University of WashingtonUniversity of Washington is a public research university, founded in 1861 in Seattle, Washington, United States. The UW is the largest university in the Northwest and the oldest public university on the West Coast. The university has three campuses, with its largest campus in the University...
, where a random key is used to encrypt data, and the key is distributed as a secret across several nodes in a
P2PPeer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
network. In order to decrypt the message, at least
t nodes on the network must be accessible; the principle for this particular project being that the number of secret-sharing nodes on the network will decrease naturally over time, therefore causing the secret to eventually
vanish. However, the network is vulnerable to a
Sybil attackThe Sybil attack in computer security is an attack wherein a reputation system is subverted by forging identities in peer-to-peer networks. It is named after the subject of the book Sybil, a fictional case study of a woman with multiple personality disorder...
, thus making Vanish insecure.
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
InternetThe Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
, some mailed on
CDThe Compact Disc is an optical disc used to store digital data. It was originally developed to store and playback sound recordings exclusively, but later expanded to encompass data storage , write-once audio and data storage , rewritable media , Video Compact Discs , Super Video Compact Discs ,...
s).
For large secrets, it may be more efficient to encrypt the secret and then distribute the key using secret sharing.
Secret sharing is an important primitive in several protocols for
secure multiparty computationSecure multi-party computation is a sub field of cryptography. The goal of methods for secure multi-party computation is to enable parties to jointly compute a function over their inputs, while at the same time keeping these inputs private...
.
See also
- Shamir's Secret Sharing
Shamir's Secret Sharing is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret....
- Homomorphic secret sharing
In cryptography, homomorphic secret sharing is a type of secret sharing algorithm in which the secret is encrypted via homomorphic encryption. A homomorphism is a transformation from one type of algebraic structure into another so that the structure is preserved...
- A simplistic decentralized voting protocol.
- Byzantine fault tolerance
Byzantine fault tolerance is a sub-field of fault tolerance research inspired by the Byzantine Generals' Problem, which is a generalized version of the Two Generals' Problem....
- Access structure
Access structures are used in the study of security system where multiple parties need to work together to obtain a resource. Groups of parties that are granted access are called qualified. In set theoretic terms they are referred to as qualified sets. In turn, the set of all such qualified sets is...
- Secure multiparty computation
Secure multi-party computation is a sub field of cryptography. The goal of methods for secure multi-party computation is to enable parties to jointly compute a function over their inputs, while at the same time keeping these inputs private...
- Visual cryptography
Visual cryptography is a cryptographic technique which allows visual information to be encrypted in such a way that the decryption can be performed by the human visual system, without the aid of computers....
- Tontine
A tontine is an investment scheme for raising capital, devised in the 17th century and relatively widespread in the 18th and 19th. It combines features of a group annuity and a lottery. Each subscriber pays an agreed sum into the fund, and thereafter receives an annuity. As members die, their...
- Secret sharing using the Chinese remainder theorem
- Network coding
Network coding is a technique where, instead of simply relaying the packets of information they receive, the nodes of a network will take several packets and combine them together for transmission. This can be used to attain the maximum possible information flow in a network...
External links