基于矩阵作用问题的公钥密码体制抗量子攻击安全性分析

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

通信学报 ›› 2023, Vol. 44 ›› Issue (3): 220-226.doi: 10.11959/j.issn.1000-436x.2023064

• 学术通信 • 上一篇

基于矩阵作用问题的公钥密码体制抗量子攻击安全性分析

黄华伟

贵州师范大学数学科学学院，贵州贵阳 550025

修回日期:2023-01-20 出版日期:2023-03-25 发布日期:2023-03-01
作者简介:黄华伟（1978- ），男，江西樟树人，博士，贵州师范大学副教授、硕士生导师，主要研究方向为密码学与信息安全
基金资助:
国家自然科学基金资助项目(61462016);贵州省科学技术基金资助项目(ZK[2021]313)

Security analysis of public-key cryptosystems based on matrix action problem against quantum attack

Huawei HUANG

School of Mathematical Sciences, Guizhou Normal University, Guiyang 550025, China

Revised:2023-01-20 Online:2023-03-25 Published:2023-03-01
Supported by:
The National Natural Science Foundation of China(61462016);The Science and Technology Foundation of Guizhou Province(ZK[2021]313)

摘要/Abstract

摘要：

半群作用问题作为离散对数问题的推广，在公钥密码的设计中有着重要应用。通过分析基于整数矩阵乘法半群在交换群直积上的作用问题的公钥密码体制，将矩阵看作直积元素的指数，这类矩阵作用具有类似群的指数运算法则。首先证明了若矩阵作用是单射或隐藏子群的生成元个数小于或等于矩阵阶的平方，则这类矩阵作用问题可在多项式时间归约为矩阵加法群直和的隐藏子群问题。其次证明了交换矩阵作用问题一定可在多项式时间归约为矩阵加法群直和的隐藏子群问题。因此基于这类矩阵作用问题的公钥密码体制无法抵抗量子攻击，该结论对抗量子攻击的公钥密码设计有理论指导意义。

关键词: Shor算法, 隐藏子群问题, 半群作用问题, 公钥密码, 抗量子攻击

Abstract:

As a generalization of the discrete logarithm problem, semigroup action problem has important applications in the design of public-key cryptography.Public-key cryptosystems based on action problem of integer matrix semigroups on the direct product of commutative groups were analyzed.The matrix was regarded as the exponent of direct product elements, and this class of matrix action had the exponential rules similar to group.It was proved that if the matrix action was injective or the number of generators of the hidden subgroup was less than or equal to the square of the order of the matrix, the matrix action problem could be reduced in polynomial time to the hidden subgroup problem of the direct sum of the additive group of the matrices.And it was proved that commutative matrix action problem could also be reduced to hidden subgroup problem of the direct sum of the additive group of the matrices in polynomial time.The cryptosystems based on this class of matrix action problem cannot against quantum attacks.This conclusion has theoretical significance in the design of public-key cryptography against quantum attacks.

Key words: Shor’s algorithm, hidden subgroup problem, semigroup action problem, public-key cryptography, against quantum attack

中图分类号:

TN918.1

黄华伟. 基于矩阵作用问题的公钥密码体制抗量子攻击安全性分析[J]. 通信学报, 2023, 44(3): 220-226.

Huawei HUANG. Security analysis of public-key cryptosystems based on matrix action problem against quantum attack[J]. Journal on Communications, 2023, 44(3): 220-226.

参考文献 29

