一类图存取结构的最优信息率计算

doi:10.3969/j.issn.1671-1122.2022.04.009

摘要/Abstract

摘要：

秘密共享为密钥管理提供了一个非常有效的途径,而存取结构的信息率为高效秘密共享方案的设计提供了理论保证。文章利用存取结构与连通图之间的关系,将参与者人数为8的一类存取结构转化为连通图中顶点数为8、边数为9且最大顶点度为3的一类共63种图存取结构,并分别通过分裂构造法、熵方法、顶点度定理、分解构造法、加权分解法对这63种图存取结构的最优信息率的准确值或上下界进行计算,得出其中30种图存取结构最优信息率的准确值和其余33种图存取结构最优信息率的上下界。

关键词: 图存取结构, 最优信息率, 秘密共享方案, 图的分解

Abstract:

Secret sharing provides a very effective way for key management and the information rate of access structure provides a theoretical guarantee for the design of efficient secret sharing scheme. In this paper, by using the relationship between access structure and connected graph, a class of access structure with 8 participants is transformed into a class of 63 graph access structures with 8 vertices, 9 edges and a maximum vertex degree of 3. The accurate value or upper and lower bounds of the optimal information rate of these 63 graph access structures are calculated by splitting construction method, entropy method, vertex degree theorem, decomposition construction method and weighted decomposition method. The accurate values of the optimal information rates of 30 graph access structures and the upper and lower bounds of the optimal information rates of the other 33 graph access structures are obtained.

Key words: graph access structure, optimal information rate, secret sharin scheme, decomposition of graphs

中图分类号:

TP309

吕凯欣, 李志慧, 黑吉辽, 宋云. 一类图存取结构的最优信息率计算[J]. 信息网络安全, 2022, 22(4): 77-85.

LYU Kaixin, LI Zhihui, HEI Jiliao, SONG Yun. Optimal Information Rate Calculation Based on a Class of Graph Access Structure[J]. Netinfo Security, 2022, 22(4): 77-85.

图/表 7

图1

表1

8个顶点、9条边且最大顶点度为3的存取结构

