O. Farràs, J. Martí-Farré, C. Padró

Ideal Multipartite Secret Sharing Schemes
Advances in Cryptology, Eurocrypt 2007. Lecture Notes in Computer Science 4515 (2007) 448-465

Abstract

The characterization of the access structures of ideal secret sharing schemes is one of the main open problems in secret sharing. Because of its difficulty, it has been studied for several particular families of access structures. In this paper, we deal with multipartite access structures, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Some particular classes of multipartite structures have been studied in seminal works on secret sharing by Shamir, Simmons, and Brickell, and also recently by several authors. In this work, the characterization of ideal multipartite access structures is studied with all generality. Actually, every access structure is multipartite and, hence, the results in this paper can be seen as an attack under a different point of view to the general open of the characterization of ideal access structures. Namely, we present some necessary conditions and some sufficient conditions for an access structure to be ideal in terms of the classification of its participants into equivalence classes. These conditions can be specially useful if the number of classes is small or these classes are distributed in some special way. More specifically, our results are the following:

1. We present a characterization of matroid-related multipartite access structures in terms of discrete polymatroids. To do that, we study the relation between multipartite matroids and discrete polymatroids. As a consequence of this characterization, a necessary condition for a multipartite access structure to be ideal is obtained.

2. We define a special class of discrete polymatroids: the linearly representable ones. We use these discrete polymatroids to characterize the representable multipartite matroids. In this way we obtain a sufficient condition for a multipartite access structure to be ideal.

3. We apply those general results to obtain a complete characterization of ideal tripartite access structures, which was until now an open problem. In particular, we prove that the matroid-related tripartite access structures coincide with the ideal ones.


 
Download  mltprtt.pdf