Scalable threshold closure

Abstract

Secret sharing is an important concept for implementing robust and secure computer systems. A (t, ℓ)-threshold scheme such as Shamir's (Commun. ACM22(11) (1979) 612-613) is a mechanism that allows a set of ℓ participants to share a secret such that only subsets of t or more participants can reconstruct it. The threshold scheme, though simple and easy to implement, is not flexible enough to support complex secret sharing policies typical in practical systems. An access structure (Benaloh and Leichter, Advances in Cryptology - CRYPTO'88, Lecture Notes in Computer Science, vol. 403, Springer, Berlin, 1990, pp. 27-35; Ito et al., Globecom'87, Tokyo, Japan, 1987, pp. 99-102), on the other hand, is a powerful concept by which complex secret sharing schemes may be represented. However, the implementation is very complicated when the access structure contains a great number of authorized sets. This paper introduces a new construction for the secret sharing schemes called threshold closure, which allows a complex access structure it represents to be realized by possibly the fewest number of (t, ℓ)-threshold schemes. © 1999 Elsevier Science B.V. All rights reserved.