Paper 2006/292

Ideal Multipartite Secret Sharing Schemes

Oriol Farras, Jaume Marti-Farre, and Carles Padro

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.

Note: September 3, 2006: Revised version with minor changes. March 16, 2010: thorough revision

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. This is the full version of the paper that appeared in Eurocrypt 2007
Keywords
Secret sharingIdeal secret sharing schemesIdeal access structuresMultipartite secret sharingMultipartite matroidsInteger polymatroids
Contact author(s)
cpadro @ ma4 upc edu
History
2010-03-16: last of 2 revisions
2006-08-24: received
See all versions
Short URL
https://ia.cr/2006/292
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/292,
      author = {Oriol Farras and Jaume Marti-Farre and Carles Padro},
      title = {Ideal Multipartite Secret Sharing Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2006/292},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/292}},
      url = {https://eprint.iacr.org/2006/292}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.