Secret Sharing

From
Revision as of 13:15, 1 December 2004 by Henryk (talk | contribs) (→‎Example)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 into pieces such that any pieces are sufficient (and necessary) to reconstruct is using a polynomial.

When splitting the secret a random polynomial with is generated. The are calculated as for .

Given any it is possible to interpolate the polynomial and calculate which gives the original secret .

Example

Let , , , 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 and , let's say: , which give the polynomial . Obviously that's a quadratic function and any 3 points on the function are sufficient to interpolate the function.

Secret-Sharing-polynomial.png

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

To reconstruct the original secret any 3 secret parts (let's say and ) are merged together: Secret-Sharing-merging.png

Then the polynomial is interpolated and computed: Secret-Sharing-reconstruction.png

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

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

The image shows five of them (for , , , and ): Secret-Sharing-security.png

16-71
10-20
43-1
-28-2
-813-3