Paper 2019/1100

Efficient Explicit Constructions of Multipartite Secret Sharing Schemes

Qi Chen, Chunming Tang, and Zhiqiang Lin


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. Secret sharing schemes for multipartite access structures have received considerable attention due to the fact that multipartite secret sharing can be seen as a natural and useful generalization of threshold secret sharing. This work deals with efficient and explicit constructions of ideal multipartite secret sharing schemes, while most of the known constructions are either inefficient or randomized. Most ideal multipartite secret sharing schemes in the literature can be classified as either hierarchical or compartmented. The main results are the constructions for ideal hierarchical access structures, a family that contains every ideal hierarchical access structure as a particular case such as the disjunctive hierarchical threshold access structure and the conjunctive hierarchical threshold access structure, the constructions for three families of compartmented access structures, and the constructions for two families compartmented access structures with compartments. On the basis of the relationship between multipartite secret sharing schemes, polymatroids, and matroids, the problem of how to construct a scheme realizing a multipartite access structure can be transformed to the problem of how to find a representation of a matroid from a presentation of its associated polymatroid. In this paper, we give efficient algorithms to find representations of the matroids associated to several families of multipartite access structures. More precisely, based on know results about integer polymatroids, for each of those families of access structures above, we give an efficient method to find a representation of the integer polymatroid over some finite field, and then over some finite extension of that field, we give an efficient method to find a presentation of the matroid associated to the integer polymatroid. Finally, we construct ideal linear schemes realizing those families of multipartite access structures by efficient methods.

Note: This is a full and extended version of the article accepted at ASIACRYPT 2019

Available format(s)
Publication info
Published elsewhere. Major revision. IACR-ASIACRYPT-2019
Secret sharing schemesMultipartite access structuresMatroidsPolymatroids.
Contact author(s)
chenqi math @ gmail com
2019-09-29: received
Short URL
Creative Commons Attribution


      author = {Qi Chen and Chunming Tang and Zhiqiang Lin},
      title = {Efficient Explicit Constructions of Multipartite Secret Sharing Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1100},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.