Shamir Secret Sharing
Shamir Secret Sharing (SSS) is one of the most popular implementations of a secret sharing scheme created by Adi Shamir, a famous Israeli cryptographer, who also contributed to the invention of RSA algorithm. SSS allows the secret to be divided into an arbitrary number of shares and allows an arbitrary threshold (as long as it is less than the total participants). SSS is based on the mathematical concept of polynomial interpolation which states that a polynomial of degree t-1 can be reconstructed from the knowledge of t or more points, known to be lying on the curve.
For instance, to reconstruct a curve of degree 1 (a straight line), we require at least 2 points that lie on the line. Conversely, it is mathematically infeasible to reconstruct a curve if the number of unique points available is less than (degree-of-curve + 1). One can imagine having infinite possible straight lines that could be formed as a result of just one point in 2D space.
Implementing Shamir’s Secret Sharing Scheme in Python
Secret Sharing schemes are used in the distribution of a secret value among multiple participants (shareholders) by dividing the secret into fragments (shares). This is done in a manner that prevents a single shareholder from having any useful knowledge of the original secret at all. The only way to retrieve the original secret is to combine the shares, distributed among the participants. Hence, the control of the secret is distributed. These schemes are examples of Threshold Cryptosystems, which involve the division of secrets among multiple parties such that several parties (more than some threshold number) must cooperate to reconstruct the secret.
Fig 1: Depiction of Secret Sharing between n participants
In general, a secret may be split into n shares (for n shareholders), out of which, a minimum of t, (t < n) shares are required for successful reconstruction. Such a scheme is referred to as a (t, n) sharing-scheme. From the n participants, any subset of shareholders, of size greater or equal to t, can regenerate the secret. Importantly, even with any k (k < t) shares, no new information about the original secret is learned.