Secret sharing
Secret sharing was invented independently by Adi Shamir[1] and George Blakley[2] in 1979.
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.
Secret sharing schemes address this problem, and allow arbitrarily high levels of confidentiality and reliability to be achieved.
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.
[citation needed] The security in such environments can be made greater by continuous changing[how?]
Common to all unconditionally secure secret sharing schemes, there are limitations:[citation needed] 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.
For example, to reveal a secret s to any two of the three players Alice, Bob and Carol, create three (
For example, imagine that the board of directors of a company would like to protect their secret formula.
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
This has led to the search for schemes that allow secrets to be shared efficiently with a threshold of 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.
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).
The Chinese remainder theorem 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 integers
, and the secret is recovered by essentially solving the system of congruences using the Chinese remainder theorem.
An attacker can only recover the secret if he can find enough other non-updated shares to reach the threshold.
The dealer can change the threshold number while distributing updates, but must always remain vigilant of players keeping expired shares.
Alternate techniques have been proposed for greatly increasing the efficiency of secret sharing schemes, by giving up the requirement of unconditional security.
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).
A related approach, known as AONT-RS,[6] 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.
In multi-secret sharing designed by Matthew K. Franklin and Moti Yung,[7] multiple points of the polynomial host secrets; the method was found useful in numerous applications from coding to multi-party computations.
[8] This scheme makes use of repeated polynomial interpolation and has potential applications in secure information dispersal on the Web and in sensor networks.
This method is based on data partitioning involving the roots of a polynomial in finite field.
[9] Some vulnerabilities of related space efficient secret sharing schemes were pointed out later.
[12] 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.
A dealer could send t shares, all of which are necessary to recover the original secret, to a single recipient.
Secret sharing is an important primitive in several protocols for secure multiparty computation.
