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
- 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
- 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
[edit] Software
SSSS: a C implementation of Shamir's scheme, with online demo page.
