基于Shamir秘密共享的密钥分发与恢复算法

doi:10.11959/j.issn.1000-436x.2015083

通信学报 ›› 2015, Vol. 36 ›› Issue (3): 265-274.doi: 10.11959/j.issn.1000-436x.2015083

基于Shamir秘密共享的密钥分发与恢复算法

荣辉桂¹,莫进侠¹,常炳国¹,孙光²,龙飞³

¹ 湖南大学信息科学与工程学院，湖南长沙 410082
² 湖南财政经济学院信息管理系，湖南长沙 410205
³ 长沙大学经济管理系，湖南长沙 410003

出版日期:2015-03-25 发布日期:2017-06-21
基金资助:
国家自然科学基金资助项目;国家科技支撑计划基金资助项目;科技部创新基金资助项目;湖南重点建设学科基金资助项目；湖南大学“青年教师成长计划”基金资助项目

Key distribution and recovery algorithm based on Shamir's secret sharing

Hui-gui RONG¹,Jin-xia MO¹,Bing-guo CHANG¹,Guang SUN²,Fei LONG³

¹ College of Computer Science and Engineering, Hunan University, Changsha 410082, China
² Department of Information Management, Hunan University of Finance and Economics, Changsha 410205, China
³ Department of Economics and Management, Changsha University, Changsha 410003, China

Online:2015-03-25 Published:2017-06-21
Supported by:
The National Natural Science Foundation of China;The National Key Technology Support Program;The Innovation Foundation of Science and Technology Ministry;The Construct Program of the Key Discipline in Hunan; The Young Teachers Development Plan of Hunan University

摘要/Abstract

摘要：

在经典的Shamir秘密共享方案中，秘密分发者把秘密s分为n个影子秘密并分发给持有者；其中任意不少于t个影子秘密均能恢复秘密s，少于t个影子秘密则得不到秘密s的任何信息。现实的秘密恢复过程中可能存在超过t个参与者的情形。因此，在Shamir的秘密共享方案基础上讨论此种情形下秘密共享问题，通过引入影子秘密的线性组合——拉格朗日因子来恢复秘密，并进一步将其扩展为一个多秘密共享方案。理论分析与仿真实验表明：改进算法在同样复杂度条件下既保证影子秘密的安全，又能阻止欺骗者得到秘密，提高了整体安全性。

关键词: 秘密共享, 密钥分发, 拉格朗日因子, 密钥恢复

Abstract:

In Shamir's secret sharing scheme, the dealer divided the secret s into n shadows and distributed it to share-holders in such a way that any t or more than t shadows can recover this secret, while fewer than t shadows cannot obtain any information about the secret s. During the actual secret recovery process, there exist other cases with more than t par-ticipants. The case of secret sharing problem was discussed based on Shamir's secret sharing scheme and reconstructs the secret by introducing a linear combination of shadows—Lagrange factor. Then, the improved algorithm of key distribu-tion and recovery was proposed and extended to a multi-secret sharing scheme. Theoretical analysis and simulation show that the improved scheme improves its security under the same conditions of complexity.

Key words: secret sharing, key distribution, Lagrange factor, key recovery

荣辉桂,莫进侠,常炳国,孙光,龙飞. 基于Shamir秘密共享的密钥分发与恢复算法[J]. 通信学报, 2015, 36(3): 265-274.

Hui-gui RONG,Jin-xia MO,Bing-guo CHANG,Guang SUN,Fei LONG. Key distribution and recovery algorithm based on Shamir's secret sharing[J]. Journal on Communications, 2015, 36(3): 265-274.

图/表 9

图1

表1

表2

图2

图3

图4

图5

图6

图7

参考文献 25

