2.1.9 What are secret sharing schemes?
Secret sharing schemes were discovered independently by Blakley [Bla79] and Shamir [Sha79]. The motivation for secret sharing is secure key management. In some situations, there is usually one secret key that provides access to many important files. If such a key is lost (for example, the person who knows the key becomes unavailable, or the computer which stores the key is destroyed), then all the important files become inaccessible. The basic idea in secret sharing is to divide the secret key into pieces and distribute the pieces to different persons in a group so that certain subsets of the group can get together to recover the key.
As a very simple example, consider the following scheme that includes a group of n people. Each person is given a share si, which is a random bit string of a fixed specified length. The secret is the bit string
s = s1 Ås2 Å¼Åsn.
Note that all shares are needed to recover the secret.
A general secret sharing scheme specifies the minimal sets of users who are able to recover the secret by sharing their secret information. A common example of secret sharing is an m-out-of-n scheme (or (m,n)-threshold scheme) for integers 1 £ m £ n. In such a scheme, there is a sender (or dealer) and n participants. The sender divides the secret into n parts and gives each participant one part so that any m parts can be put together to recover the secret, but any m - 1 parts do not suffice to determine the secret. The pieces are usually called shares or shadows. Different choices for the values of m and n reflect the tradeoff between security and reliability. An m-out-of-n secret sharing scheme is perfect if any group of at most m-1 participants (insiders) cannot determine more information about the secret than an outsider. The simple example above is a perfect n-out-of-n secret sharing scheme.
Both Shamir's scheme and Blakley's scheme (see Question 3.6.12) are m-out-of-n secret sharing schemes, and Shamir's scheme is perfect in the sense just described. They represent two different ways of constructing such schemes, based on which more advanced secret sharing schemes can be designed. The study of the combination of proactive techniques (see Question 7.16) with secret sharing schemes is an active area of research. For further information on secret sharing schemes, see [Sim92].