A t-out-of-l threshold scheme is a generalization of a an erasure code. An (l+1,t) erasure code can correct up to l+1-t erasures. In a threshold scheme one also has up to l+1-t erasures. However, the first entry, called the secret key, is always one of these l+1-t erasures and one is not interested in correcting the other erasures, called shares. Secret sharing schemes, which are a generalization of threshold schemes, have mainly been studied from an information theoretical and combinatorial viewpoint.

In many applications the entropy of the secret key is zero, and an information theoretical treatment makes then no sense. We therefore discuss a computational complexity treatment of secret sharing. A way to address this issue is to develop threshold schemes that work over any (Abelian) group. One method presented to achieve this is a generalization of the Reed-Solomon codes. The erasure code and error-correcting properties of this generalized code are discussed in detail. Other methods to achieve group independent threshold schemes have been presented. These rely on combinatorics, e.g., on Vandermonde's convolution and on families of perfect hash functions. We briefly discuss the importance and applications of group independent threshold schemes.

In many threshold schemes, t-1 shares have been chosen uniformly. A new research goal is to develop secret sharing schemes in which the shares are not uniform, but corresponds to ordinary pictures, sound, etc. Methods to achieve this are briefly discussed. Such secret sharing schemes may be used towards watermarking.

Back to Workshop Schedule