Secret Sharing

Secret Sharing is used to split a secret (usually a key) into several pieces which are then given to distinct persons so that some of these persons must cooperate to reconstruct the secret.

A Simple Approach

One simple approach to split a secret number $D$ into $n$ pieces $D_1,D_2,$…$,D_n$ such that any $k$ pieces are sufficient (and necessary) to reconstruct $D$ is using a $k-1$ polynomial.

When splitting the secret a random polynomial $f(x)=a_0+a_{1}x+a_{2}x+$…$+a_{k-1}{x}^{k-1}$ with $a_0=D$ is generated. The $D_i$ are calculated as $D_i=f(i)$ for $i=1,$…$,n$.

Given any $k$ $D_i$ it is possible to interpolate the polynomial and calculate $f(0)$ which gives the original secret $D$.

Example

Let $D=4$, $k=3$, $n=5$, that is: The secret is split into 5 parts of which at least 3 are necessary to reconstruct the secret.

Now generate 2 random numbers $a_1$ and $a_2$, let's say: $a_1=3,a_2=-1$ which give the polynomial $f(x)=4+3x-1x^2$. Obviously that's a quadratic function and any 3 points on the function are sufficient to interpolate the function.