Secret Sharing - Revision history

Henryk: /* Example */

2004-12-01T13:15:34Z

Example

← Older revision		Revision as of 13:15, 1 December 2004
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>

Henryk: /* Example */

2004-12-01T12:59:48Z

Example

← Older revision		Revision as of 12:59, 1 December 2004
Line 26:		Line 26:
	* <math>6 = a_0 + 2 a_1 + 4 a_2</math>		* <math>6 = a_0 + 2 a_1 + 4 a_2</math>
	* <math>4 = a_0 + 3 a_1 + 9 a_2</math>		* <math>4 = a_0 + 3 a_1 + 9 a_2</math>
	with three unknown variables thus allowing for infinitely many solutions.		with three unknown variables thus allowing for infinitely many solutions which are all equally likely.

			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]]

Henryk: /* Example */

2004-12-01T12:36:00Z

Example

← Older revision		Revision as of 12:36, 1 December 2004
Line 22:		Line 22:
	Then the polynomial is interpolated and <math>f(0)</math> computed:		Then the polynomial is interpolated and <math>f(0)</math> computed:
	[[Image:Secret-Sharing-reconstruction.png]]		[[Image:Secret-Sharing-reconstruction.png]]

			Let's suppose we wanted to reconstruct the shared secret but only had two of the parts: <math>D_2</math> and <math>D_3</math>. This gives two equations:
			* <math>6 = a_0 + 2 a_1 + 4 a_2</math>
			* <math>4 = a_0 + 3 a_1 + 9 a_2</math>
			with three unknown variables thus allowing for infinitely many solutions.

Henryk: /* Example */

2004-12-01T11:09:51Z

Example

← Older revision		Revision as of 11:09, 1 December 2004
Line 11:		Line 11:
	Let <math>D = 4</math>, <math>k = 3</math>, <math>n = 5</math>, that is: The secret is split into 5 parts of which at least 3 are necessary to reconstruct the secret.		Let <math>D = 4</math>, <math>k = 3</math>, <math>n = 5</math>, 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 <math>a_1</math> and <math>a_2</math>, let's say: <math>a_1 = 3, a_2 = -1</math> which give the polynomial <math>f(x) = 4 + 3 x - 1 x^2</math>. Obviously that's a quadratic function and any 3 points on the function are sufficient to interpolate the function.		Now generate 2 random numbers <math>a_1</math> and <math>a_2</math>, let's say: <math>a_1 = 3</math>, <math>a_2 = -1</math> which give the polynomial <math>f(x) = 4 + 3 x - 1 x^2</math>. Obviously that's a quadratic function and any 3 points on the function are sufficient to interpolate the function.

			[[Image:Secret-Sharing-polynomial.png]]

			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:
			[[Image:Secret-Sharing-merging.png]]

			Then the polynomial is interpolated and <math>f(0)</math> computed:
			[[Image:Secret-Sharing-reconstruction.png]]

Henryk: /* Example */

2004-12-01T10:51:53Z

Example

← Older revision		Revision as of 10:51, 1 December 2004
Line 10:		Line 10:
	=== Example ===		=== Example ===
	Let <math>D = 4</math>, <math>k = 3</math>, <math>n = 5</math>, that is: The secret is split into 5 parts of which at least 3 are necessary to reconstruct the secret.		Let <math>D = 4</math>, <math>k = 3</math>, <math>n = 5</math>, 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 <math>a_1</math> and <math>a_2</math>, let's say: <math>a_1 = 3, a_2 = -1</math> which give the polynomial <math>f(x) = 4 + 3 x - 1 x^2</math>. Obviously that's a quadratic function and any 3 points on the function are sufficient to interpolate the function.

Henryk at 10:44, 1 December 2004

2004-12-01T10:44:51Z

← Older revision		Revision as of 10:44, 1 December 2004
Line 7:		Line 7:

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

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

Henryk at 10:33, 1 December 2004

2004-12-01T10:33:16Z

← Older revision		Revision as of 10:33, 1 December 2004
Line 2:		Line 2:

	== A Simple Approach ==		== A Simple Approach ==
	One simple approach to split a secret number <math>D</math> into <math>n</math> pieces <math>D_1, D_2, ~~\ldots~~, D_n</math> such that any <math>k</math> pieces are sufficient (and necessary) to reconstruct <math>D</math> is using a <math>k-1</math> polynomial.		One simple approach to split a secret number <math>D</math> into <math>n</math> pieces <math>D_1, D_2, </math>…<math>, D_n</math> such that any <math>k</math> pieces are sufficient (and necessary) to reconstruct <math>D</math> is using a <math>k-1</math> polynomial.

	When splitting the secret a random polynomial <math>f(x) = a_0 + a_1 ~~\cdot~~ x + a_2 ~~\cdot~~ x + ~~\ldots~~ a_{k-1} x^{k-1}</math> with <math>a_0 = D</math> is generated. The <math>D_i</math> are calculated as <math>D_i = f(i) ~~\mbox{~~ for } i = 1, ~~\ldots~~, n</math>.		When splitting the secret a random polynomial <math>f(x) = a_0 + a_1 x + a_2 x + </math>…<math> + a_{k-1} x^{k-1}</math> with <math>a_0 = D</math> is generated. The <math>D_i</math> are calculated as <math>D_i = f(i)</math> for <math>i = 1, </math>…<math>, n</math>.

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

Henryk at 10:23, 1 December 2004

2004-12-01T10:23:34Z

New page

''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 <math>D</math> into <math>n</math> pieces <math>D_1, D_2, \ldots, D_n</math> such that any <math>k</math> pieces are sufficient (and necessary) to reconstruct <math>D</math> is using a <math>k-1</math> polynomial.

When splitting the secret a random polynomial <math>f(x) = a_0 + a_1 \cdot x + a_2 \cdot x + \ldots a_{k-1} x^{k-1}</math> with <math>a_0 = D</math> is generated. The <math>D_i</math> are calculated as <math>D_i = f(i) \mbox{ for } i = 1, \ldots, n</math>.

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