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

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

Abstract

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

CLC Number:

TN918.1

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.

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

Metrics

Recommended 0

No Suggested Reading articles found!

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 29

Related Articles 2

Metrics

Recommended 0

[1]	Huaqun WANG, Zhe LIU, Debiao HE, Jiguo LI. Identity-based provable data possession scheme for multi-source IoT terminal data in public cloud [J]. Journal on Communications, 2021, 42(7): 52-60.
[2]	Hua-wei HUANG,Chang-wen PENG,Yun-yun QU,Chun-hua LI. Security of the cryptosystems based on ergodic matrices [J]. Journal on Communications, 2015, 36(8): 61-67.