Threshold shadow scheme

A threshold shadow scheme (also known as a "threshold signature scheme" or "secret sharing") is a form of secure multiparty computation in which a message is shared between several (N) people. Any piece of the message on its own is totally meaningless, owning 1/Nth of the message will not allow reading of 1/Nth of the message. Only when all people put their parts together can the entire message be read. It may be required that less than N people can come together in order to recreate the entire message, or that some people will have more weight than others.

For example, a missile system might be designed such that the missiles can not be launched unless two generals and a colonel insert their keys.

Possible implementation

Shamir's scheme uses polynomial interpolation. Let's split a message M into N parts, where only T parts are required to reconstruct the original.Simplified it comes down to this:
* Represent the secret to share as an integer M. (Usually over a Finite field)
* Generate T-1 random numbers, Ri
* Construct the polynomial $y(x)\; =\; M\; +\; sum\_\{i=1\}^\{T-1\}\; R\_i\; cdot\; x^i$
* The N parts are the number-pairs { (1, y(1)); (2, y(2)); (3, y(3)); ...; (N, y(N)) }

To reconstruct the message, you need to interpollate the original polynomial. You need at least T points on that polynomial to reconstruct it.The original message is then y(0).

There are ways to update the shared secret (in case of theft of one of them):
* Generate T-1 random numbers, Ri
* Generate a polynomial of the form $y\text{'}(x)\; =\; 0\; +\; sum\_\{i=1\}^\{T-1\}\; R\_i\; cdot\; x^i$
* Recalculate the number pairs { (1, y'(1)); ... }
* Send each owner his part
* Each owner should calculate y"(i) = y(i) + y'(i)
* y" becomes the new part, y and y' should be destroyed

Software

[http://point-at-infinity.org/ssss/ SSSS] : a C implementation of Shamir's scheme, with online demo page.