You are looking at a specific version 20190929:183715 of this paper. See the latest version.

Paper 2019/1100

Efficient Explicit Constructions of Multipartite Secret Sharing Schemes

Qi Chen and Chunming Tang and Zhiqiang Lin

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. 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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. IACR-ASIACRYPT-2019
Keywords
Secret sharing schemesMultipartite access structuresMatroidsPolymatroids.
Contact author(s)
chenqi math @ gmail com
History
2019-09-29: received
Short URL
https://ia.cr/2019/1100
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.