基于秘密仿射变换和零知识证明的多变量代理签名方案的研究
|
摘要
随着网络技术的高速发展,数字签名也在电子政务和电子商务等诸多方面得到了广泛的应用。代理签名作为数字签名中的一员,主要应用在电子选举,电子现金,电子拍卖等方面,而且根据功能的不同,又相继出现了如代理盲签名,提名代理签名,门限代理签名等不同的代理签名方案。但是这些代理签名方案大部分都是基于传统的公钥密码体制,在面对未来量子计算机的诞生时,它们将受到很严重的威胁。
为了能够面对未来量子计算机带来的危机,多变量公钥密码体制(MPKC)作为能够抵御未来基于量子计算机的攻击的候选者之一。本论文结合了多变量的性质,使用有限域上的二次多变量多项式构造代理签名体制,利用了多变量同构问题(IP),选取以Rainbow结构的多项式作为中心映射,并且基于安全性的考虑,在签名方案基础上增加了秘密仿射变换的性质,使公钥多项式并非像其在原模型当中一样为私钥的直接合成,而是隐藏部分私钥,减少攻击者获得的信息量；同时签名验证是对中间过程某结果的验证,提出了一种基于多变量签名体制的代理保护型签名方案；再根据零知识证明的方法,结合证书签名,提出了一种基于IP模式零知识证明的证书代理签名方案。
With the fast development of network, the digital signatures have wide application in electronic government affairs and electronic commercial affairs and many other affairs. Proxy Signature is one of the digital signatures. The main application of Proxy Signature is in electronic election, electronic cash and electronic auction etc. According to the different environments, people propose many types, such as proxy blind signature and nomination proxy signature threshold proxy signature etc. But most of them are based on traditional public cryptosystem. They will be vulnerable when the quantum computer is emerged in the future.
Multivariate public cryptosystem is one of the public key cryptosystem resistant to attack quantum computers. Combine with multivariate properties and the Isomorphism of Polynomials Problem which is a fundamental problem of multivariate cryptography, I propose a proxy signature scheme with the central map is chose a rainbow multivariate polynomials. In terms of the security, I combine the secret affine transformation with the signature to hidden part of the private key. Moreover, I propose a certificated-based proxy signature scheme with Zero-knowledge Proofs of Knowledge and IP scheme.
为了能够面对未来量子计算机带来的危机,多变量公钥密码体制(MPKC)作为能够抵御未来基于量子计算机的攻击的候选者之一。本论文结合了多变量的性质,使用有限域上的二次多变量多项式构造代理签名体制,利用了多变量同构问题(IP),选取以Rainbow结构的多项式作为中心映射,并且基于安全性的考虑,在签名方案基础上增加了秘密仿射变换的性质,使公钥多项式并非像其在原模型当中一样为私钥的直接合成,而是隐藏部分私钥,减少攻击者获得的信息量；同时签名验证是对中间过程某结果的验证,提出了一种基于多变量签名体制的代理保护型签名方案；再根据零知识证明的方法,结合证书签名,提出了一种基于IP模式零知识证明的证书代理签名方案。
With the fast development of network, the digital signatures have wide application in electronic government affairs and electronic commercial affairs and many other affairs. Proxy Signature is one of the digital signatures. The main application of Proxy Signature is in electronic election, electronic cash and electronic auction etc. According to the different environments, people propose many types, such as proxy blind signature and nomination proxy signature threshold proxy signature etc. But most of them are based on traditional public cryptosystem. They will be vulnerable when the quantum computer is emerged in the future.
Multivariate public cryptosystem is one of the public key cryptosystem resistant to attack quantum computers. Combine with multivariate properties and the Isomorphism of Polynomials Problem which is a fundamental problem of multivariate cryptography, I propose a proxy signature scheme with the central map is chose a rainbow multivariate polynomials. In terms of the security, I combine the secret affine transformation with the signature to hidden part of the private key. Moreover, I propose a certificated-based proxy signature scheme with Zero-knowledge Proofs of Knowledge and IP scheme.
引文
[1]Shor. P.Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. SIAM Journal on Computing,1997,26(5):1484-1509.
[2]Grover L K.A Fast Quantum Mechanical Algorithm for Database Search [A]. In:28th Anntual ACM Symposium on Theory of Computing [C]. New York:ACM,1996:212-220.
[3]杨丽.基于多变量公钥密码体制的代理签名的研究[D]广东：华南理工大学,2011.
[4]沈璐璐.基于多变量公钥密码体制的多方同时签名[D]陕西：西安理工大学,2010.
[5]Bemstein Daniel J, Buchmann JohallIles, Dahmen Erik. Post quantum crypto-graphy. Springer-Verlag,2008.
[6]Tsujii S,Tadaki K,and Fujioka R. Piece in Hand concept for enhanceing the security of multivariate type public key cryptosystem:public key without containing all the information of secret key.IACR eprint 2004.
[7]Tsujii S,Tadaki K,and Fujioka R.Proposal for piece in hand matrix ver.2:General concept for enhancing security of multivariate public key cryptosystem. IACR eprint 2006.
[8]Bringer J,Chabanne H,and Dottax E.Perturbing and protecting a traceable block cipher. Cryptology ePrint Archive,Report 2006/064,2006.
[9]Gouget Aline and Patarin Jacques. Probabilistic multivariate cryptography. VIETCRYPT 2006,LNCS,Springer,2006,Vol.4341,1-18.
[10]BilletO. Robshaw M, Peyrin T. On building hash functions from multivariate quadratic equations,nformation Security and Privacy. ACISP 2007,LNCS, Springer,2007, V01.4586: 82-95.
[11]Ding J,and Yang B-Y Multivariates polynomials for hashing information security and cryptology(Inscrypt2007),LNCS, Springer,2007,V01.4990:358-371.
[12]Ding J and Gower J. Inoculating multivariate schemes against differential attacks. PKC 2006,LNCS,Springer,2006,V01.3958:290-301.
[13]Yang B and Chen J. Building secure tame—like multivariate public key Cryptosystems-the new TTS. Information Security and Privacy:10th Australasian Conference-ACISP 2005, LNCS,Springer,2005,V01,574:518-531.
[14]Wang L,Hu Y, Lai F,Chou C and Yang B.Tractable rational map signature, Public Key Cryptography—PKC 2005,LNCS,Springer,2005, V01.3386:244-257.
[15]Wang L C, and Chang F-H. Revision of tractable rational map cryptosystem.
[16]Fouque P-A, Granboulan L, and Stem J. Differential cryptanalysis for multivariate schemes. In Advances in Cryptology Eurocrypt'05,LNCS, Springer,2005.V01.3494:341-353.
[17]Wolf Christopher,Braeken An,and Preneel Bart. Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC.hl Conference On Security in Communication Networks—SCN 2004,LNCS, Springer,2004,V01.3352:294-309.
[18]Dubois V, Granboulan L, and Stern J. Cryptanalysis of HFE with Internal perturbation. PKC 2007,LNCS,Springer,2007,V01.4450:249-265.
[19]王志伟,郑世慧,杨义先.概率多变量签名方案的新构造.北京：北京邮电大学学报,2008,6(31)：26.29.
[20]Aumasson J-P and Meier W:Analysis of multivariate hash functions. Information Security and Cryptology-ICISC 2007,LNCS, Springer'2007, V01.4817:309-323.
[21]Luo Y and Lai X.Higher order differential cryptanalysis of multivariate hash functions. Cryptology ePrint archive,Report 2008/350.
[22]王鑫.基于多变量多项式的公钥密码方案研究[D].陕西：西安电子科技大学2009.3-4.
[23]Mambo M,Usuda K,Okamoto E. Proxy signature for delegating operation[C]//Proc.3rd ACM Conference on computer and communic-ation security.1996:48-57.
[24]Mambo M,Usuda K,Okamoto E. Proxy signatures:delegation of the power to sign messages[J].IEICE Trans. Fundamentals,1996, E79--A(9):1338-1354.
[25]Zhang K.Threshold proxy signature chemes[C]//1997 Information Security Workshop. Japan,1997:191-197.
[26]Yi L J,Bai G Q,Xiao G Z.Proxy multi-signature scheme:A new type of proxy signature scheme[J].Electron Letter,2000,36(6):527-528
[27]祁明,Harn L基于离散对数的若干新型代理签名方案[J].电子学报,2000,28(11)：111-225.
[28]Lee B,Kim H.Kim K. Strong proxy signature and its application[C]//Proc of ACISP' 2001.2001.603-608.
[29]Lee B,Kim H.Kim K. Secure mobile agent using strong non-designated proxy signature [C]//Proc of ACISP'2001.2001.474-476.
[30]Shum K,Wei Victor.A strong proxy signature scheme with proxy signer privacy protection[EB/OL].
[31]Shum K, Wei Victor K. A Strong Proxy Signature Scheme with Proxy Signer Privacy Protection [A]. In:Proc. Of the 11th IEEE Int. Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE'02) [C]. New York:IEEE Press,2002.
[32]赵泽茂.数字签名理论.科学出版社.2007：111-112.
[33]Ars G, Faugere J, Imai H, Kawazoe M, Sugita M.Comparison Between XL and Grobner Basis Algorithms [A]. In:Asiacrypt 2004[C].LNCS 3329, Spring,2004:338-353.
[34]Faugere Jean-Charles. A New Efficient Algorithm for Computing Grobner Bases(F4) [J]. Journal of Pure and Applied Algebra, June 1999,139:61-88.
[35]Faugere Jean-Charles. A New Efficient Algorithm for Computing Grobner Bases without Reduction to Zero(F5) [A]. In:International Symposium on Symbolic and Algebraic Computation-ISSAC 2002[C]. ACM Press,2002.75-83.
[36]Bettale Luk, Faugere Jean-Charles, Perret Ludovic. Security analysis multivariate polynomials for hash.Inscrypt 2008,LNCS,Springer,2009, v01.5487:115-124.
[37]Courtois N.Generic Attacks and the Security of Quartz.PKC 2003,LNCS v01.2567:35 1-364.
[38]马伟芳代理签名及其应用研究[D]陕西：陕西师范大学,2010.
[39]Patarin J, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP):Two New Families of Asymmetric Algorithms [A], in Advances in Cryptology-EUROCRYPT'96, LNCS 1070[C]. Springer-Verlag,1996:33-48.
[40]Ding, Jintai and Schmidt, Dieter (2005b). Rainbow, a new multivariable polynomial signature scheme. In loannidis, John, Keromytis, Angelos D, and Yung, Moti, editors. Third International Conference Applied Cryptography and Network Security (ACNS 2005), volume 3531 of LNCS Springer.
[41]Patarin,Jacques(1997).The oil and vinegar signature scheme. Dagstuhl Workshop on Cryptography,September 1997.
[42]杨光栋.基于多变量公钥密码体制的群签名的研究[D].广东：华南理工大学,2011.
[43]Coppersmith, Don, Stern, Jacques, and Vaudenay, Serge (1997). The security of the birational permutation signature schemes.J. Cryptology,10(3):207-221.
[44]Courtois, Nicolas (2001). The security of hidden field equations(HFE). In Naccachc,C., editor. Progress in cryptology,CT-RSA,volume 2020 of LNCS:266-281.
[45]Patarin, Jacques (1995). Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88.In Coppersmith,D.,editor. Advances in Cryptology-Crypto'95,63 of LNCS: 248-261.
[46]Wolf, Christopher, Bracken, An, and Preneel, Bart (2004). Efficient cryptanalysis of rse(2)pkc and rsse(2)pkc. In Blundo, Carlo and Cimato, Stelvio, editors. Security in Communication Networks:4th International Conference,SCN 2004,Amalfi,Italy,September 8-10,2004, volume 3352 of LNCS:294-309.
[2]Grover L K.A Fast Quantum Mechanical Algorithm for Database Search [A]. In:28th Anntual ACM Symposium on Theory of Computing [C]. New York:ACM,1996:212-220.
[3]杨丽.基于多变量公钥密码体制的代理签名的研究[D]广东：华南理工大学,2011.
[4]沈璐璐.基于多变量公钥密码体制的多方同时签名[D]陕西：西安理工大学,2010.
[5]Bemstein Daniel J, Buchmann JohallIles, Dahmen Erik. Post quantum crypto-graphy. Springer-Verlag,2008.
[6]Tsujii S,Tadaki K,and Fujioka R. Piece in Hand concept for enhanceing the security of multivariate type public key cryptosystem:public key without containing all the information of secret key.IACR eprint 2004.
[7]Tsujii S,Tadaki K,and Fujioka R.Proposal for piece in hand matrix ver.2:General concept for enhancing security of multivariate public key cryptosystem. IACR eprint 2006.
[8]Bringer J,Chabanne H,and Dottax E.Perturbing and protecting a traceable block cipher. Cryptology ePrint Archive,Report 2006/064,2006.
[9]Gouget Aline and Patarin Jacques. Probabilistic multivariate cryptography. VIETCRYPT 2006,LNCS,Springer,2006,Vol.4341,1-18.
[10]BilletO. Robshaw M, Peyrin T. On building hash functions from multivariate quadratic equations,nformation Security and Privacy. ACISP 2007,LNCS, Springer,2007, V01.4586: 82-95.
[11]Ding J,and Yang B-Y Multivariates polynomials for hashing information security and cryptology(Inscrypt2007),LNCS, Springer,2007,V01.4990:358-371.
[12]Ding J and Gower J. Inoculating multivariate schemes against differential attacks. PKC 2006,LNCS,Springer,2006,V01.3958:290-301.
[13]Yang B and Chen J. Building secure tame—like multivariate public key Cryptosystems-the new TTS. Information Security and Privacy:10th Australasian Conference-ACISP 2005, LNCS,Springer,2005,V01,574:518-531.
[14]Wang L,Hu Y, Lai F,Chou C and Yang B.Tractable rational map signature, Public Key Cryptography—PKC 2005,LNCS,Springer,2005, V01.3386:244-257.
[15]Wang L C, and Chang F-H. Revision of tractable rational map cryptosystem.
[16]Fouque P-A, Granboulan L, and Stem J. Differential cryptanalysis for multivariate schemes. In Advances in Cryptology Eurocrypt'05,LNCS, Springer,2005.V01.3494:341-353.
[17]Wolf Christopher,Braeken An,and Preneel Bart. Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC.hl Conference On Security in Communication Networks—SCN 2004,LNCS, Springer,2004,V01.3352:294-309.
[18]Dubois V, Granboulan L, and Stern J. Cryptanalysis of HFE with Internal perturbation. PKC 2007,LNCS,Springer,2007,V01.4450:249-265.
[19]王志伟,郑世慧,杨义先.概率多变量签名方案的新构造.北京：北京邮电大学学报,2008,6(31)：26.29.
[20]Aumasson J-P and Meier W:Analysis of multivariate hash functions. Information Security and Cryptology-ICISC 2007,LNCS, Springer'2007, V01.4817:309-323.
[21]Luo Y and Lai X.Higher order differential cryptanalysis of multivariate hash functions. Cryptology ePrint archive,Report 2008/350.
[22]王鑫.基于多变量多项式的公钥密码方案研究[D].陕西：西安电子科技大学2009.3-4.
[23]Mambo M,Usuda K,Okamoto E. Proxy signature for delegating operation[C]//Proc.3rd ACM Conference on computer and communic-ation security.1996:48-57.
[24]Mambo M,Usuda K,Okamoto E. Proxy signatures:delegation of the power to sign messages[J].IEICE Trans. Fundamentals,1996, E79--A(9):1338-1354.
[25]Zhang K.Threshold proxy signature chemes[C]//1997 Information Security Workshop. Japan,1997:191-197.
[26]Yi L J,Bai G Q,Xiao G Z.Proxy multi-signature scheme:A new type of proxy signature scheme[J].Electron Letter,2000,36(6):527-528
[27]祁明,Harn L基于离散对数的若干新型代理签名方案[J].电子学报,2000,28(11)：111-225.
[28]Lee B,Kim H.Kim K. Strong proxy signature and its application[C]//Proc of ACISP' 2001.2001.603-608.
[29]Lee B,Kim H.Kim K. Secure mobile agent using strong non-designated proxy signature [C]//Proc of ACISP'2001.2001.474-476.
[30]Shum K,Wei Victor.A strong proxy signature scheme with proxy signer privacy protection[EB/OL].
[31]Shum K, Wei Victor K. A Strong Proxy Signature Scheme with Proxy Signer Privacy Protection [A]. In:Proc. Of the 11th IEEE Int. Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE'02) [C]. New York:IEEE Press,2002.
[32]赵泽茂.数字签名理论.科学出版社.2007：111-112.
[33]Ars G, Faugere J, Imai H, Kawazoe M, Sugita M.Comparison Between XL and Grobner Basis Algorithms [A]. In:Asiacrypt 2004[C].LNCS 3329, Spring,2004:338-353.
[34]Faugere Jean-Charles. A New Efficient Algorithm for Computing Grobner Bases(F4) [J]. Journal of Pure and Applied Algebra, June 1999,139:61-88.
[35]Faugere Jean-Charles. A New Efficient Algorithm for Computing Grobner Bases without Reduction to Zero(F5) [A]. In:International Symposium on Symbolic and Algebraic Computation-ISSAC 2002[C]. ACM Press,2002.75-83.
[36]Bettale Luk, Faugere Jean-Charles, Perret Ludovic. Security analysis multivariate polynomials for hash.Inscrypt 2008,LNCS,Springer,2009, v01.5487:115-124.
[37]Courtois N.Generic Attacks and the Security of Quartz.PKC 2003,LNCS v01.2567:35 1-364.
[38]马伟芳代理签名及其应用研究[D]陕西：陕西师范大学,2010.
[39]Patarin J, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP):Two New Families of Asymmetric Algorithms [A], in Advances in Cryptology-EUROCRYPT'96, LNCS 1070[C]. Springer-Verlag,1996:33-48.
[40]Ding, Jintai and Schmidt, Dieter (2005b). Rainbow, a new multivariable polynomial signature scheme. In loannidis, John, Keromytis, Angelos D, and Yung, Moti, editors. Third International Conference Applied Cryptography and Network Security (ACNS 2005), volume 3531 of LNCS Springer.
[41]Patarin,Jacques(1997).The oil and vinegar signature scheme. Dagstuhl Workshop on Cryptography,September 1997.
[42]杨光栋.基于多变量公钥密码体制的群签名的研究[D].广东：华南理工大学,2011.
[43]Coppersmith, Don, Stern, Jacques, and Vaudenay, Serge (1997). The security of the birational permutation signature schemes.J. Cryptology,10(3):207-221.
[44]Courtois, Nicolas (2001). The security of hidden field equations(HFE). In Naccachc,C., editor. Progress in cryptology,CT-RSA,volume 2020 of LNCS:266-281.
[45]Patarin, Jacques (1995). Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88.In Coppersmith,D.,editor. Advances in Cryptology-Crypto'95,63 of LNCS: 248-261.
[46]Wolf, Christopher, Bracken, An, and Preneel, Bart (2004). Efficient cryptanalysis of rse(2)pkc and rsse(2)pkc. In Blundo, Carlo and Cimato, Stelvio, editors. Security in Communication Networks:4th International Conference,SCN 2004,Amalfi,Italy,September 8-10,2004, volume 3352 of LNCS:294-309.