Sharing Multiple Secrets: Models, Schemes, and Analysis

A multi-secret sharing scheme is a protocol to share more than one secret among a set of participants, where each secret may have a distinct family of subsets of participants (also called ‘access structure’) that are qualified to recover it. In this paper we use an information-theoretic approach to analyze two different models for multi-secret sharing schemes. The proposed models generalize specific models which have already been considered in the literature. We first analyze the relationships between the security properties of the two models. Afterwards, we show that the security property of a multi-secret sharing scheme does not depend on the particular probability distribution on the sets of secrets. This extends the analogous result for the case of single-secret sharing schemes and implies that the bounds on the size of the information distributed to participants in multi-secret sharing schemes can all be strengthened. For each of the two models considered in this paper, we show lower bounds on the size of the shares distributed to participants. Specifically, for the general case in which the secrets are shared according to a tuple of arbitrary (and possibly different) access structures, we show a combinatorial condition on these structures that is sufficient to require a participant to hold information of size larger than a certain subset of secrets. For specific access structures of particular interest, namely, when all access structures are threshold structures, we show tight bounds on the size of the information distributed to participants.