Tag Info

Shamir's secret sharing scheme is a threshold secret sharing scheme based on polynomial interpolation over a finite field.

A $(t,n)$-threshold secret sharing scheme is a method used to split a secret message into $k$ "shares" in such a way, that it can only be reconstructed if at least $t$ shares are combined. Combining any lesser number of shares reveals no information about the secret.

Shamir's secret sharing scheme accomplishes this by encoding the secret $s$ as an element of a finite field and choosing $t-1$ other random elements $c_i$ from the field. The shares are then generated by evaluating the polynomial $$f(x) = s + c_1 x + c_2 x^2 + \dotsb + c_{t-1} x^{t-1}$$ at $n$ different (non-zero) values of $x$. The shares are then pairs of the form $(x,y)$, where $y=f(x)$.

To reconstruct the secret, we can pick any $t$ shares $(x,y)$ and use Lagrange polynomial interpolation to construct the unique order $t-1$ polynomial $f$ passing through these points. The secret is then equal to the constant term of the polynomial (or, equivalently, to $f(0)$).

Shamir's secret sharing is unconditionally secure: it can be proven that, given less than $t$ shares, an attacker cannot recover any information about the secret even if they have access to unlimited computing power. Informally, this is because, for any set of $u < t$ shares, it's possible to choose the $t-u$ remaining share values in such a way as to yield any desired value for the reconstructed secret $s'$, and further, choosing the remaining share values at random produces each possible value of $s'$ with equal probability.

Compared to other secret sharing schemes such as Blakley's, Shamir's scheme is convenient in that the size of the shares does not depend on the number of participants $n$ or on the threshold $t$ (except that $n$ cannot exceed the number of elements in the field used). Where the secret message is too long to fit into a conveniently sized finite field, it can be split into smaller chunks and each chunk shared separately.

Convenient fields for Shamir's secret sharing include the binary Galois fields $GF(2^k)$, whose elements map one-to-one to $k$-bit bitstrings; for example, choosing $k=8$ allows each byte of the secret message to be shared separately, with each share containing only as many bytes as the message. Where the ability to generate more than 255 shares is desired, $k = 16$ or $k = 32$ may be used instead.