How to Share a SecretHow to Share a SecretShamir, Adi1979

Paper summaryjoecohenThis paper defines a scheme to share a secret message with a complete group of people. It requires the group of $k$ people, no less, to combine their secret keys in order to obtain the shared secret. The secret shared is contained in the $a_0, .. a_{k-1}$ coefficients of a polynomial:
$$f(x)=a_0+a_1x+a_2x^2+\cdots+a_{k-1}x^{k-1}$$
There is a property of defining polynomials such that 2 points are sufficient to define a line, 3 points are sufficient to define a parabola, 4 points to define a cubic curve, etc. It takes $k$ points to define a polynomial of degree $k-1$
You can then give out $k$ pairs of input $x$ and output $f(x)$ examples. Given $k$ unique examples of an input $x$ and an output $f(x)$ you can determine what the coefficients were. But only having $k-1$ examples leaves a free variable and without added information it is impossible to know the coefficients. This means all $k$ people must provide their examples in order to determine the secret!

This paper defines a scheme to share a secret message with a complete group of people. It requires the group of $k$ people, no less, to combine their secret keys in order to obtain the shared secret. The secret shared is contained in the $a_0, .. a_{k-1}$ coefficients of a polynomial:
$$f(x)=a_0+a_1x+a_2x^2+\cdots+a_{k-1}x^{k-1}$$
There is a property of defining polynomials such that 2 points are sufficient to define a line, 3 points are sufficient to define a parabola, 4 points to define a cubic curve, etc. It takes $k$ points to define a polynomial of degree $k-1$
You can then give out $k$ pairs of input $x$ and output $f(x)$ examples. Given $k$ unique examples of an input $x$ and an output $f(x)$ you can determine what the coefficients were. But only having $k-1$ examples leaves a free variable and without added information it is impossible to know the coefficients. This means all $k$ people must provide their examples in order to determine the secret!