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

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

Abstract

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

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.

Figures/Tables 9

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

Metrics

Recommended 0

No Suggested Reading articles found!

操作	秘密分发	秘密恢复
拉格朗日插值	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)	较高

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 25

Related Articles 15

Metrics

Recommended 0

[1]	Jinbo XIONG, Yongjie ZHOU, Renwan BI, Liang WAN, Youliang TIAN. Towards edge-collaborative, lightweight and privacy-preserving classification framework [J]. Journal on Communications, 2022, 43(1): 127-137.
[2]	Hai LIU, Youliang TIAN, Ying TANG, Jianbing Ni, Jianfeng MA. Design models of secret reconstruction towards rational users [J]. Journal on Communications, 2021, 42(11): 54-65.
[3]	Jinbo XIONG,Renwan BI,Qianxin CHEN,Ximeng LIU. Towards edge-collaborative,lightweight and secure region proposal network [J]. Journal on Communications, 2020, 41(10): 188-201.
[4]	Hua WANG,Yongli ZHAO. Overview of quantum key distribution metropolitan optical networking technology [J]. Journal on Communications, 2019, 40(9): 168-174.
[5]	Yuan XU,Chao YANG,Li YANG. Single password authentication method for remote user based on mobile terminal assistance [J]. Journal on Communications, 2019, 40(2): 174-187.
[6]	Yanshuo ZHANG,Wenjing LI,Lei CHEN,Wei BI,Tao YANG. Verifiable special threshold secret sharing scheme based on eigenvalue [J]. Journal on Communications, 2018, 39(8): 169-175.
[7]	Xin LIU,Qiuliang XU,Bin ZHANG,Bo ZHANG. k-times attribute-based authentication scheme using direct anonymous attestation [J]. Journal on Communications, 2018, 39(12): 113-133.
[8]	Fang QI,Yanmei LI,Zhe TANG. Revocable and traceable key-policy attribute-based encryption scheme [J]. Journal on Communications, 2018, 39(11): 63-69.
[9]	En ZHANG,Yaoyao PEI,Jiao DU. RLWE-based ciphertext-policy attribute proxy re-encryption [J]. Journal on Communications, 2018, 39(11): 129-137.
[10]	Jianwu LIANG,Xiaoshu LIU,Zi CHENG. Quantum secret sharing with graph states based on Chinese remainder theorem [J]. Journal on Communications, 2018, 39(10): 72-78.
[11]	Xiangmin JI,Bo ZHAO,Jinhui LIU,Jianwei JIA,Huanguo ZHANG,Shuang XIANG. WSN key recovery attack based on symmetric matrix decomposition [J]. Journal on Communications, 2018, 39(10): 87-96.
[12]	En ZHANG,Kui GENG,Wei JIN,Yong-jun LI,Yun-qing SUN,Feng-hua LI. Cloud outsourcing secret sharing scheme against covert adversaries [J]. Journal on Communications, 2017, 38(5): 57-65.
[13]	Shao-ting LIU,Xiao-kai WANG,Da-bo GUO. Accelerated computational implementation of reconciliation for continuous variable quantum key distribution on GPU [J]. Journal on Communications, 2017, 38(11): 171-177.
[14]	Ying-di DONG,Jin-ye PENG,Xiao-bo ZHANG,Zhen-long ZHANG. Quantum identity authentication scheme based on measurement-device-independent quantum key distribution protocol [J]. Journal on Communications, 2016, 37(2): 152-157.
[15]	You-liang TIAN,Xue-mei WANG,Lin-fang LIU. Rational secret sharing scheme based on Markov decision [J]. Journal on Communications, 2015, 36(9): 222-229.