Secret Sharing: Difference between revisions

From
Jump to navigation Jump to search
 
Line 17: Line 17:
The image shows the resultant function (in red), the original secret (in green, at <math>x=0</math>) and the 5 new secret parts (in blue).
The image shows the resultant function (in red), the original secret (in green, at <math>x=0</math>) and the 5 new secret parts (in blue).


To reconstruct the original secret any 3 secret parts (let's say <math>D_2, D_3</math> and <math>D_5</math> are merged together:
To reconstruct the original secret any 3 secret parts (let's say <math>D_2, D_3</math> and <math>D_5</math>) are merged together:
[[Image:Secret-Sharing-merging.png]]
[[Image:Secret-Sharing-merging.png]]


Line 30: Line 30:
The image shows five of them (for <math>a_2 = -3</math>, <math>a_2 = -2</math>, <math>a_2 = -1</math>, <math>a_2 = 0</math> and <math>a_2 = 1</math>):
The image shows five of them (for <math>a_2 = -3</math>, <math>a_2 = -2</math>, <math>a_2 = -1</math>, <math>a_2 = 0</math> and <math>a_2 = 1</math>):
[[Image:Secret-Sharing-security.png]]
[[Image:Secret-Sharing-security.png]]
<table border="1" style="text-align: right">
<tr><th><math>a_0</math></th><th><math>a_1</math></th><th><math>a_2</math></th></tr>
<tr><td>16</td><td>-7</td><td>1</td></tr>
<tr><td>10</td><td>-2</td><td>0</td></tr>
<tr><td>4</td><td>3</td><td>-1</td></tr>
<tr><td>-2</td><td>8</td><td>-2</td></tr>
<tr><td>-8</td><td>13</td><td>-3</td></tr>
</table>

Latest revision as of 13:15, 1 December 2004

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