key management;secret sharing;Shamir's scheme">


Question 103. 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 (e.g., 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 so that certain subsets of the persons can get together to recover the key.

The general model for secret sharing is called an m-out-of-n scheme (or (m,n)-threshold scheme) for integers 1 m n. In the 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 reveal no information about 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. A secret sharing scheme is perfect if any group of at most m - 1 participants (insiders) has no advantage in guessing the secret over the outsiders.

Both Shamir's scheme (see Question 104) and Blakley's scheme (see Question 105) are m-out-of-n secret sharing schemes. They represent two different ways of constructing such schemes, based on which more advanced secret sharing schemes can be designed. For further information on secret sharing schemes, see [Sim92].