您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2014, Vol. 49 ›› Issue (09): 74-82.doi: 10.6040/j.issn.1671-9352.2.2014.181

• 论文 • 上一篇    下一篇

参与者人数为9的一类连通超图存取结构的信息率

张娜, 李志慧   

  1. 陕西师范大学数学与信息科学学院, 陕西 西安 710119
  • 收稿日期:2014-06-24 修回日期:2014-08-27 出版日期:2014-09-20 发布日期:2014-09-30
  • 通讯作者: 李志慧（1966-），女，教授，博士，研究方向为有限域和密码学.E-mail：lizhihui@snnu.edu.cn E-mail:lizhihui@snnu.edu.cn
  • 作者简介:张娜（1989-），女，硕士研究生，研究方向为有限域和密码学.E-mail：zhangna1@snnu.edu.cn
  • 基金资助:
    国家自然科学基金资助项目（61373150）；陕西省科学技术研究发展计划工业攻关项目（2013K0611）

The optimal information rate of a type of access structures based on connected hypergraphs on nine participants

ZHANG Na, LI Zhi-hui   

  1. College of Mathematics and Information Science, Shaanxi Normal University, Xi'an 710119, Shaanxi, China
  • Received:2014-06-24 Revised:2014-08-27 Online:2014-09-20 Published:2014-09-30

PDF (PC)

599

摘要： 基于存取结构与连通超图之间的关系，给出了顶点数为9，秩为3，超边数为4和5的一共226种不同构的连通超图存取结构，进而估算了它们的最优信息率。本文首先证明了具有4条超边的一类超星可以用理想的秘密共享方案来实现，并证明了满足一定条件的顶点数为n（5≤n≤11），超边数为5且秩为3的连通超图其最优信息率的下界为2/3。运用超图的相关理论对其中的16种超图存取结构最优信息率的精确值进行了计算，对余下的210种超图存取结构进行了分类，并估算了这些超图存取结构最优信息率的界。

关键词: 超图, 理想超图, 秘密共享方案, 最优信息率, 超图存取结构

Abstract: Based on the relationship between access structures and connected hypergraph, 226 connected hypergraph access structures with 9 vertices, 3 ranks and 4 or 5 hyperedges were given. These structures are not mutually isomorphism, and their optimal information rates were estimated. First, it was proved that there exists ideal secret sharing scheme for a kind of hyperstar with 4 hyperedges and shown that the lower bounds of the optimal information rates of the connected hypergraph with n(5≤n≤11) vertices and 3 ranks are 2/3. Then using the theory of hypergraphs, the exact values for the optimal information rate of 16 access structures were computed. Final, the remaining 210 access structures were classified, and the bounds of the optimal information rates of these access structures were estimated.

Key words: ideal hypergraph, secret sharing schemes, hypergraph access structure, optimal information rate, hypergraph

中图分类号: 

  • TP309
[1] 刘木兰, 张志芳. 密钥共享体制和安全多方计算[M]. 北京: 电子工业出版社, 2008. LIU Mulan, ZHANG Zhifang. Secret sharing schemes and secure multiparty computation[M].Beijing: Publishing House of Electronics Industry, 2008.
[2] JACKSON W, MARTIN K M. Perfect secret sharing schemes on five participants[J]. Designs, Codes and Cryptography, 1996, 9(3):267-286.
[3] GHARAHI M, DEHKORDI M H,The complexity of the graph access structures on six participants[J]. Designs, Codes and Cryptography, 2013, 67(2):169-173.
[4] VAN D M. On the information rate of perfect secret sharing schemes[J]. Designs, Codes and Cryptography, 1995, 6(2): 143-169.
[5] SONG Yun, LI Zhihui, WANG Weicong. The information rate of secret sharing schemes based on seven participants by connect graphs[J]. Recent Advance in Computer Science and Information Engineering Lecture Notes in Electrical Engineering, 2012, 127:637-645.
[6] 宋云, 李志慧. 参与者人数为八的一类图存取结构的信息率[J]. 计算机工程与应用, 2012, 48 (14): 112-116. SONG Yun, LI Zhihui. Information rate of a type of access structures based on graphs on eight participants[J]. Computer Engineering and Applications, 2012, 48(14):112-116.
[7] 杨丽杰, 李志慧, 李婧. 一类超图存取结构的秘密共享方案的信息率[J]. 计算机应用研究, 2013, 30(7): 2115-2119. YANG Lijie, LI Zhihui, LI Jing. Information rate of secret sharing schemes of type of access structures based on hypergraphs[J].Application Research of Computers, 2013, 30(7):2115-2119.
[8] 李志慧, 杨丽杰. 7人参与者的一类超图存取结构的最优信息率[J]. 陕西师范大学学报, 2014, 42(1):1-6. LI Zhihui, YANG Lijie. The optimal information rate of a type of access structures based on hypergraphs on seven participants[J]. Journal of Shaanxi Normal University, 2014, 42(1):1-6.
[9] MARTI F J, PADRO C. Secret sharing schemes with three or four minimal qualified subsets[J]. Design,Codes and Cryptography, 2005, 34(1): 17-34.
[10] GIOVAANNI D C, CLEMENTE G. Hypergraph decomposition and secret sharing [J]. Discrete Applied Mathematics, 2009, 157(5):928-946.
[1] 张军琪,高海英. 在线/离线非单调CP-ABE方案构造[J]. 山东大学学报（理学版）, 2016, 51(12): 78-86.
[2] 关爱霞, 李芳, 李国全. 关于诱导度偏差的指数型上尾估计[J]. 山东大学学报（理学版）, 2015, 50(12): 73-75.
[3] 薛丽霞, 李志慧, 谢佳丽. 对3条超边的超圈存取结构最优信息率的一点注记[J]. 山东大学学报（理学版）, 2015, 50(11): 60-66.
[4] 刘雅辉1,2,刘春阳3*,张铁赢1,程学旗1. 图索引技术研究综述[J]. J4, 2013, 48(11): 44-52.
[5] 孙林. 几个特殊超图在完美图上的应用[J]. J4, 2011, 46(8): 92-94.
[6] 刘洪平 赵平 许娟. 一类弱惟一染色B-超图的构造及其最小点数[J]. J4, 2010, 45(2): 5-9.
[7] 杨朝霞 . 超图嵌入带权重圈的一个2-近似算法[J]. J4, 2008, 43(8): 11-13 .
[8] 刁科凤,赵　平 . 具有最小连通点对图的C-超图的染色讨论[J]. J4, 2007, 42(2): 56-58 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发