[1]	SHAMIR A . How to share a secret[J]. Communications of the ACM, 1979,22(11):612-613.
[2]	BLAKLEY G R . Safeguarding cryptographic keys[A]. Managing Requirements Knowledge, International Workshop[C].IEEE Computer Society, 1979.313-313.
[3]	肖清华．秘密共享及相关应用研究[D]．杭州：浙江大学， 2005. XIAO Q H . Research on Secret Sharing and Its Related Applications[D]. Hangzhou: Zhejiang University, 2005.
[4]	CHOR B , GOLDWASSER S , MICALI S , et al. Verifiable secret shar-ing and achieving simultaneity in the presence of faults[A]. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science[C]. 1985.383-395.
[5]	KAYA K , SEL?UK A A . A verifiable secret sharing scheme based on the Chinese remainder theorem[A]. Progress in Cryptology- IN-DOCRYPT 2008[C]. Springer Berlin Heidelberg, 2008.414-425.
[6]	LU Q , XIONG Y , HUANG W , et al. A distributed ECC-DSS authenti-cation scheme based on CRT-VSS and trusted computing in MANET[A]. Trust, Security and Privacy in Computing and Communications (TrustCom), 2012 IEEE 11th International Conference[C]. 2012.656-665.
[7]	KAYA K , SEL?UK A A . A verifiable secret sharing scheme based on the chinese remainder theorem[A]. Progress in Cryptology-INDOCRYPT 2008[C]. Springer Berlin Heidelberg, 2008.414-425.
[8]	HARN L , FUYOU M , CHANG C C . Verifiable secret sharing based on the Chinese remainder theorem[J]. Security and Communication Networks, 2014,7(6):950-957.
[9]	ZHANG L , GUO F , LIU S , et al. A verifiable multi-secret sharing scheme based on LUC cryptosystem[A]. Consumer Electronics, Communications and Networks (CECNet), 2011 International Conference on IEEE[C]. 2011.2905-2908.
[10]	HU C , LIAO X , CHENG X . Verifiable multi-secret sharing based on LFSR sequences[J]. Theoretical Computer Science, 2012,445:52-62.
[11]	LAIH C S , HARN L , LEE J Y , et al. Dynamic threshold scheme based on the definition of cross-product in an n-dimensional linear space[A]. Advances in Cryptology—CRYPTO'89 Proceedings[C]. Springer New York, 1990.286-298.
[12]	李大伟，杨庚．基于单向散列链的可更新(t,n)门限秘密共享方案[J]．通信学报， 2010,31(7):128-135. LI D W , YANG G . Renewable (t, n) threshold secret sharing scheme based on one-way hash chain[J]. Journal on Communications, 2010,31(7):128-135.
[13]	LIN H Y , YEH Y S . Dynamic multi-secret sharing scheme[J]. International Journal of Contemporary Mathematical Sciences, 2008,3(1):37-42.
[14]	QU J , ZOU L , ZHANG J . A practical dynamic multi-secret sharing scheme[A]. Information Theory and Information Security (ICITIS), 2010 IEEE International Conference[C]. 2010.629-631.
[15]	TADAYON M H , KHANMOHAMMADI H , ARABI S . An attack on a dynamic multi-secret sharing scheme and enhancing its security[A]. Electrical Engineering (ICEE), 2013 21st Iranian Conference[C]. 2013.1-5.
[16]	贾秀芹，赖红．抗欺诈的动态(t, n)门限秘密共享方案[J]．计算机工程， 2011,37(4):152-154. JIA X Q , LAI H . Anti-cheat and dynamic (t, n) threshold secret sharing scheme[J]. Computer Engineering, 2011,37(4):152-154.
[17]	ESLAMI Z , RAD S K . A new verifiable multi-secret sharing scheme based on bilinear maps[J]. Wireless Personal Communications, 2012,63(2):459-467.
[18]	HERZBERG A , JARECKI S , KRAWCZYK H , et al. Proactive secret sharing or: How to cope with perpetual leakage[A]. Advances in Cryptology—CRYPT0'95[C].Springer Berlin Heidelberg, 1995.339-352.
[19]	SUN H , ZHENG X , YU Y . A proactive secret sharing scheme based on elliptic curve cryptography Education Technology and Computer Science[A]. First International Workshop on IEEE[C]. 2009.666-669.
[20]	WANG X . A novel adaptive proactive secret sharing without a trusted party[J]. IACR Cryptology ePrint Archive, 2011,241.
[21]	范畅，茹鹏．一种基于 ECC 的动态秘密共享方案[J]．计算机仿真， 2012,29(12):131-134. FAN C , RU P . Proactive secret sharing scheme based on ECC[J]. Computer Simulation, 2012,29(12):131-134.
[22]	NIKOV V , NIKOVA S . On a relation between verifiable secret sharing schemes and a class of error-correcting codes[A]. Coding and Cryp-tography[C].Springer Berlin Heidelberg, 2006.275-290.
[23]	OGATA W , KUROSAWA K , STINSON D R . Optimum secret sharing scheme secure against cheating[J]. SIAM Journal on Discrete Mathematics, 2006,20(1):79-95.
[24]	JHANWAR M P , SAFAVI-NAINI R . On the share efficiency of robust secret sharing and secret sharing with cheating detection[A]. Progress in Cryptology-INDOCRYPT 2013[C]. Springer International Publishing, 2013.179-196.
[25]	BENALOH J C . Secret sharing homomorphisms: Keeping shares of a secret secret[A]. Advances in Cryptology—CRYPTO'86[C].Springer Berlin Heidelberg, 1987.251-260.

