Secret sharing
Each cret share is a plane, and the cret is the point at which three shares interct. Two shares yield only a
line interction.
Secret sharing (also called cret splitting ) refers to method for
distributing a cret amongst a group of participants, each of
whom is allocated a share of the cret. The cret can be
reconstructed only when a sufficient number, of possibly different
types, of shares are combined together; individual shares are of no
u on their own.
In one type of cret sharing scheme there is one dealer and n
players . The dealer gives a share of the cret to the players, but
only when specific conditions are fulfilled will the players be able
to reconstruct the cret 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 cret 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 independently by Adi Shamir and
George Blakley in 1979.Importance of Secret Sharing Schemes
Secret sharing schemes are ideal for storing information that is highly nsitive and highly important. Examples include: encryption keys, missile launch codes, and numbered bank accounts. Each of the 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 si
multaneously achieving high levels of confidentiality and reliability. This is becau when storing the encryption key, one must choo between keeping a single copy of the key in one location for maximum crecy, 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.
An example cret sharing scheme
A cure cret sharing scheme distributes shares so that anyone with fewer than t shares has no extra information about the cret than someone with 0 shares. Consider the naive cret sharing scheme in which the cret phra "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, and so on as more persons collude. This system is not a cure cret sharing scheme, becau a player with fewer than t shares gains some information about the content of the cret. In a cure s
cheme, even a player missing only one share should still face 268 = 208 billion combinations. Arbitrary strength can be maintained even with this "naive" cret sharing scheme with sufficiently chon fragment (and cret) length.
Limitations of cret sharing schemes
Several cret sharing schemes are said to be information theoretically cure and can be proved to be so, while others give up this unconditional curity for improved efficiency while maintaining enough curity to be considered as cure as other common cryptographic primitives. For example, they might allow crets to be protected by shares with 128-bits of entropy each, since each share would be considered enough to stymie any conceivable prent-day adversary, requiring a brute force attack of average size 2127.
Common to all unconditionally cure cret sharing schemes, there are limitations:
•Each share of the cret must be at least as large as the cret itlf. This result is bad in information theory, but can be understood intuitively. Given t-1 shares, no information whatsoever can be determined about the cret.
Thus, the final share must contain as much information as the cret itlf.
•All cret sharing schemes u random bits. To distribute a one-bit cret among threshold t people, t-1 random bits are necessary. To distribute a cret of arbitrary length entropy of (t-1)*length is necessary.
Trivial cret sharing
There are veral (t, n) cret sharing schemes for t = n, when all shares are necessary to recover the cret:•Encode the cret as an integer s. Give to each player i (except one) a random integer r
i
. Give to the last player the number . The cret is the sum of the players' shares.
•Encode the cret as an arbitrary length binary number s. Give to each player i (except one) a random number p
i
with the same length as s. Give to the last player the result of (s XOR p
1 XOR p
2
XOR ... XOR p
i
) where XOR is
bitwi exclusive or. The cret is the bitwi XOR of all the players' numbers (p).
When space efficiency is not a concern, the schemes can be ud to reveal a cret to any desired subts of the players simply by applying the scheme for each subt. For example, to reveal a cret s to any two of the three players Alice, Bob and Carol, create three different (2,2) cret shares for s, giving the three ts of two shares to Alice and Bob, Alice and Carol, and Bob and Carol. This approach quickly becomes impractical as the number of subts increas, for example when revealing a cret to any 50 of 100 players, whereas the schemes described below allow crets to efficiently be shared with a threshold of players.
A t ≠ n example
The difficulty lies in creating schemes that are still cure, but do not require all n shares. For example, imagine that the Board of Directors of a company would like to protect their cret 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 cret formula together. This can be accomplished by a cret 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 ud to recover the cret. The system relies on the idea that you can fit a unique polynomial of degree (t-1) to any t 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 cret 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 cret.
Blakley's scheme
Two nonparallel lines in the same plane interct at exactly one point. Three "nonparallel" planes in space interct at exactly one point. More generally, any n nonparallel (n-1)-dimensional hyperplanes interct at a specific point. The cret may be encoded as any single coordinate of the point of interction. If the cret is encoded using all the coordinates, even if they are random, then an insider (someone in posssion of one or more of the (n-1)-dimensional hyperplanes) gains information about the cret since he knows it must lie on his plane. If an insider can gain any more knowledge about the cret than an outsider can, then the system no longer has information theoretic curity. If only one of the n coordinates is ud, then the insider knows no more than an outsider (i.e., that the cret must lie on the x-axis for a 2-dimensional system). Each player is given enough information to define a hyperplane; the cret is recovered by calculating the planes' point of interction and then taking a specified coordinate of that interction.
Blakley's scheme in three dimensions: each share is a plane, and the cret is the point at which thr
ee shares interct. Two shares are insufficient to determine the cret, although they do provide enough information to narrow it down to the line where both planes interct.
Blakley's scheme is less space-efficient than Shamir's; while Shamir's shares are each only as large as the original cret, 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.
Using the Chine Remainder Theorem
The Chine Remainder Theorem can also be ud in cret 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 cret sharing schemes that make u of the Chine Remainder Theorem, Mignotte's and Asmuth-Bloom's Schemes. They are threshold cret sharing schemes, in which the shares are generated by reduction modulo the integers , and the cret is recovered by esntially solving the system of congruences using the Chine
Remainder Theorem.
Proactive cret sharing
If the players store their shares on incure computer rvers, an attacker could crack in and steal the shares. If it is not practical to change the cret, the uncompromid (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 cret.
All of the non-updated shares the attacker accumulated become uless. An attacker can only recover the cret if he can find enough other non-updated shares to reach the threshold. This situation should not happen becau the players deleted their old shares. Additionally, an attacker cannot recover any information about the original cret from the update files becau 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 cret sharing
A player might lie about his own share to gain access to other shares. A verifiable cret 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 devid 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 tho players are coordinated by an "adaptive" attacker who can change strategies in realtime depending on what information has been revealed.
Computationally cure cret sharing
The disadvantage of unconditionally cure cret 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 cret times the number of shares. If the size of the cret 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 propod for greatly increasing the efficiency of cret sharing schemes, by giving up the requirement of unconditional curity.
One of the techniques, known as cret sharing made short,[1] combines Rabin's information dispersal algorithm[2] (IDA) with Shamir's cret 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 cret sharing schemes, but unlike cret 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 ca, this scheme is 10 times more efficient than if Shamir's scheme had been applied directly on the data. The final step in cret sharing made short is to u Shamir cret 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,[3] applies an All-or-nothing transform 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 us and applications
A cret sharing scheme can cure a cret over multiple rvers and remain recoverable despite multiple rver failures. The dealer may treat himlf as veral distinct participants, distributing the shares between himlf. Each share may be stored on a different rver, but the dealer can recover the cret even if veral rvers break down as long as he can recover at least t shares; however, crackers that break into one rver would still not know the cret as long as fewer than t shares are stored on each rver.
This is one of the major concepts behind the Vanish computer project at the University of Washington, where a random key is ud to encrypt data, and the key is distributed as a cret across veral nodes in a P2P 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 cret-sharing nodes on the network will decrea naturally over time, therefore causing the cret to eventually vanish. However, the network is vulnerable to a Sybil attack, thus making Vanish incure.[4]
A dealer could nd t shares, all of which are necessary to recover the original cret, to a single recipient. An attacker would have to intercept all t shares to recover the cret, a task which is more difficult than intercepting a single file, especially if the shares are nt using different media (e.g. so
me over the Internet, some mailed on CDs). For large crets, it may be more efficient to encrypt the cret and then distribute the key using cret sharing. Secret sharing is an important primitive in veral protocols for cure multiparty computation.
Notes
[1]Krawczyk, Hugo (1993). "Secret Sharing Made Short" (ll.edu/cours/cs754/2001fa/cretshort.pdf). CRYPTO '93.
.
[2]Rabin, Michael O. (1989). "Efficient dispersal of information for curity, load balancing, and fault tolerance". Journal of the ACM36 (2).
[3]Resch, Jason; Plank, James (February 15, 2011). "AONT-RS: Blending Security and Performance in Disperd Storage Systems" (
[4]"'Unvanish: Reconstructing Self-Destructing Data'" (z.cs.utexas.edu/urs/osa/unvanish/home). .
References
•Blakley, G. R. (1979). "Safeguarding cryptographic keys". Proceedings of the National Computer Conference48: 313–317.
•Shamir, Adi (1979). "How to share a cret" (www.cs.tau.ac.il/~bchor/Shamir.html). Communications of the ACM22 (11): 612–613. doi:10.1145/359168.359176.
•Knuth, Donald (1997). Seminumerical Algorithms. The Art of Computer Programming. 2 (3 ed.).
Addison-Wesley. p. 505. ISBN 0-201-89684-2. OCLC 174593116.
External links
•ssss: A free (GPL) implementation of Shamir's Scheme (/ssss/) with online demo (/ssss/demo.html).
•libgfshare (/software/libgfshare) is a free implementation (C library and commandline tools) of Shamir's scheme in GF(256).
•Description of Shamir's and Blakley's schemes (/rsalabs/node.asp?id=2259)•Patent for u of cret sharing for recovering PGP (and other?) pass phras U.S. Patent 6,662,299 (www.
• A bibliography on cret-sharing schemes (www.cacr.math.uwaterloo.ca/~dstinson/ssbib.html)
•Code signing systems using Shared Secret (/web/20080214135432/www.
•Christophe David's web bad implementation of Shamir's scheme 'How to share a Secret' (www.
• A simple cret sharing implementation using XOR in Python (/2011/03/ cret-sharing-simple-implementation.html)
•Software products from IBM (publib./infocenter/dmndhelp/v6rxmx/index.
jsp?topic=/com.ibm.websphere.nd.doc/info/ae/ae/trun_ha_newpolicy.html), Sun (/
source/816-5547-10/index.html), and Netscape (/source/816-5531-10/kycrt_ee.htm),
and hardware products from Safenet (/products/pki/lunaCA3.asp) u cret
sharing. There are libraries for cret sharing in veral programming languages.
•SecretSharing (/projects/cretsharing/) A QT implementation of Shamir's scheme using GF(2^8) field arithmetic.
