Cryptology ePrint Archive: Report 2006/292

Ideal Multipartite Secret Sharing Schemes

Oriol Farras and 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.

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 format(s): 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


[ Cryptology ePrint archive ]