存取结构名称	存取结构	存取结构名称	存取结构
G1	AB+AC+AF+BD+BE+ CD+CE+DG+FH	G33	AB+AD+AH+BC+BE+ CD+CF+EG+FG
G2	AB+AC+AF+BC+BE+ CD+DE+DG+EH	G34	AB+AD+AH+BC+BD+ CE+CF+EG+FG
G3	AF+AG+AH+BC+BD+ BF+CD+CE+DE	G35	AB+AD+AH+BE+BF+ CE+CF+CG+DG
G4	AB+AG+AH+BC+BD+ CE+CF+DE+DF	G36	AB+AD+AH+BC+BE+ CE+CF+DG+FG
G5	AB+AG+AH+BC+BE+ CD+CF+DE+DF	G37	AB+AC+AH+BD+BE+ CD+CF+EG+FG
G6	AB+AG+AH+BC+BD+ CD+CE+DF+EF	G38	AB+AD+AH+BC+BE+ CF+CG+DE+FG
G7	AB+AE+AG+BC+BF+ CD+CF+DE+DH	G39	AB+AD+AH+BC+BE+ CF+CG+DG+EF
G8	AB+AE+AG+BC+BD+ CE+CF+DF+DH	G40	AB+AC+AH+BD+BE+ CF+CG+DF+EG
G9	AE+AF+AG+BC+BD+ BE+CD+CF+DH	G41	AB+AC+AH+BD+BE+ CF+CG+DE+FG
G10	AB+AE+AG+BC+BF+ CD+CE+DF+DH	G42	AB+AC+AH+BC+BD+ CE+DF+EG+FG
G11	AB+AE+AG+BC+BE+ CD+CF+DF+DH	G43	AB+AD+AE+BF+BG+ CE+CF+CG+DH
G12	AB+AE+AG+BD+BF+ CD+CE+CF+DH	G44	AB+AC+AD+BE+BF+ CE+CF+DG+GH
G13	AB+AE+AG+BC+BH+ CD+CF+DE+DF	G45	AD+AE+AF+BC+BE+ BG+CF+CG+DH
G14	AB+AE+AG+BD+BH+ CE+CF+DE+DF	G46	AC+AD+AE+BC+BE+ BF+CF+DG+GH
G15	AB+AE+AG+BC+BD+ CD+CF+DH+EF	G47	AB+AC+AD+BE+BF+ CF+CG+EG+DH
G16	AB+AC+AG+BC+BD+ CH+DE+DF+EF	G48	AB+AD+AE+BC+BF+ CE+CG+FG+DH
G17	AB+AC+AG+BD+BE+ CD+CF+DH+EF	G49	AB+AD+AE+BC+BF+ CF+CG+EG+DH
G18	AB+AC+AG+BD+BH+ CD+CE+DF+EF	G50	AB+AD+AE+BC+BE+ CF+CG+FG+DH
G19	AB+AE+AG+BC+BD+ CD+CF+DE+FH	G51	AB+AC+AD+BC+BE+ CE+DF+FG+GH
G20	AB+AE+AG+BC+BD+ CD+CF+DF+EH	G52	AB+AC+AD+BC+BE+ CF+DG+EF+GH
G21	AB+AC+AG+BC+BD+ CE+DE+DF+FH	G53	AB+AC+AD+BC+BE+ CF+EG+FG+DH
G22	AB+AC+AG+BD+BE+ CD+CF+DF+EH	G54	AC+AD+AE+BC+BD+ BF+EG+FH+GH
G23	AB+AC+AG+BD+BE+ CD+CE+DF+FH	G55	AC+AD+AE+BC+BF+ BG+DH+EH+FG
G24	AB+AC+AG+BC+BD+ CD+DE+EF+FH	G56	AC+AD+AE+BC+BF+ BG+DH+EG+FH
G25	AB+AC+AE+BC+BD+ CD+DF+EG+FH	G57	AB+AC+AD+BC+BE+ DH+EF+FG+GH
G26	AD+AE+AH+BC+BD+ BE+CF+CG+FG	G58	AB+AC+AD+BE+BF+ CG+DG+EH+FH
G27	AD+AE+AH+BD+BF+ BG+CE+CF+CG	G59	AB+AC+AD+BE+BF+ CG+EG+DH+FH
G28	AD+AE+AH+BC+BD+ BF+CE+CG+FG	G60	AC+AD+AE+BF+BG+ BH+CG+DH+EF
G29	AD+AE+AH+BC+BD+ BF+CF+CG+EG	G61	AC+AD+AE+BF+BG+ BH+CE+DG+FH
G30	AB+AD+AH+BE+BF+ CE+CF+CG+FG	G62	AB+AC+AD+BE+BF+ CG+DH+EF+GH
G31	AB+AD+AH+BE+BF+ CD+CF+CG+EG	G63	AB+AC+AD+BE+BG+ CF+DG+EH+FH
G32	AB+AD+AH+BD+BE+ CE+CF+CG+FG	—	——

表1

图2

图3

图4

图5

表2

参考文献 26

[1]	ZHANG Lu, XU Yanhong, ZHANG Hao, et al. A Safe Cloud Storage Solution Based on Secret Sharing[J]. Netinfo Security, 2013, 13(4): 67-69.
	张璐, 徐燕红, 张浩, 等. 基于秘密共享的安全云存储方案[J]. 信息网络安全, 2013, 13(4):67-69.
[2]	TANG Chunming. Leakproof Secret Sharing Protocols with Applications to Group Identication Scheme[J]. Scientia Sinica(Informationis), 2012, 42(5): 634-647.
	唐春明. 防泄露的秘密共享方案及其在群身份认证协议中的应用[J]. 中国科学:信息科学, 2012, 42(5): 634-647.
[3]	ZHANG Yaze. Research on the Application of Image Secret Sharing Technology in Information Protection[D]. Xi’an: Xi’an University of Technology, 2020.
	张亚泽. 图像秘密共享技术在信息保护中的应用研究[D]. 西安: 西安理工大学, 2020.
[4]	ZHANG Benhui, XIE Xiaojuan, TANG Yuansheng. Fair Secret Sharing Scheme with Unconditional Security[J]. Journal of Cryptologic Research, 2017, 4(6): 537-544.
	张本慧, 解晓娟, 唐元生. 无条件安全的公平秘密共享方案[J]. 密码学报, 2017, 4(6): 537-544.