[1]	SHOR P W . Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997,26(5): 1484-1509.
[2]	MONTANARO A . Quantum algorithms:an overview[J]. NPJ Quantum Information, 2016,2(1): 1-8.
[3]	ANSCHUETZ E , OLSON J , ASPURU-GUZIK A ,et al. Variational quantum factoring[C]// Quantum Technology and Optimization Problems. Berlin:Springer, 2019: 74-85.
[4]	GYONGYOSI L , IMRE S . A survey on quantum computing technology[J]. Computer Science Review, 2019,31: 51-71.
[5]	DALEY A J , BLOCH I , KOKAIL C ,et al. Practical quantum advantage in quantum simulation[J]. Nature, 2022,607(7920): 667-676.
[6]	王丽萍, 戚艳红 . 基于编码的后量子公钥密码研究进展[J]. 信息安全学报, 2019,4(2): 20-28.
	WANG L P , QI Y H . Recent progress of code-based post-quantum public key cryptography[J]. Journal of Cyber Security, 2019,4(2): 20-28.
[7]	王小云, 刘明洁 . 格密码学研究[J]. 密码学报, 2014,1(1): 13-27.
	WANG X Y , LIU M J . Survey of lattice-based cryptography[J]. Journal of Cryptologic Research, 2014,1(1): 13-27.
[8]	ASIF R . Post-quantum cryptosystems for Internet-of-things:a survey on lattice-based algorithms[J]. IoT, 2021,2(1): 71-91.
[9]	郁昱 . 后量子密码专栏序言[J]. 密码学报, 2017,4(5): 472-473.
	YU Y . Preface to post-quantum cryptography column[J]. Journal of Cryptologic Research, 2017,4(5): 472-473.
[10]	BERNSTEIN D J , BUCHMANN J , DAHMEN E . Post-quantum cryptography[M]. Berlin: Springer, 2009.
[11]	MAZE G , MONICO C , ROSENTHAL J . A public key cryptosystem based on actions by semigroups[C]// Proceedings of the IEEE International Symposium on Information Theory. Piscataway:IEEE Press, 2004:266.
[12]	MAZE G , MONICO C , ROSENTHAL J ,et al. Public key cryptography based on semigroup actions[J]. Advances in Mathematics of Communications, 2007,1(4): 489-507.
[13]	HUANG H W , YANG B , ZHU S L ,et al. Generalized ElGamal public key cryptosystem based on a new Diffie-Hellman problem[C]// International Conference on Provable Security. Berlin:Springer, 2008: 1-21.
[14]	CRAMER R , DAMGARD I , KILTZ E ,et al. DDH-like assumptions based on extension rings[C]// International Workshop on Public Key Cryptography. Berlin:Springer, 2012: 644-661.
[15]	WANG L C , WANG L H , CAO Z F ,et al. Conjugate adjoining problem in braid groups and new design of braid-based signatures[J]. Science China Information Sciences, 2010,53(3): 524-536.
[16]	CLIMENT J J , NAVARRO P R , TORTOSA L . An extension of the noncommutative Bergman’s ring with a large number of noninvertible elements[J]. Applicable Algebra in Engineering,Communication and Computing, 2014,25(5): 347-361.
[17]	GRIGORIEV D , SHPILRAIN V . Tropical cryptography[J]. Communications in Algebra, 2014,42(6): 2624-2632.
[18]	GRIGORIEV D , SHPILRAIN V . Tropical cryptography II:extensions by homomorphisms[J]. Communications in Algebra, 2019,47(10): 4224-4229.
[19]	EKERT A , JOZSA R . Quantum computation and Shor’s factoring algorithm[J]. Reviews of Modern Physics, 1996,68(3): 733-753.
[20]	JOZSA R . Quantum factoring,discrete logarithms,and the hidden subgroup problem[J]. Computing in Science ＆ Engineering, 2001,3(2): 34-43.
[21]	BONEH D , LIPTON R J . Quantum cryptanalysis of hidden linear functions[C]// Advances in Cryptology — CRYPT0’ 95. Berlin:Springer, 1995: 424-437.
[22]	HALLGREN S . Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem[J]. Journal of the ACM, 2007,54(1): 1-19.
[23]	AMBAINIS A , . New developments in quantum algorithms[C]// International Symposium on Mathematical Foundations of Computer Science. Berlin:Springer, 2010: 1-11.
[24]	GONCALVES D N , FERNANDES T , COSME C . An efficient quantum algorithm for the hidden subgroup problem over some non-abelian groups[J]. Tema, 2017,18(2): 215-223.
[25]	HORAN K , KAHROBAEI D . The hidden subgroup problem and post-quantum group-based cryptography[C]// International Congress on Mathematical Software. Berlin:Springer, 2018: 218-226.
[26]	SUO J W , WANG L C , YANG S J ,et al. Quantum algorithms for typical hard problems:a perspective of cryptanalysis[J]. Quantum Information Processing, 2020,19(6): 178.
[27]	BANIN M T , TSABAN B . A reduction of Semigroup DLP to classic DLP[J]. Designs,Codes and Cryptography, 2016,81(1): 75-82.
[28]	HAN J , ZHUANG J C . DLP in semigroups:algorithms and lower bounds[J]. Journal of Mathematical Cryptology, 2022,16(1): 278-288.
[29]	TINANI S , ROSENTHAL J . A deterministic algorithm for the discrete logarithm problem in a semigroup[J]. Journal of Mathematical Cryptology, 2022,16(1): 141-155.

