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.
Category / Keywords: cryptographic protocols / Secret sharing, Ideal secret sharing schemes, Ideal access structures, Multipartite secret sharing, Multipartite matroids, Integer polymatroids Publication Info: This is the full version of the paper that appeared in Eurocrypt 2007 Date: received 24 Aug 2006, last revised 16 Mar 2010 Contact author: cpadro at ma4 upc edu Available formats: PDF | BibTeX Citation Note: September 3, 2006: Revised version with minor changes. March 16, 2010: thorough revision Version: 20100316:143058 (All versions of this report) Discussion forum: Show discussion | Start new discussion