[5]	LIU Mulan, ZHANG Zhifang. Secret Sharing Schemes and Secure Multiparty Computation[M]. Beijing: Publishing House of Electronics Industry, 2008.
	刘木兰, 张志芳. 密钥共享体制和安全多方计算[M]. 北京: 电子工业出版社, 2008.
[6]	SHAMIR A. How to Share a Secret[J]. Communications of the ACM, 1979, 22(11): 612-613. doi: 10.1145/359168.359176 URL
[7]	BLAKLEY G. Safeguarding Cryptographic Keys[C]// IEEE. Proceedings of the National Conference. New York: IEEE, 1979: 313-317.
[8]	STINSON D R. Cryptography: Theory and Practice[M]. 3rd Editon. Translated by FENG Dengguo. Beijing: Electronic Publishing House, 2009.
	斯廷森. 密码学原理与实践[M]. 3版.冯登国,译. 北京: 电子出版社, 2009.
[9]	RONG Huigui, MO Jinxia, CHANG Bingguo, et al. Key Distribution and Recovery Algorithm Based on Shamie’s Secret Sharing[J]. Journal on Communications, 2015, 36(3): 64-73. doi: 10.1111/j.1460-2466.1986.tb01438.x URL
	荣辉桂, 莫进侠, 常炳国, 等. 基于Shamir 秘密共享的密钥分发与恢复算法[J]. 通信学报, 2015, 36(3):64-73.
[10]	SONG Yun, LI Zhihui, LI Yongming. Secret Sharing Schemes Based on Minimal Linear Codes[J]. Acta Electronica Sinica, 2013, 41(2): 220-226.
	宋云, 李志慧, 李永明. 基于极小线性码上的秘密共享方案[J]. 电子学报, 2013, 41(2): 220-226.
[11]	LIU Chengji, LI Zhihui, SI Mengmeng, et al. Quantum-Secret-Sharing Scheme Based on Local Distinguishability of Orthogonal Six-Qudit Entangled States[J]. Netinfo Security, 2018, 18(4): 56-64.
	刘成基, 李志慧, 司萌萌, 等. 基于局域区分的六粒子正交纠缠态的量子秘密共享方案[J]. 信息网络安全, 2018, 18(4): 56-64.
[12]	LIU Xiaofen, CHEN Xiaofeng, LIAN Guiren, et al. Authenticated Multiparty Quantum Secret Sharing Protocol with d-level Single Particle[J]. Netinfo Security, 2020, 20(3): 51-55.
	刘晓芬, 陈晓峰, 连桂仁, 等. 基于d级单粒子的可认证多方量子秘密共享协议[J]. 信息网络安全, 2020, 20(3):51-55.
[13]	FEI Li, CHEN Miao, CHEN Sijing, et al. Research on the Application of Quantum Key Distribution Technology on Offshore Platform[J]. Ship Science and Technology, 2020, 42(3): 139-143.
	费礼, 陈苗, 陈思井, 等. 海上平台量子密钥分发技术应用研究[J]. 舰船科学技术, 2020, 42(3): 139-143.
[14]	CHEN Jiupeng, ZHANG Chi, LIU Yang, et al. Sending-or-not-Sending with Independent Lasers: Secure Twin-Field Quantum Key Distribution over 509 km[EB/OL]. (2020-03-16)[2021-12-15]. http://med.wanfangdata.com.cn/Paper/Detail/PeriodicalPaper_PM32142314 .
[15]	PENG Chengzhi, PAN Jianwei. Quantum Science Experimental Satellite-“Micius”[J]. Bulletin of Chinese Academy of Sciences, 2016, 31(9): 1096-1104.
	彭承志, 潘建伟. 量子科学实验卫星-“墨子号”[J]. 中国科学院院刊, 2016, 31(9): 1096-1104.
[16]	LIU Lu, LI Zhihui, LU Dianjun, et al. Quantum Secret Sharing Scheme Based on Linear Codes[J]. Netinfo Security, 2021, 21(8): 62-69.
	刘璐, 李志慧, 芦殿军, 等. 基于线性码的量子秘密共享方案[J]. 信息网络安全, 2021, 21(8):62-69.
