Secret sharing

Secret sharing is used as a term to refer to ways of sharing a secret among many people. Each person knows part of the secret that is shared, but a number of people need to cooperate to rebuild the secret. The knowledge of one person alone is not enough to reconstruct the secret. Adi Shamir and George Blakley developed the method independently of each other, in 1979.

One example where secret sharing is used is the RSA cryptosystem. It uses a secret key. If this key is distributed among many people, no single person can make a signature. Even if the part of one person is revealed or lost, a number of them can still make a signature. This is often used is areas where security is very important, such as banks, or the military.

The dealer hands each player their part of the secret. In an easier setup, the parts of the players can be combined to form the secret, but with each part there is extra information. Say that a secret needs five parts, and three parts are known. In this setup, guessing the two parts that are missing will be easier than guessing the secret awhen no parts are known. The other setup is said to be secure from the point of view of information theory, because knowing part of the required number of player parts will not change how difficult it is to guess the secret.

There are different methods of secure secret sharing techniques.

Shamir's method

In this method, any t out of the n shares may be used to recover the secret. The idea is that a polynomial of degree t-1 is defined by t points on the polynomial: It takes two points to define a straight line, three to define a quadratic curve, four for a cubic, and so on. It takes t points to define a polynomial of degree t-1. That way it is possible to build a polynomial, the first coefficient is the secret; there are n randomly picked coefficients. Each player receives one of the n coefficients. If there are at least t players, they can rebuild the original curve, and get the secret.