An algorithm for efficient geometric secret sharing schemes

Abstract

A secret sharing scheme is a method of distributing among a set of participants some information relating to a secret. A secret sharing scheme can be associated with two disjoint collections Γ, Δ of sets of participants. Sets of participants in Γ can use their information to reconstruct, the secret, whilst sets of participants in Δ cannot gain any knowledge of the secret from their information. Geometric secret sharing schemes form a wide class of secret sharing schemes with desirable properties. We present an algorithm for the construction of optimally efficient geometric secret sharing schemes. In order to do so, we first show that with the exception of degenerate cases, every geometric scheme can be obtained directly from its corresponding cumulative scheme (a generally inefficient secret sharing scheme which has a simple algorithmic construction). We analyse the complexity of our algorithm and discuss other published algorithms.