A secret sharing scheme is a protocol by which a dealer distributes a secret among a set of participants in such a way that only qualified sets of them can reconstruct the value of the secret whereas any non-qualified subset of participants obtain no information at all about the value of the secret. Secret sharing schemes have always played a very important role in the construction of higher level cryptographic primitives and protocols.
In this paper we investigate the construction of efficient secret sharing schemes by using a technique called {\em hypergraph decomposition}, extending in a non-trivial way the previously studied graph decomposition technique.
The application of this technique allows us to obtain secret sharing schemes for particular and large classes of access structures (such as hyperpaths, hypercycles, hyperstar and hypertrees) with dramatically improved efficiency over previous results. Specifically, in all cases, schemes obtained using previous techniques generate shares of exponential blowup in size, while for ours the blowup is always polynomial, in some cases even constant. Our schemes are also complemented by bounds on the blowup that are essentially tight.
In the course of the formulation of the hypergraph decomposition
technique, we also obtain an elementary characterization
of the ideal access structures among the hyperstar,
which is of independent interest.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-35.ps.gz
DIMACS Home Page