International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Ideal Multipartite Secret Sharing Schemes

Oriol Farràs
Jaume Martí-Farré
Carles Padró
Search ePrint
Search Google
Abstract: Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. In this work, the characterization of ideal multipartite access structures is studied with all generality. Our results are based on the well-known connections between ideal secret sharing schemes and matroids and on the introduction of a new combinatorial tool in secret sharing, integer polymatroids. Our results can be summarized as follows. First, we present a characterization of multipartite matroid ports in terms of integer polymatroids. As a consequence of this characterization, a necessary condition for a multipartite access structure to be ideal is obtained. Second, we use representations of integer polymatroids by collections of vector subspaces to characterize the representable multipartite matroids. In this way we obtain a sufficient condition for a multipartite access structure to be ideal, and also a unified framework to study the open problems about the efficiency of the constructions of ideal multipartite secret sharing schemes. Finally, we apply our general results to obtain a complete characterization of ideal tripartite access structures, which was until now an open problem.
  title={Ideal Multipartite Secret Sharing Schemes},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / Secret sharing, Ideal secret sharing schemes, Ideal access structures, Multipartite secret sharing, Multipartite matroids, Integer polymatroids},
  note={This is the full version of the paper that appeared in Eurocrypt 2007 14684 received 24 Aug 2006, last revised 16 Mar 2010},
  author={Oriol Farràs and Jaume Martí-Farré and Carles Padró},