操作	秘密分发	秘密恢复
拉格朗日插值	0	kn lg² n
构造插值多项式	nk²+kt+k	0
累加运算	2n+2k	j

方案	预防欺骗	复杂度	安全性
文献[1]( Shamir秘密共享算法)	否	O(nlg²n)	较低
文献[12](动态秘密共享算法)	能	O(nlg²n)	条件安全
文献[20](主动秘密共享算法)	能	O(n³)	条件安全
本文提出的Shamir改进算法	能	O(nlg²n)	较高

基于Shamir秘密共享的密钥分发与恢复算法

Key distribution and recovery algorithm based on Shamir's secret sharing

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 25

相关文章 15

Metrics

推荐阅读 0

[1]	熊金波, 周永洁, 毕仁万, 万良, 田有亮. 边缘协同的轻量级隐私保护分类框架[J]. 通信学报, 2022, 43(1): 127-137.
[2]	刘海, 田有亮, 唐莹, Jianbing Ni, 马建峰. 面向理性用户的秘密重构设计模型[J]. 通信学报, 2021, 42(11): 54-65.
[3]	熊金波,毕仁万,陈前昕,刘西蒙. 边缘协作的轻量级安全区域建议网络[J]. 通信学报, 2020, 41(10): 188-201.
[4]	王华,赵永利. 量子密钥分发城域光组网技术前瞻[J]. 通信学报, 2019, 40(9): 168-174.
[5]	徐渊,杨超,杨力. 基于移动端协助的远程用户单一口令认证方法[J]. 通信学报, 2019, 40(2): 174-187.
[6]	张艳硕,李文敬,陈雷,毕伟,杨涛. 基于特征值的可验证特殊门限秘密共享方案[J]. 通信学报, 2018, 39(8): 169-175.
[7]	张恩,裴瑶瑶,杜蛟. 基于RLWE的密文策略属性代理重加密[J]. 通信学报, 2018, 39(11): 129-137.
[8]	梁建武,刘晓书,程资. 基于图态和中国剩余定理的量子秘密共享方案[J]. 通信学报, 2018, 39(10): 72-78.
[9]	纪祥敏,赵波,刘金会,贾建卫,张焕国,向騻. 基于对称矩阵分解的无线传感网密钥恢复攻击[J]. 通信学报, 2018, 39(10): 87-96.
[10]	李维,赵凡,张二虎,任鹏. 基于SATD的H.265/HEVC拉格朗日因子选择算法[J]. 通信学报, 2017, 38(6): 68-74.
[11]	张恩,耿魁,金伟,李勇俊,孙韵清,李凤华. 抗隐蔽敌手的云外包秘密共享方案[J]. 通信学报, 2017, 38(5): 57-65.
[12]	伍祈应,马建峰,苗银宾,张俊伟,沈丽敏. 多数据拥有者认证的密文检索方案[J]. 通信学报, 2017, 38(11): 161-170.
[13]	刘绍婷,王晓凯,郭大波. 连续变量量子密钥分发数据协调加速运算的GPU实现[J]. 通信学报, 2017, 38(11): 171-177.
[14]	田有亮,王雪梅,刘琳芳. 基于马尔可夫决策的理性秘密共享方案[J]. 通信学报, 2015, 36(9): 222-229.
[15]	李滨. 基于向量空间不同访问群体的门限方案[J]. 通信学报, 2015, 36(11): 67-72.