|
|
Milestone Year
1979
How to Share a Secret
Suppose that you want to share a secret among the members of a committee by distributing shares to the members such that any strict majority of the members can reconstruct the secret but no minority group can learn anything about the secret. More generally, the problem is parameterized by two quantities: The number of parties n, and the threshold t, which represents the number of parties that is necessary and sufficient to reconstruct the secret.
In 1979, a Weizmann scientist presented a simple solution for the above problem. The solution consists of having the dealer select a random polynomial of degree t, over a finite field, with a free term that equals the secret, and distribute to the parties the values of this polynomial at distinct (non-zero) evaluation points.
The above notion of secret sharing as well as the simple solution sketched above have had a vast impact on further developments in the area of cryptography. Typically applications include cases where the problem's definition contains a dichotomy between what few parties versus many parties may be able to do.