Threshold shadow scheme

From Wikipedia, the free encyclopedia

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.

[edit] 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):