Secret sharing (also called secret splitting) refers to methods for distributing a
secret
Secrecy is the practice of hiding information from certain individuals or groups who do not have the "need to know", perhaps while sharing it with other individuals. That which is kept hidden is known as the secret.
Secrecy is often controvers ...
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
Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identifi ...
and
George Blakley
George Robert (Bob) Blakley Jr. was an American cryptographer and a professor of mathematics at Texas A&M University, best known for inventing a secret sharing scheme in 1979 (see ).
Biography
Blakley did his undergraduate studies in physics at Ge ...
in 1979.
Importance
Secret sharing schemes are ideal for storing information that is highly sensitive and highly important. Examples include:
encryption key
A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key c ...
s,
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.
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
Cloud computing is the on-demand availability of computer system resources, especially data storage ( cloud storage) and computing power, without direct active management by the user. Large clouds often have functions distributed over mul ...
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
Wireless sensor networks (WSNs) refer to networks of spatially dispersed and dedicated sensors that monitor and record the physical conditions of the environment and forward the collected data to a central location. WSNs can measure environmental c ...
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 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. 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, ''P
i'' are public
asymmetric encryption
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic al ...
keys and ''Q
i'' 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 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 the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...
, 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
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
s. To distribute a one-bit secret among threshold ''t'' people, random bits are necessary. To distribute a secret of arbitrary length ''b'' bits, entropy of bits is necessary.
Trivial secret sharing
''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 an arbitrary length
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
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''
''n''−1) where ''XOR'' is
bitwise exclusive or. The secret is the bitwise XOR of all the players' numbers (''p'').
# Additionally, (1) can be performed using the linear operator in any
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
. For example, here's an alternative that is functionally equivalent to (1). Let's select 32-bit integers with well-defined overflow semantics (i.e. the correct answer is preserved, modulo 2
32). First, ''s'' can be divided into a vector of ''M'' 32-bit integers called ''v''
secret. Then players are each given a vector of ''M'' random integers, player ''i'' receiving ''v
i''. The remaining player is given ''v
n'' = (''v''
secret − ''v''
1 − ''v''
2 − ... − ''v''
''n''−1). The secret vector can then be recovered by summing across all the player's vectors.
1 < ''t'' < ''n'', and, more generally, any desired subset of
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.
When space efficiency is not a concern, trivial ''t'' = ''n'' 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.
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.
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
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
of degree 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 . 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
Plane(s) most often refers to:
* Aero- or airplane, a powered, fixed-wing aircraft
* Plane (geometry), a flat, 2-dimensional surface
Plane or planes may also refer to:
Biology
* Plane (tree) or ''Platanus'', wetland native plant
* ''Planes' ...
intersect at exactly one point. Three nonparallel planes in space intersect at exactly one point. More generally, any ''n'' nonparallel
-dimensional hyperplane
In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyper ...
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
-dimensional hyperplane
In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyper ...
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 security
A cryptosystem is considered to have information-theoretic security (also called unconditional security) if the system is secure against adversaries with unlimited computing resources and time. In contrast, a system which depends on the computatio ...
. 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.
Using the Chinese remainder theorem
The
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
can also be used in secret sharing, for it provides us with a method to uniquely determine a number ''S'' modulo ''k'' many
pairwise coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
integers
, given that
. There are two secret sharing schemes that make use of the
Chinese Remainder Theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
, 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 Theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
.
Proactive secret sharing
If the players store their shares on insecure computer servers, an
attacker
In some team sports, an attacker is a specific type of player, usually involved in aggressive play. Heavy attackers are, usually, placed up front: their goal is to score the most possible points for the team. In association football, attackers a ...
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
Tal Rabin (Hebrew: טל רבין, born 1962) is a computer scientist and Professor of Computer and Information Science at the University of Pennsylvania. She was previously the head of Research at the Algorand Foundation and the head of the cr ...
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.
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 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.
Multi-secret and space efficient (batched) secret sharing
An information-theoretically secure ''k''-of-''n'' secret-sharing scheme generates ''n'' shares, each of size at least that of the secret itself, leading to the total required storage being at least ''n''-fold larger than the secret. In multi-secret sharing designed by
Matthew K. Franklin and
Moti Yung
Mordechai M. "Moti" Yung is a cryptographer and computer scientist known for his work on cryptovirology and kleptography.
Career
Yung earned his PhD from Columbia University in 1988 under the supervision of Zvi Galil. In the past, he worked at th ...
, multiple points of the polynomial host secrets; the method was found useful in numerous applications from coding to multi-party computations. In space efficient secret sharing, devised by Abhishek Parakh and
Subhash Kak
Subhash Kak is an Indian-American computer scientist and historical revisionist. He is the Regents Professor of Computer Science Department at Oklahoma State University–Stillwater, an honorary visiting professor of engineering at Jawaharlal N ...
, each share is roughly the size of the secret divided by .
This scheme makes use of repeated polynomial interpolation and has potential applications in secure information dispersal on the Web and in
sensor networks
Wireless sensor networks (WSNs) refer to networks of spatially dispersed and dedicated sensors that monitor and record the physical conditions of the environment and forward the collected data to a central location. WSNs can measure environmental c ...
. This method is based on data partitioning involving the roots of a polynomial in finite field. Some vulnerabilities of related ''space efficient'' secret sharing schemes were pointed out later. They show that a scheme based on interpolation method cannot be used to implement a scheme when the ''k'' secrets to be distributed are inherently generated from a polynomial of degree less than , and the scheme does not work if all of the secrets to be shared are the same, etc.
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 act as several distinct participants, distributing the shares among the participants. 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 they can recover at least ''t'' shares; however,
crackers that break into one server would still not know the secret as long as fewer than ''t'' shares are stored on each server.
This is one of the major concepts behind the
Vanish computer project at the
University of Washington
The University of Washington (UW, simply Washington, or informally U-Dub) is a public research university in Seattle, Washington.
Founded in 1861, Washington is one of the oldest universities on the West Coast; it was established in Seattle a ...
, where a random key is used to encrypt data, and the key is distributed as a secret across several nodes in a
P2P
P2P may refer to:
* Pay to play, where money is exchanged for services
* Peer-to-peer, a distributed application architecture in computing or networking
** List of P2P protocols
* Phenylacetone, an organic compound commonly known as P2P
* Poin ...
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 attack
Sibyls were oracular women believed to possess prophetic powers in ancient Greece.
Sybil or Sibyl may also refer to:
Films
* ''Sybil'' (1921 film)
* ''Sybil'' (1976 film), a film starring Sally Field
* ''Sybil'' (2007 film), a remake of the 19 ...
, thus making Vanish insecure.
Any shareholder who ever has enough information to decrypt the content at any point is able to take and store a copy of X. Consequently, although tools and techniques such as Vanish can make data irrecoverable within their own system after a time, it is not possible to force the deletion of data once a malicious user has seen it. This is one of the leading conundrums of
Digital Rights Management
Digital rights management (DRM) is the management of legal access to digital content. Various tools or technological protection measures (TPM) such as access control technologies can restrict the use of proprietary hardware and copyrighted works. ...
.
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
The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...
, some mailed on
CDs).
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 computation
Secure multi-party computation (also known as secure computation, multi-party computation (MPC) or privacy-preserving computation) is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their ...
.
Secret sharing can also be used for user authentication in a system.
[Gupta, Kishor Datta, et al. "Shamir's Secret Sharing for Authentication without Reconstructing Password." 2020 10th Annual Computing and Communication Workshop and Conference (CCWC). IEEE, 2020.]
See also
References
External links
Ubuntu Manpage: gfshare – explanation of Shamir Secret Sharing in GF(28)Description of Shamir's and Blakley's schemes* Patent for use of secret sharing for recovering PGP (and other?) pass phrases
*
*
{{Cryptography navbox
Cryptography