display | more...

Say you have an important secret, for instance nuclear launch codes that you want to keep safe not only from your enemies but also from possible problems among the people you are supposed to trust. You wouldn't want a lone madman among your generals to initiate a nuclear launch. You also wouldn't want two madmen to collaborate and initiate a launch. Military high command, however, decides that the risk of having three insane generals is sufficiently low, and requires that at least three generals give their authorization before a launch occurs.

A similar scenario is that the CEO of a corporation knows the cryptographic keys to encrypt the company's most vital secrets, but in case she gets run over by a bus, a certain number of her underlings can reconstruct the key. But she doesn't want one or two of her five vice presidents who have been bribed by the competition to be able to reconstruct her key and steal the secrets when she's not looking, and the stockholders don't want the secrets to be lost if she were flying with one of her vice presidents and the plane blows up.

Secret sharing algorithms provide a solution to this problem by using cryptography. In their simplest form, they basically take a large secret, and produce n pieces (called shadows) such that m of these pieces will be sufficient to reconstruct the whole secret. This is called an (m, n)-threshold scheme in the literature.

One scheme developed for doing this was invented by Adi Shamir (the "S" in RSA). His scheme involves creating the shadows by using polynomial equations in a finite field. Get a finite field whose cardinality is greater than the size of the largest possible secret and the largest number of shadows. To create an (m,n)-threshold scheme with this method, generate an arbitrary polynomial of degree (m-1) in this finite field. Say you wanted a (3, n)-threshold scheme, you can generate a quadratic polynomial in GF(p) (where p is a prime larger than M and n):

F(x) = ax2 + bx2 + M mod p

where M is the secret to be shared. The coefficients a and b must be kept secret and discarded after the shadows are generated.

The shadows are generated by evaluating the polynomial at n points:

ki = F(xi)

so the shadows are the points (ki, F(xi)). Since these are points on a quadratic polynomial, three of these shadows will be sufficient to reconstruct the original polynomial (and hence the secret) by using the Lagrange interpolation formula.

Another scheme was developed independently by George Blakley that works by expressing the secret to be shared as a point in m-dimensional space. Each shadow is the equation of a random (m-1)-dimensional hyperplane that contains the secret point. These hyperplanes should be linearly independent, so solving the system of equations formed by taking m of them together will recover the secret.

Several other schemes have also been devised and are in the literature. The most intriguing property of all of these secret sharing schemes is that provided everything was done properly, they are provably secure. That is, say for a (3,5) thresholding scheme, two people with infinite computing power will be unable to learn anything about the secret. This is as secure as a one time pad.