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$):