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.

The image shows the resultant function (in red), the original secret (in green, at $x=0$) and the 5 new secret parts (in blue).

To reconstruct the original secret any 3 secret parts (let's say $D_2,D_3$ and $D_5$) are merged together:

Then the polynomial is interpolated and $f(0)$ computed:

Let's suppose we wanted to reconstruct the shared secret but only had two of the parts: $D_2$ and $D_3$. This gives two equations:

• $6=a_0+2a_1+4a_2$
• $4=a_0+3a_1+9a_2$

with three unknown variables thus allowing for infinitely many solutions which are all equally likely.

The image shows five of them (for $a_2=-3$, $a_2=-2$, $a_2=-1$, $a_2=0$ and $a_2=1$):

$a_0$	$a_1$	$a_2$
16	-7	1
10	-2	0
4	3	-1
-2	8	-2
-8	13	-3