基于量子BCH码的McEliece及Niederreiter公钥密码算法研究
|
摘要
针对量子计算攻击对传统密码体制的安全威胁,设计出一类抗量子攻击的McEliece公钥密码体制,因为量子计算没有攻击McEliece公钥密码体制的多项式时间算法。给出了3类量子BCH码的生成算法,第1类是一般性量子BCH码生成算法,第2类是特殊的对称量子BCH码生成算法,第3类是特殊的非对称量子BCH码生成算法。以本文生成的非对称量子BCH码为基础,设计出量子McEliece公钥密码体制和量子Niederreiter公钥密码体制,详细给出这两种公钥体制的加密和解密过程。给出的密码体制既保留了抗量子计算优点,又能在量子态下加密和解密,其基本域为任意有限域。分析了这两种体制的计算复杂性理论、数据结构及算法模式,得到了时间复杂性和空间复杂性达到指数级,得到了抵抗Shor算法和Grover算法攻击的结果。最后,利用量子BCH码的结构特征,设计了一种经典Niederreiter体制数字签名,具有抗量子攻击能力。
In order to resist the security threat of quantum computing attacks to the traditional cryptosystem, a class of McEliece public-key cryptosystems was designed in this paper, based on the fact that no quantum computing algorithm can attack the McEliece public-key cryptosystem within polynomial time. Three types of algorithms for generating quantum BCH codes were presented. The first one was general quantum BCH code generation algorithm, the second one was special symmetric quantum BCH code generation algorithm, and the third one was special asymmetric quantum BCH code generation algorithm. Based on the asymmetric quantum BCH codes generated in this paper, the quantum McEliece public-key cryptosystem and the quantum Niederreiter public-key cryptosystem were designed, and the encryption and decryption processes of the two public-key systems were given in detail. The proposed cryptosystems not only retained the advantages of the post-quantum computation, but also can encrypt and decrypt in quantum states. The basic field has been extended to the arbitrary finite field. The computational complexity theory, data structure and algorithm model of the two public-key cryptosystems were analyzed. The exponential time and space complexity were obtained, and the results of resisting the attacks of Shor and Grover algorithms were also obtained. Finally, with the structural characteristics of quantum BCH codes, a classical Niederreiter signature system was designed, which has the ability of resisting quantum attacks.
In order to resist the security threat of quantum computing attacks to the traditional cryptosystem, a class of McEliece public-key cryptosystems was designed in this paper, based on the fact that no quantum computing algorithm can attack the McEliece public-key cryptosystem within polynomial time. Three types of algorithms for generating quantum BCH codes were presented. The first one was general quantum BCH code generation algorithm, the second one was special symmetric quantum BCH code generation algorithm, and the third one was special asymmetric quantum BCH code generation algorithm. Based on the asymmetric quantum BCH codes generated in this paper, the quantum McEliece public-key cryptosystem and the quantum Niederreiter public-key cryptosystem were designed, and the encryption and decryption processes of the two public-key systems were given in detail. The proposed cryptosystems not only retained the advantages of the post-quantum computation, but also can encrypt and decrypt in quantum states. The basic field has been extended to the arbitrary finite field. The computational complexity theory, data structure and algorithm model of the two public-key cryptosystems were analyzed. The exponential time and space complexity were obtained, and the results of resisting the attacks of Shor and Grover algorithms were also obtained. Finally, with the structural characteristics of quantum BCH codes, a classical Niederreiter signature system was designed, which has the ability of resisting quantum attacks.
引文
[1]Zhang Huanguo,Wang Houzhen.Anti-cryptography quantum computing research[J].Netinfo Security,2011(6):56-59.
[2]Grigni M,Schulman L,Vazirani M,et al.Quantum mechanical algorithms for the nonabelian hidden subgroup problem[J].Combinatorica,2004,24(1):137-154.
[3]Bernstein D J,Buchmann J,Dahmen E,等.抗量子计算密码[M].张焕国,王后珍,杨昌,译.北京:清华大学出版社,2015.
[4]Jin Lingfei,Xing Chaoping.A construction of new quantum MDS codes[J].IEEE Transactions on Information Theory,2014,60(5):2921-2925.
[5]Jin Lingfei,Xing Chaoping.New MDS self-dual codes from generalized reed-olomon codes[J].IEEE Transactions on Information Theory,2017,63(3):1434-1438.
[6]Jin Lingfei.Quantum stabilizer codes from maximal curves[J].IEEE Transactions on Information Theory,2014,60(1):313-316.
[7]Xu Gen,Li Ruihu,Guo Luobin,et al.New quantum codes constructed from quaternary BCH codes[J].Quantum Information Processing,2016,15(10):4099-4116.
[8]Chuang I,Gottesman D.Quantum digital signatures:US7246240[P].2007-07-17.
[9]Ablayev F M,Vasiliev A V.Cryptographic quantum hashing[J].Laser Physics Letters,2014,11(2):025202.
[10]Bennett C H,Brassard G.Quantum cryptography:Public key distribution and coin tossing[J].Theoretical Computer Science,2014,560(1):7-11.
[11]Zeng Guihua.Quantum authentication[M]//Quantum Private Communication.Heidelberg:Springer,2010:167-215.
[12]Toyran M.Quantum cryptography[C]//Proceedings of the2007 IEEE 15th Signal Processing and Communications Applications.Eskisehir:IEEE,2007:1-4.
[13]Okamoto T,Tanaka K,Uchiyama S.Quantum public-key cryptosystems[M]//Advances in Cryptology—CRYPTO2000.Heidelberg:Springer,2000:147-165.
[14]Wieschebrink C.Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes[C]//Proceedings of the Third International Conference on Post-Quantum Cryptography.Heidelberg:Springer-Verlag,2010:61-72.
[15]McEliece R J.A public-key cryptosystem based on algebra-ic coding theory[R].Pasadena:Califomia Institute of Technology,1978:114-116
[16]Li Yuanxing,Deng R H,Wang Xinmei.On the equivalence of McEliece's and Niederreiter's public-key cryptosystems[J].IEEE Transactions on Information Theory,1994,40(1):271-273.
[17]Cao Dong,Zhao Shengmei,Song Yaoliang,et al.Quantum McEliece public-key cryptosystem based on quantum QCLDPC codes[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science),2011,31(2):64-68.[曹东,赵生妹,宋耀良,等.一种基于量子准循环LDPC码的McEliece公钥密码算法[J].南京邮电大学学报(自然科学版),2011,31(2):64-68.]
[18]Huffman W C,Pless V.Fundamentals of error-correcting codes[M].Cambridge:Cambridge University Press,2003.
[19]Calderbank A R,Rains E M,Shor P W,et al.Quantum error correction via codes over GF(4)[J].IEEE Transactions on Information Theory,1998,44(4):1369-1387.
[20]Aly S A,Klappenecker A,Sarvepalli P K.On quantum and classical BCH codes[J].IEEE Transactions on Information Theory,2007,53(3):1183-1188.
[21]Wang Liqi,Zhu Shixin.On the construction of optimal asymmetric quantum codes[J].International Journal of Quantum Information,2014,12(3):1450017.
[22]Zhang Huanguo,Mao Shaowu,Wu Wanqing,et al.Overview of quantum computation complexity theory[J].Chinese Journal of Computers,2016,39(12):2403-2428.[张焕国,毛少武,吴万青,等.量子计算复杂性理论综述[J].计算机学报,2016,39(12):2403-2428.]
[23]Dinh H,Moore C,Russell A.McEliece and Niederreiter cryptosystems that resist quantum fourier sampling attacks[M]//Advances in Cryptology-CRYPTO 2011.Heidelberg:SpringerVerlag,2011:761-779.
[24]Courtois N T,Finiasz M,Sendrier N.How to achieve a McEliece-based digital signature scheme[M]//Advances in Cryptology ASIACRYPT 2001.Heidelberg:Springer-Verlag,2001:157-174.
[25]Liu Jinhui,Jia Jianwei,Zhang Huanguo,et al.Digital signature protocol based on error-correcting code[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2014,42(11):97-101.[刘金会,贾建卫,张焕国,等.一种基于纠错码的数字签名协议[J].华中科技大学学报(自然科学版),2014,42(11):97-101.]
[2]Grigni M,Schulman L,Vazirani M,et al.Quantum mechanical algorithms for the nonabelian hidden subgroup problem[J].Combinatorica,2004,24(1):137-154.
[3]Bernstein D J,Buchmann J,Dahmen E,等.抗量子计算密码[M].张焕国,王后珍,杨昌,译.北京:清华大学出版社,2015.
[4]Jin Lingfei,Xing Chaoping.A construction of new quantum MDS codes[J].IEEE Transactions on Information Theory,2014,60(5):2921-2925.
[5]Jin Lingfei,Xing Chaoping.New MDS self-dual codes from generalized reed-olomon codes[J].IEEE Transactions on Information Theory,2017,63(3):1434-1438.
[6]Jin Lingfei.Quantum stabilizer codes from maximal curves[J].IEEE Transactions on Information Theory,2014,60(1):313-316.
[7]Xu Gen,Li Ruihu,Guo Luobin,et al.New quantum codes constructed from quaternary BCH codes[J].Quantum Information Processing,2016,15(10):4099-4116.
[8]Chuang I,Gottesman D.Quantum digital signatures:US7246240[P].2007-07-17.
[9]Ablayev F M,Vasiliev A V.Cryptographic quantum hashing[J].Laser Physics Letters,2014,11(2):025202.
[10]Bennett C H,Brassard G.Quantum cryptography:Public key distribution and coin tossing[J].Theoretical Computer Science,2014,560(1):7-11.
[11]Zeng Guihua.Quantum authentication[M]//Quantum Private Communication.Heidelberg:Springer,2010:167-215.
[12]Toyran M.Quantum cryptography[C]//Proceedings of the2007 IEEE 15th Signal Processing and Communications Applications.Eskisehir:IEEE,2007:1-4.
[13]Okamoto T,Tanaka K,Uchiyama S.Quantum public-key cryptosystems[M]//Advances in Cryptology—CRYPTO2000.Heidelberg:Springer,2000:147-165.
[14]Wieschebrink C.Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes[C]//Proceedings of the Third International Conference on Post-Quantum Cryptography.Heidelberg:Springer-Verlag,2010:61-72.
[15]McEliece R J.A public-key cryptosystem based on algebra-ic coding theory[R].Pasadena:Califomia Institute of Technology,1978:114-116
[16]Li Yuanxing,Deng R H,Wang Xinmei.On the equivalence of McEliece's and Niederreiter's public-key cryptosystems[J].IEEE Transactions on Information Theory,1994,40(1):271-273.
[17]Cao Dong,Zhao Shengmei,Song Yaoliang,et al.Quantum McEliece public-key cryptosystem based on quantum QCLDPC codes[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science),2011,31(2):64-68.[曹东,赵生妹,宋耀良,等.一种基于量子准循环LDPC码的McEliece公钥密码算法[J].南京邮电大学学报(自然科学版),2011,31(2):64-68.]
[18]Huffman W C,Pless V.Fundamentals of error-correcting codes[M].Cambridge:Cambridge University Press,2003.
[19]Calderbank A R,Rains E M,Shor P W,et al.Quantum error correction via codes over GF(4)[J].IEEE Transactions on Information Theory,1998,44(4):1369-1387.
[20]Aly S A,Klappenecker A,Sarvepalli P K.On quantum and classical BCH codes[J].IEEE Transactions on Information Theory,2007,53(3):1183-1188.
[21]Wang Liqi,Zhu Shixin.On the construction of optimal asymmetric quantum codes[J].International Journal of Quantum Information,2014,12(3):1450017.
[22]Zhang Huanguo,Mao Shaowu,Wu Wanqing,et al.Overview of quantum computation complexity theory[J].Chinese Journal of Computers,2016,39(12):2403-2428.[张焕国,毛少武,吴万青,等.量子计算复杂性理论综述[J].计算机学报,2016,39(12):2403-2428.]
[23]Dinh H,Moore C,Russell A.McEliece and Niederreiter cryptosystems that resist quantum fourier sampling attacks[M]//Advances in Cryptology-CRYPTO 2011.Heidelberg:SpringerVerlag,2011:761-779.
[24]Courtois N T,Finiasz M,Sendrier N.How to achieve a McEliece-based digital signature scheme[M]//Advances in Cryptology ASIACRYPT 2001.Heidelberg:Springer-Verlag,2001:157-174.
[25]Liu Jinhui,Jia Jianwei,Zhang Huanguo,et al.Digital signature protocol based on error-correcting code[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2014,42(11):97-101.[刘金会,贾建卫,张焕国,等.一种基于纠错码的数字签名协议[J].华中科技大学学报(自然科学版),2014,42(11):97-101.]