Multipartite matroids and secret sharing  

作　　者：HSU ChingFang TANG XueMing CHENG Qi XIAO HaiJun 

机构地区：[1]College of Computer Science & Technology, Huazhong University of Science and Technology, Wuhan 430074, China [2]Institute of Wuhan Digital Engineering, Wuhan 430074, China [3]School of Mathematics & Physics, China University ofGeosciences, Wuhan 430074, China

出　　处：《Chinese Science Bulletin》2010年第29期3261-3266,共6页

基　　金：supported by the National Natural Science Foundation of China (60903196)

摘　　要：In a secret-sharing scheme,a secret value is distributed among a set of participants by giving each participant a share.The requirement is that only predefined subsets of participants can recover the secret from their shares.The family of the predefined authorized subsets is called the access structure.An access structure is ideal if there exists a secret-sharing scheme realizing it in which the shares have optimal length,that is,in which the shares are taken from the same domain as the secrets.Brickell and Davenport proved that ideal access structures are induced by matroids.Subsequently,ideal access structures and access structures induced by matroids have received a lot of attention.Seymour gave the first example of an access structure induced by a matroid namely the Vamos matroid,that is non-ideal.Since every matroid is multipartite and has the associated discrete polymatroid,in this paper,by dealing with the rank functions of discrete polymatroids,we obtain a sufficient condition for a multipartite access structure to be ideal.Furthermore,we give a new proof that all access structures related to bipartite and tripartite matroids coincide with the ideal ones.Our results give new contributions to the open problem,that is,which matroids induce ideal access structures.In a secret-sharing scheme, a secret value is distributed among a set of participants by giving each participant a share. The requirement is that only predefined subsets of participants can recover the secret from their shares. The family of the predefined authorized subsets is called the access structure, An access structure is ideal if there exists a secret-sharing scheme realizing it in which the shares have optimal length, that is, in which the shares are taken from the same domain as the secrets. Brickell and Davenport proved that ideal access structures are induced by matroids. Subsequently, ideal access structures and access structures induced by matroids have received a lot of attention. Seymour gave the first example of an access structure induced by a matroid namely the Vamos matroid, that is non-ideal. Since every matroid is multipartite and has the associated discrete polymatroid, in this paper, by dealing with the rank functions of discrete polymatroids, we obtain a sufficient condition for a multipartite access structure to be ideal. Furthermore, we give a new proof that all access structures related to bipartite and tripartite matroids coincide with the ideal ones. Our results give new contributions to the open problem, that is, which matroids induce ideal access structures.

关 键 词：秘密共享方案 拟阵 访问结构 接入结构 最佳长度 充分条件 公开问题 参与者 

分 类 号：TN918.1[电子电信—通信与信息系统]