How to Share a Secret: Summary of Shamir's Paper

In his 1979 paper, Adi Shamir explains an ingenious way to share a secret between n people, such that only if k of them cooperate will the secret be revealed. And that even if k-1 people cooperated, nothing would be revealed.

How it works is simple. For a polynomial of degree 1 (i.e, $f(x)=a_{1}x+a_{0}$), how many (x,y) points do you need to find $a_{1}$ and $a_{0}$? Two. If you had only one point, you could find a relationship between $a_{0}$ and $a_{1}$ but that would be all. For a polynomial of degree 2 (i.e, $f(x)=a_{2}x^2+a_{1}x+a_{0}$), how many (x,y) points do you need to find $a_{2}, a_{1}$ and $a_{0}$? Three. If you had only two points, there would still be an infinite pairs of $a_{2}$, $a_{1}$ and $a_{0}$.

Knowing what we know about polynomials, suppose n people need to be able to be part of our trusted group, such that if k of them cooperated, they could work out the secret.

We set $a_{0}$ as our secret. We generate a polynomial of degree k-1 so there are k coefficients and at least k points or cooperating members are needed. Except for $a_{0}$ which is our secret, we generate the coefficients ($a_{1}$ to $a_{n}$) randomly. Then we index our n members give them each the f(x) of their index, so member one gets f(1), member two gets f(2) and so on up to member n who gets f(n). Now if any k members cooperate, they'll have the numbers to find out all the coefficients, and work out $a_{0}$. Easy as that. We will also use modulo arithmetic for our polynomial equations so every number is equally likely in it.