[17]	LI Zhihui, BAI Haiyan, BAI Chenming. Threshold Quantum Secret Sharing Scheme Based on Quantum Circuit[J]. Journal of Wuhan University Natural Science Edition, 2019, 65(2): 200-206.
	李志慧, 白海艳, 白晨明. 基于量子电路的门限量子秘密共享方案[J]. 武汉大学学报(理学版), 2019, 65(2):200-206.
[18]	ZHI Danli, LI Zhihui, HAN Zhaowei, et al. Verifiable Quantum Secret Sharing Based on a Single Qudit[J]. International Journal of Theoretical Physics, 2020, 59(12): 3672-3684. doi: 10.1007/s10773-020-04599-7 URL
[19]	DOU Zhao. Research on the Design of a New Quantum Secret Sharing Protocol[D]. Beijing: Beijing University of Posts and Telecommunications, 2019.
	窦钊. 新型量子秘密共享协议设计的研究[D]. 北京: 北京邮电大学, 2019.
[20]	DIJK M V. On the Information Rate of Perfect Secret Sharing Schemes[J]. Designs Codes & Cryptography, 1995, 6(2): 143-169.
[21]	GHARAHI M, DEHKORDI M H. The Complexity of the Graph Access Structures on Six Participants[J]. Designs Codes & Cryptography, 2013, 67(2): 169-173.
[22]	MASSOUD H D, ALI S. The Complexity of the Connected Graph Access Structure on Seven Participants[J]. Journal of Mathematical Cryptology, 2017, 11(1): 25-35. doi: 10.1515/jmc-2016-0017 URL
[23]	SONG Yun, LI Zhihui, WANG Weicong. The Information Rate of Secret Sharing Schemes on Seven Participants by Connected Graphs[M]. Berlin: Springer, 2012.
[24]	WANG Weicong, LI Zhihui, SONG Yun. The Optimal Information Rate of Perfect Secret Sharing Schemes[C]// IEEE. 2011 International Conference on Business Management and Electronic Information. New York: IEEE, 2011: 207-212.
[25]	SONG Yun, LI Zhihui. Information Rate of a Type of Access Structures Based on Graphs on Eight Participants Computer Engineering and Applications[J]. Computer Engineering and Applications, 2012, 48(14): 112-116.
	宋云, 李志慧. 参与者人数为八的一类图存取结构的信息率[J]. 计算机工程与应用, 2012, 48(14):112-116.
[26]	CHEN Zhongbiao. Isomorphism Determination of Undirected Graph Based on Incidence Point Degree Matrix[J]. Wireless Internet Technology, 2016(7): 77-78.
	陈中标. 基于关联点度矩阵的无向图同构判定[J]. 无线互联科技, 2016(7): 77-78.

存取结构名称	最优信息率	存取结构名称	最优信息率	存取结构名称	最优信息率	存取结构名称	最优信息率
G1	3/5	G17	1/2~3/5	G33	4/7~3/5	G49	4/7~3/5
G2	1/2~3/5	G18	1/2~3/5	G34	2/3	G50	4/7~3/5
G3	1/2~3/5	G19	1/2~3/5	G35	3/5	G51	2/3
G4	3/5	G20	1/2~3/5	G36	4/7~3/5	G52	1/2~3/5
G5	2/3	G21	3/5	G37	1/2~3/5	G53	1/2~3/5
G6	4/7~3/5	G22	1/2~3/5	G38	3/5	G54	2/3
G7	3/5	G23	1/2~3/5	G39	3/5	G55	2/3
G8	5/9~3/5	G24	1/2~3/5	G40	1/2~3/5	G56	3/5
G9	4/7~3/5	G25	3/5~2/3	G41	3/5	G57	3/5
G10	1/2~3/5	G26	3/5~2/3	G42	3/5	G58	2/3
G11	5/9~3/5	G27	2/3	G43	3/5	G59	3/5
G12	1/2~3/5	G28	3/5~2/3	G44	2/3	G60	3/5
G13	1/2~3/5	G29	3/5~2/3	G45	3/5	G61	2/3
G14	1/2~3/5	G30	4/7~3/5	G46	3/5	G62	3/5
G15	1/2~3/5	G31	4/7~3/5	G47	1/2~3/5	G63	3/5
G16	1/2~3/5	G32	3/5	G48	3/5	——	——