Technology attributes
Other attributes
Shamir's Secret Sharing (SSS) is an algorithm in cryptography that allows for information to be broken into separate parts, or shares, and reconstructed using a fraction of the total shares. The algorithm was proposed in 1979 by Israeli cryptographer Adi Shamir, who also co-invented the Rivest–Shamir–Adleman (RSA) algorithm. SSS is a key distribution algorithm that divides a secret, such as a crypto key, into separate parts called shares, which can be distributed to a group of people. The shares can be brought together to reconstruct the secret. However, using SSS, the secret can be reconstructed using a number less than the total number of shares; this number is called the threshold.
SSS introduces a threshold scheme overcoming issues decrypting sensitive information, should people holding shares be unavailable. Additionally, as the threshold needs to be met in order to reconstruct the secret, SSS helps secure against an adversary even if they have unlimited computational power. In cryptography, this is known as information theoretically secure. Another benefit of SSS is that it is flexible and extensible, meaning it is possible to add, remove, or amend shares at any time without modifying the original secret.
The method for secret sharing behind SSS relies on polynomial interpolation, an algebraic method of estimating unknown values in a gap between two known data points without requiring knowledge outside of those data points. The idea behind SSS's threshold scheme is that 2 points are sufficient to define a line, 3 points are sufficient to define a parabola, 4 points to define a cubic curve, and so on. SSS encodes the original information or secret into a polynomial and then splits it into pieces that are distributed among multiple holders. SSS uses polynomial interpolation to allow the efficient reconstruction of the secret without needing every piece or share, only a specific threshold of shares. As long as the threshold is met, it is possible to reconstruct the polynomial, correctly estimating the values of the missing information.
SSS makes it possible for multiple parties who do not know each other to store private information. This could be for storing user secrets, such as personal information or private cryptographic keys, across a distributed network. When SSS is combined with other cryptographic techniques, such as multiparty computation and zero-knowledge cryptography, it can provide an additional layer of security, improving the security of data sharing and storage and making it resilient to accidental data loss and external attacks.
Israeli cryptographer Adi Shamir, who had previously co-invented the RSA algorithm, introduced SSS in a November 1979 paper titled How to share a secret. Published in Communications of the ACM, Volume 22, Issue 11, the paper's abstract includes:
In this paper we show how to divide data D into n pieces in such a way that D is easily reconstructable from any k pieces, but even complete knowledge of k - 1 pieces reveals absolutely no information about D. This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.
The aim of the SSS algorithm is to divide the original data (D) into a number of pieces (n), D1, D2, ... Dn, such that:
- Knowledge of the threshold (k) or more pieces makes D easy to compute
- Knowledge of fewer pieces than the threshold (<k) leaves D undetermined. Put another way, all possible values for D are equally likely.
The SSS scheme is called a (k,n) threshold. If k=n, then the threshold is equal to the total number of shares, and the algorithm is redundant.
SSS uses the fact that for k points, it is possible to find a polynomial equation with degree (k-1). For example, with two points (x1, y1) and (x2, y1), it is possible to find a linear polynomial: y = ax + b. Similarly, with three points, it is possible to find a quadratic polynomial: y = ax2 + bx + c.
Therefore, SSS builds a polynomial with degree (k-1) such that the constant term is the original encoded secret and the remaining numbers are random. The constant term needs to be discoverable using k out of the total n points from this polynomial using Lagrange's basis polynomial.
For example, using the (k,n) threshold to share a secret S that is assumed to an element in a finite field F. Choose at random k-1 coefficients (a1, ... , ak-1) in F and let a0 = S. Build the polynomial function:
Calculate n points from the polynomial function and assign them to the chosen participants, such that they receive the input and the output of the function. With any subset k of these pairs, it is possible to determine the coefficients of the polynomial function and, therefore, the original secret S, which is equal to the constant coefficient a0.
The reconstruction of the polynomial utilizes the Lagrange basis polynomial. The main concept behind this is to form Lagrange's identities first, and the summation of these identities gives us the required function to find from the given points.