基于矩阵作用问题的公钥密码体制抗量子攻击安全性分析

Security analysis of public-key cryptosystems based on matrix action problem against quantum attack

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

参考文献 29

相关文章 15

Metrics

推荐阅读 0

[1]	王子园, 杜瑞忠. 边缘环境下基于无证书公钥密码的数据完整性审计方案[J]. 通信学报, 2022, 43(7): 62-72.
[2]	王竹, 杨思琦, 李凤华, 耿魁, 彭婷婷, 史梦瑶. 高效可证明安全的无证书有序聚合签名方案[J]. 通信学报, 2022, 43(5): 58-67.
[3]	王化群, 刘哲, 何德彪, 李继国. 公有云中身份基多源IoT终端数据PDP方案[J]. 通信学报, 2021, 42(7): 52-60.
[4]	刘镇,韩益亮,杨晓元,柳曙光. 基于RLWE的可证明安全无陷门签密方案[J]. 通信学报, 2020, 41(6): 14-25.
[5]	李慧贤,邵璐,庞辽军. 基于多项式同构的代理重签名方案[J]. 通信学报, 2017, 38(2): 16-24.
[6]	秦艳琳,吴晓平,胡卫. 高效的无证书多接收者匿名签密方案[J]. 通信学报, 2016, 37(6): 129-136.
[7]	杜红珍,温巧燕. 无证书强指定验证者多重签名[J]. 通信学报, 2016, 37(6): 20-28.
[8]	黄华伟,彭长文,瞿云云,李春华. 遍历矩阵密码体制的安全性[J]. 通信学报, 2015, 36(8): 61-67.
[9]	聂旭云,刘波,鲁刚,钟婷. 新扩展多变量公钥密码方案的安全性分析[J]. 通信学报, 2015, 36(6): 60-65.
[10]	杜红珍,温巧燕. 改进的无证书有序多重签名方案[J]. 通信学报, 2015, 36(10): 56-61.
[11]	秦艳琳,吴晓平. 高效的无证书有序多重签名方案[J]. 通信学报, 2013, 34(7): 105-110.
[12]	秦艳琳，吴晓平. 高效的无证书有序多重签名方案[J]. 通信学报, 2013, 34(7): 12-110.
[13]	古春生. 破解HFEM公钥密码方案[J]. 通信学报, 2013, 34(3): 85-89.
[14]	张金中,寇应展,王韬,郭世泽,赵新杰. 针对滑动窗口算法的椭圆曲线密码故障分析[J]. 通信学报, 2012, 33(1): 71-78.
[15]	赵永哲,赵博,裴士辉,姜占华. HFEM公钥密码方案的设计与实现[J]. 通信学报, 2011, 32(6): 24-31.