加权门限秘密共享研究
|
摘要
秘密共享是现代密码学的一个重要分支,是保障信息安全和数据保密的重要手段之一。利用秘密共享保存和管理秘密信息,一方面可以防止权力过于集中而被滥用,分散了责任;另一方面可以保证数据的安全性和完整性。秘密共享的研究不仅具有重要的理论意义,而且具有广泛的应用前景。
本文介绍了秘密共享的研究背景、现状及相关数学工具,探讨了门限秘密共享研究的若干研究方向,分析了几种经典的门限秘密共享方案,重点研究了加权门限秘密共享。针对已有的加权门限秘密共享方案存在的问题,提出了一个新的加权门限秘密共享方案。该方案具有以下特点:
(1)允许参与者具有不同的权重值,只有当参与者集合的权重之和大于或等于门限值时,才能恢复秘密;反之,则得不到关于秘密的任何信息。
(2)方案中引入Mignotte列,并对其进行扩展,无论参与者的权重大小如何,只需要保存一个秘密份额。从而减少了秘密信息的传输量,同时有助于提高秘密信息的安全性。
(3)无需设定额外的辅助数据(如间接秘密等),从而简化了方案的结构,降低了计算复杂度。
最后,本文介绍了大素数的生成和检测方法等算法及实现,利用VC++ 6.0实现了该方案的原型系统,并分析了系统的各个模块及其功能。实验结果表明:本文所提出的方案是正确和可行的,具备良好的安全性和应用性。
Secret sharing is an important branch of modern cryptography. It is a significant way to protecting information security and data encryption. Secret sharing is used for saving secret information. It prevents excessive concentration of power being abused and can disperse responsibility. On the other hand, it guarantees the security and integrity of data. Therefore, research of secret sharing has important theoretical significance and broad application prospects.
Firstly, the backgrounds, status and related Mathematical tools of secret sharing are presented in the dissertation. In succession, several current research areas of threshold secret sharing are discussed. Some classical threshold secret sharing schemes are analyzed. Then, the features of current weighted threshold secret sharing are researched. A new weighted threshold secret sharing scheme is proposed. There are some features in the scheme as follows:
(1) The participants are allowed to own different weight value. Only when the total weight value of the participants is greater or equal to the threshold value, the participants could recover the secret, otherwise they can do nothing.
(2) Mignotte sequence is introduced and extended in the scheme. No matter how much the weight value of the participant is, each participant only needs to save one share. It can greatly reduce the transmission quantity of confidential information and enhance the security of information.
(3) No additional data is required in the scheme, which simplifies the structure and reduces the computational difficulty.
Finally, the generation and realization algorithms of the large prime number are introduced in the dissertation. A prototype system is implemented by using VC++6.0. The functions of component of the prototype system are detailed analyzed. The experimental results show that the scheme is correct and feasible and has good security and applicability.
本文介绍了秘密共享的研究背景、现状及相关数学工具,探讨了门限秘密共享研究的若干研究方向,分析了几种经典的门限秘密共享方案,重点研究了加权门限秘密共享。针对已有的加权门限秘密共享方案存在的问题,提出了一个新的加权门限秘密共享方案。该方案具有以下特点:
(1)允许参与者具有不同的权重值,只有当参与者集合的权重之和大于或等于门限值时,才能恢复秘密;反之,则得不到关于秘密的任何信息。
(2)方案中引入Mignotte列,并对其进行扩展,无论参与者的权重大小如何,只需要保存一个秘密份额。从而减少了秘密信息的传输量,同时有助于提高秘密信息的安全性。
(3)无需设定额外的辅助数据(如间接秘密等),从而简化了方案的结构,降低了计算复杂度。
最后,本文介绍了大素数的生成和检测方法等算法及实现,利用VC++ 6.0实现了该方案的原型系统,并分析了系统的各个模块及其功能。实验结果表明:本文所提出的方案是正确和可行的,具备良好的安全性和应用性。
Secret sharing is an important branch of modern cryptography. It is a significant way to protecting information security and data encryption. Secret sharing is used for saving secret information. It prevents excessive concentration of power being abused and can disperse responsibility. On the other hand, it guarantees the security and integrity of data. Therefore, research of secret sharing has important theoretical significance and broad application prospects.
Firstly, the backgrounds, status and related Mathematical tools of secret sharing are presented in the dissertation. In succession, several current research areas of threshold secret sharing are discussed. Some classical threshold secret sharing schemes are analyzed. Then, the features of current weighted threshold secret sharing are researched. A new weighted threshold secret sharing scheme is proposed. There are some features in the scheme as follows:
(1) The participants are allowed to own different weight value. Only when the total weight value of the participants is greater or equal to the threshold value, the participants could recover the secret, otherwise they can do nothing.
(2) Mignotte sequence is introduced and extended in the scheme. No matter how much the weight value of the participant is, each participant only needs to save one share. It can greatly reduce the transmission quantity of confidential information and enhance the security of information.
(3) No additional data is required in the scheme, which simplifies the structure and reduces the computational difficulty.
Finally, the generation and realization algorithms of the large prime number are introduced in the dissertation. A prototype system is implemented by using VC++6.0. The functions of component of the prototype system are detailed analyzed. The experimental results show that the scheme is correct and feasible and has good security and applicability.
引文
[1] Shamir, A. How to share a secret[C]. Communications of the ACM 22 ,1979. 612–613.
[2] Blakley G. R. Safeguarding cryptographic keys. National Computer Conference[J].American Federation of Information Processing Societies Proceedings 48,1979.313–317.
[3] Asmuth C A and J Bloom. A modular approach to key safeguarding[J]. IEEE Transactions on Information Theory IT-29 ,1983,208–210.
[4] E D Karnin, J W Greene and M E Hellman. On secret sharing systems[J]. IEEE Transactions on Information Theory,1983, 9(1):35–41.
[5] B Chor, S Goldwasser, S Micali and B Awerbuch. Verifiable secretsharing and achieving simultaneity in the presence of faults[C]. In Proceedings of the 26th IEEE Symposium on the Foundations of Computer Science,1985, 383–395.
[6] P Feldman. A practical scheme for non-interactive verifiable secret sharing[C]. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, 1987, 427–437.
[7] M Tompa and H Woll. How to share a secret with cheaters[J]. Journal of Cryptology, 1988,1(2):133–138.
[8]Toshinori Akraki,Satoshi Obana.Flaws in Some Secret Sharing Schems Against Cheating[C].ACISP 2007,LNCS 4586.2007,122-132.
[9]C. Blundo, A. De Santis, L Gargano, and U Vaccaro. On the information rate of secret sharing schemes[J]. Theoretical Computer Science, 1996,154 (2):283–306.
[10]Hwang Renjun, Chang Chinchen.An on-line secret sharing scheme for multi-secret[J]. Computer Communications, 1998,21:1170-1176.
[11]HY Chien,JK Jan YM Tseng.A practical (t,n) multi-secret sharing scheme[J]. IEICE Transactions on Fundamentals,2000,E83-A(12):2762-2765.
[12]Yang Chouchen,Chang Tingyi,Hwang MinShiang.A (t,n) multi-secret sharing scheme[J].Applied Mathematics and Comoutation,2004,151(2):483-490.
[13]Pang Liao-Jun, Wang Yu-Min. A new (t,n) multi-secret sharing scheme based on Shamir's secret sharing [J]. Applied Mathematics and Computation, 2005,167(2):840-848.
[14] P. Morillo, C. Padr′o, G. S′aez, and J. L. Villar. Weighted threshold secret sharing schemes[J]. Information Processing Letters, 1999,70(5):211–216.
[15]Yanshuo ZHANG,Zhuojun LIU.Dynamic and verifiable secret sharing amongweighted participants[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY. 2007,20(4):481-485.
[16]S Iftene, M Grindei. Weighted Threshold RSA Based on the Chinese Remainder Theorem[J]. In T Jebelean, V Negru, D Petcu, and D Zaharie, editors, Proceedings of the 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, September 2007, 175-181.
[17]M.Mignotte. How to share a secret. In T. Beth, editor, Cryptography- Proceedings of the Workshop on Cryptography[C], Burg Feuerstein, 1982,volume 149 of Lecture Notes in Computer Science, 1983. 371–375.
[18]M Ito, A Saito, and T. Nishizeki. Secret sharing scheme realizing general access structure[C]. In Proceedings of the IEEE Global Telecommunications Conference, Globecom’87, 1987. 99–102.
[19] M. van Dijk. A linear construction of secret sharing schemes[C]. Designs,Codes and Cryptography, 1997,12(2):161–201.
[20]Blakley G R, Kabatianski G A. Ideal perfect threshold schemes and MDS codes. Proceedings[C]. 1995 IEEE International Symposium on Information Theory, 1995.488.
[21] Brickell E F .Some ideal secret sharing schemes. in: J.-J. Quisquater and J. Vandewalle[C], editors,Advances in Cryptology - EUROCRYPT’89, Lecture Notes in Computer Science 434 (1990).468–475.
[22]斯廷森D. R.著,张文政译.密码学—理论与实践[M],国防科学技术保密通信重点实验室,1997年.
[23]阂嗣鹤,严士健.初等数论[M],第三版,高等教育出版社,2003.
[24]许春香.安全秘密共享及其应用研究.西安电子科技大学博士论文[D],2003年11月.
[25]C Park,K Kurosawa.New ELGamal Type Threshold Sinature Scheme[J]. IEEE79-A(1),1979. 86-93.
[26] J He and E Dawson. Multistage secret sharing based on one-way function[J]. Electronics Letters, 1994,30(19):1591–1592.
[27]Harn L. Efficient sharing(broadcasting) of multiple secret[J].IEEE Proceedings Computers and Digital Techniques.1995,142(3):237-240.
[28]Chan C W Chang C C.A scheme for threhold multi-secret sharing.Applied Mathematics and Computation[J].2005,166(1):1-14.
[29]Huang Dongping, Liu Duo, and Dai Yiqi. Weighted threshold secret sharing[J] .Journal of Computer Research and Development. 2007, 44(8):1378-1382.
[30]S. Iftene. A generalization of Mignotte's secret sharing scheme. In T.Jebelean, V.Negru, D.Petcu,and D.Zaharie,editors[C], Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing,Timisoara, Romania, September 2004,196–201
[31]S. Iftene and I. Boureanu. Weighted threshold secret sharing based on the Chinese remainder theorem[J].Scientific Annals of the“Al. I. Cuza”University of Ias?i, Computer Science Section, 2005,XV:161–172.
[32] Ore, O., The general Chinese remainder theorem[J].American Mathematical Monthly 59 , 1952:365–370.
[33]Ito M., Saito A., Matsumoto T.Secret sharing scheme realizing general access structure[J]. Proceedings IEEE Grobecom’87, 1987: 99-102.
[34] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signature public key cryptosystem[C]. Communications of the ACM, 1978, 21(2): 120-126.
[35]ElGamal, T. A public-key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Trans. on Information Theory, 1985, 31(4): 469-472.
[36]Lin T Y,Wu T C.(t,n)threshold verifiable multi-secret sharing scheme based on intractability and discrete logaithm modulo a composite problems[J]. IEE proc.comput.Digit.Tech,1999,146(5):264-268.
[37]Chen L,Gollmann d,Mitchell C J,Wild P.Secret sharing with reusable polynomials[J].Proceeding of ACISP'97,1997:183-189.
[38]He W H,Wu T S.Comment on Lin-Wu (t,n)threshold verifiable multi-secret sharing[J].IEE Proc.Comput.Digit.Tech,2001,3:139-148.
[39]S. Iftene, M. Grindei. Weighted Threshold RSA Based on the Chinese Remainder Theorem[J]. In T. Jebelean, V. Negru, D. Petcu, and D. Zaharie, editors, Proceedings of the 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, September 2007, 175-181.
[40] Susilo W, Safavi-Naini R, Oieprzyk J. Fail-stop threshold signature schemes based on elliptic curves[C], ACISP’99, Springer-verlag, Berlin, 1999: 103-116.
[41]C. Ding, D. Pei, and A. Salomaa. Chinese remainder theorem: applications in computing[M]. coding,cryptography.World Scientific Publishing, 1996.
[42]H M Sun , B L Chen.Weighted decomposition construction for perfect secretsharing schemes [J ].Computers and Mathematics with Applications, 2002,43 (6/7): 877–887.
[43]K H Rosen. Elementary Number Theory and Its Applications[M]. Fourth Edition,Reading,MA:Addison-Wesley,2000.
[44]T. P. Pedersen. Distributed provers verifiable secret sharing based on the discrete logarithm problem[D].PhD Thesis,Aarhus University,Computer Science Department,1992.
[45]M. Stadler. Publicly verifiable secret sharing[C]. In U. M. Maurer, editor,Advances in Cryptology - EUROCRYPT’96, volume 1070 of Lecture Notes in Computer Science,1996: 190–199.
[46]L. Harn. Comment on“Multistage secret sharing based on one-way function”[J]. Electronics Letters, 1995,31(4):262.
[2] Blakley G. R. Safeguarding cryptographic keys. National Computer Conference[J].American Federation of Information Processing Societies Proceedings 48,1979.313–317.
[3] Asmuth C A and J Bloom. A modular approach to key safeguarding[J]. IEEE Transactions on Information Theory IT-29 ,1983,208–210.
[4] E D Karnin, J W Greene and M E Hellman. On secret sharing systems[J]. IEEE Transactions on Information Theory,1983, 9(1):35–41.
[5] B Chor, S Goldwasser, S Micali and B Awerbuch. Verifiable secretsharing and achieving simultaneity in the presence of faults[C]. In Proceedings of the 26th IEEE Symposium on the Foundations of Computer Science,1985, 383–395.
[6] P Feldman. A practical scheme for non-interactive verifiable secret sharing[C]. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, 1987, 427–437.
[7] M Tompa and H Woll. How to share a secret with cheaters[J]. Journal of Cryptology, 1988,1(2):133–138.
[8]Toshinori Akraki,Satoshi Obana.Flaws in Some Secret Sharing Schems Against Cheating[C].ACISP 2007,LNCS 4586.2007,122-132.
[9]C. Blundo, A. De Santis, L Gargano, and U Vaccaro. On the information rate of secret sharing schemes[J]. Theoretical Computer Science, 1996,154 (2):283–306.
[10]Hwang Renjun, Chang Chinchen.An on-line secret sharing scheme for multi-secret[J]. Computer Communications, 1998,21:1170-1176.
[11]HY Chien,JK Jan YM Tseng.A practical (t,n) multi-secret sharing scheme[J]. IEICE Transactions on Fundamentals,2000,E83-A(12):2762-2765.
[12]Yang Chouchen,Chang Tingyi,Hwang MinShiang.A (t,n) multi-secret sharing scheme[J].Applied Mathematics and Comoutation,2004,151(2):483-490.
[13]Pang Liao-Jun, Wang Yu-Min. A new (t,n) multi-secret sharing scheme based on Shamir's secret sharing [J]. Applied Mathematics and Computation, 2005,167(2):840-848.
[14] P. Morillo, C. Padr′o, G. S′aez, and J. L. Villar. Weighted threshold secret sharing schemes[J]. Information Processing Letters, 1999,70(5):211–216.
[15]Yanshuo ZHANG,Zhuojun LIU.Dynamic and verifiable secret sharing amongweighted participants[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY. 2007,20(4):481-485.
[16]S Iftene, M Grindei. Weighted Threshold RSA Based on the Chinese Remainder Theorem[J]. In T Jebelean, V Negru, D Petcu, and D Zaharie, editors, Proceedings of the 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, September 2007, 175-181.
[17]M.Mignotte. How to share a secret. In T. Beth, editor, Cryptography- Proceedings of the Workshop on Cryptography[C], Burg Feuerstein, 1982,volume 149 of Lecture Notes in Computer Science, 1983. 371–375.
[18]M Ito, A Saito, and T. Nishizeki. Secret sharing scheme realizing general access structure[C]. In Proceedings of the IEEE Global Telecommunications Conference, Globecom’87, 1987. 99–102.
[19] M. van Dijk. A linear construction of secret sharing schemes[C]. Designs,Codes and Cryptography, 1997,12(2):161–201.
[20]Blakley G R, Kabatianski G A. Ideal perfect threshold schemes and MDS codes. Proceedings[C]. 1995 IEEE International Symposium on Information Theory, 1995.488.
[21] Brickell E F .Some ideal secret sharing schemes. in: J.-J. Quisquater and J. Vandewalle[C], editors,Advances in Cryptology - EUROCRYPT’89, Lecture Notes in Computer Science 434 (1990).468–475.
[22]斯廷森D. R.著,张文政译.密码学—理论与实践[M],国防科学技术保密通信重点实验室,1997年.
[23]阂嗣鹤,严士健.初等数论[M],第三版,高等教育出版社,2003.
[24]许春香.安全秘密共享及其应用研究.西安电子科技大学博士论文[D],2003年11月.
[25]C Park,K Kurosawa.New ELGamal Type Threshold Sinature Scheme[J]. IEEE79-A(1),1979. 86-93.
[26] J He and E Dawson. Multistage secret sharing based on one-way function[J]. Electronics Letters, 1994,30(19):1591–1592.
[27]Harn L. Efficient sharing(broadcasting) of multiple secret[J].IEEE Proceedings Computers and Digital Techniques.1995,142(3):237-240.
[28]Chan C W Chang C C.A scheme for threhold multi-secret sharing.Applied Mathematics and Computation[J].2005,166(1):1-14.
[29]Huang Dongping, Liu Duo, and Dai Yiqi. Weighted threshold secret sharing[J] .Journal of Computer Research and Development. 2007, 44(8):1378-1382.
[30]S. Iftene. A generalization of Mignotte's secret sharing scheme. In T.Jebelean, V.Negru, D.Petcu,and D.Zaharie,editors[C], Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing,Timisoara, Romania, September 2004,196–201
[31]S. Iftene and I. Boureanu. Weighted threshold secret sharing based on the Chinese remainder theorem[J].Scientific Annals of the“Al. I. Cuza”University of Ias?i, Computer Science Section, 2005,XV:161–172.
[32] Ore, O., The general Chinese remainder theorem[J].American Mathematical Monthly 59 , 1952:365–370.
[33]Ito M., Saito A., Matsumoto T.Secret sharing scheme realizing general access structure[J]. Proceedings IEEE Grobecom’87, 1987: 99-102.
[34] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signature public key cryptosystem[C]. Communications of the ACM, 1978, 21(2): 120-126.
[35]ElGamal, T. A public-key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Trans. on Information Theory, 1985, 31(4): 469-472.
[36]Lin T Y,Wu T C.(t,n)threshold verifiable multi-secret sharing scheme based on intractability and discrete logaithm modulo a composite problems[J]. IEE proc.comput.Digit.Tech,1999,146(5):264-268.
[37]Chen L,Gollmann d,Mitchell C J,Wild P.Secret sharing with reusable polynomials[J].Proceeding of ACISP'97,1997:183-189.
[38]He W H,Wu T S.Comment on Lin-Wu (t,n)threshold verifiable multi-secret sharing[J].IEE Proc.Comput.Digit.Tech,2001,3:139-148.
[39]S. Iftene, M. Grindei. Weighted Threshold RSA Based on the Chinese Remainder Theorem[J]. In T. Jebelean, V. Negru, D. Petcu, and D. Zaharie, editors, Proceedings of the 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, September 2007, 175-181.
[40] Susilo W, Safavi-Naini R, Oieprzyk J. Fail-stop threshold signature schemes based on elliptic curves[C], ACISP’99, Springer-verlag, Berlin, 1999: 103-116.
[41]C. Ding, D. Pei, and A. Salomaa. Chinese remainder theorem: applications in computing[M]. coding,cryptography.World Scientific Publishing, 1996.
[42]H M Sun , B L Chen.Weighted decomposition construction for perfect secretsharing schemes [J ].Computers and Mathematics with Applications, 2002,43 (6/7): 877–887.
[43]K H Rosen. Elementary Number Theory and Its Applications[M]. Fourth Edition,Reading,MA:Addison-Wesley,2000.
[44]T. P. Pedersen. Distributed provers verifiable secret sharing based on the discrete logarithm problem[D].PhD Thesis,Aarhus University,Computer Science Department,1992.
[45]M. Stadler. Publicly verifiable secret sharing[C]. In U. M. Maurer, editor,Advances in Cryptology - EUROCRYPT’96, volume 1070 of Lecture Notes in Computer Science,1996: 190–199.
[46]L. Harn. Comment on“Multistage secret sharing based on one-way function”[J]. Electronics Letters, 1995,31(4):262.