AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (439.9 KB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Cryptanalysis of Public Key Cryptosystems Based on Non-Abelian Factorization Problems

Computer School of Wuhan University, Wuhan 430072, China.
Computer School of Pingdingshan University, Pingdingshan 467001, China.
Show Author Information

Abstract

Advances in quantum computers threaten to break public-key cryptosystems (e.g., RSA, ECC, and EIGamal), based on the hardness of factoring or taking a discrete logarithm. However, no quantum algorithms have yet been found for solving certain mathematical problems in non-commutative algebraic structures. Recently, two novel public-key encryption schemes, BKT-B cryptosystem and BKT-FO cryptosystem, based on factorization problems have been proposed at Security and Communication Networks in 2013. In this paper we show that these two schemes are vulnerable to structural attacks and linearization equations attacks, and that they only require polynomial time complexity to obtain messages from associated public keys. We conduct a detailed analysis of the two attack methods and show corresponding algorithmic descriptions and efficiency analyses. In addition, we provide some improvement suggestions for the two public-key encryption schemes.

References

[1]
Cao Z., New Directions of Modern Cryptography. CRC Press, 2012.
[2]
Mosca M., Post-Quantum Cryptography. Springer International Publishing, 2014.
[3]
Gaborit P., Post-Quantum Cryptography. Springer Berlin Heidelberg, 2013.
[4]
Ling S., Phan D. H., Stehl’e D., Steinfeld R., Hardness of k-LWE and applications in traitor tracing, in Proc. Advances in Cryptology-CRYPTO, Santa Barbara, CA, USA, 2014, pp. 315-334.
[5]
Zhang H., Liu J., Jia J., Mao S., and Wu W., A survey on applications of matrix decomposition in cryptography, Journal of Cryptologic Research, vol. 9, no. 1, pp. 341-357, 2014.
[6]
Wang H., Zhang H., Wang Z., and Tang M., Extended multivariate public key cryptosystems with secure encryption function, SCIENCE CHINA Information Sciences, vol. 54, no. 6, pp. 1161-1171, 2011.
[7]
Mao S., Zhang H., Wu W., Liu J., and Wang H., A resistant quantum key exchange protocol and its corresponding encryption scheme, China Communications, vol. 11, no. 9, pp. 131-141, 2014.
[8]
Yang Y., Zhang S., Yang J., Li J., and Li Z., Targeted fully homomorphic encryption based on a double decryption algorithm for polynomials, Tsinghua Science and Technology, vol. 19, no. 5, pp. 478-485, 2014.
[9]
Boaz T., Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography, Journal of Cryptology, vol. 28, no. 3, pp. 601-622 , 2015.
[10]
Wang S., Zhu Y., Ma D., and Feng R., Lattice-based key exchange on small integer solution problem, SCIENCE CHINA Information Sciences, vol. 57, no. 11, pp. 1-12, 2014.
[11]
Habeeb M., Kahrobaei D., Koupparis C., and Shpilrain V., Public key exchange using semidirect product of (semi)groups, in Proceedings of ACNS 2013, 2013.
[12]
Gu L., Wang L., Ota K., Dong M., Cao Z., and Yang Y., New public key cryptosystems based on non-Abelian factorization problems, Security and Communication Networks, vol. 6, no. 7, pp. 912-922, 2013.
[13]
Myasnikov A., Shpilrain V., and Ushakov A., Noncommutative Cryptography and Complexity of Grouptheoretic Problems. American Mathematical Society, 2011.
[14]
Gashkov S. and Sergeev I., Complexity of computation in finite fields, Journal of Mathematical Sciences, vol. 191, no. 5, pp. 661-685, 2013.
[15]
Bettale L., Faug‘ere J. C., Perret L., HFE Cryptanalysis of, multi-HFE and variants for odd and even characteristic, Designs, Codes and Cryptography, vol. 69, no. 1, pp. 1-52, 2013.
[16]
Gu L. and Zheng S., Conjugacy systems based on Nonabelian factorization problems and their applications in cryptography, Journal of Applied Mathematics, vol. 52, no. 2, pp. 1-9, 2014.
Tsinghua Science and Technology
Pages 344-351
Cite this article:
Liu J, Fan A, Jia J, et al. Cryptanalysis of Public Key Cryptosystems Based on Non-Abelian Factorization Problems. Tsinghua Science and Technology, 2016, 21(3): 344-351. https://doi.org/10.1109/TST.2016.7488745

683

Views

40

Downloads

3

Crossref

N/A

Web of Science

6

Scopus

0

CSCD

Altmetrics

Received: 20 January 2016
Accepted: 17 March 2016
Published: 13 June 2016
© The author(s) 2016
Return