ABSTRACT
A secret sharing scheme is a method of protecting a secret among a group of participants in such a way that only certain specified subsets of the participants (those belonging to an access structure) can reconstruct the secret. A secret sharing scheme is normally initialized by a trusted dealer who securely transfers a piece of information related to the secret, called a share, to each participant in the scheme. The first secret sharing schemes proposed independently by Shamir [142] and Blakley [21] were (t, n)-threshold schemes where the access structure consists of all subsets of at least t (out of a total number of n) participants. Secret sharing schemes for general access structures were introduced and constructed by Ito, Saito, and Nishizeki [79]. Secret sharing schemes, originally motivated by the problem in secure information storage, have become an indispensable basic cryptographic tool in any security environment where active entities are groups rather than individuals, e.g., general protocols for multiparty computation, Byzantine agreement, threshold cryptography, access control, and generalized oblivious transfer (cf. [9]).
