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

Jinhui Liu; Aiwan Fan; Jianwei Jia; Huanguo Zhang; Houzhen Wang; Shaowu Mao

doi:10.1109/TST.2016.7488745

Tsinghua Science and Technology 2016, 21(3): 344-351 https://doi.org/10.1109/TST.2016.7488745

Open Access | Issue | Published: 13 June 2016

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

Show Author's Information Hide Author's Information Jinhui Liu, Aiwan Fan, Jianwei Jia, Huanguo Zhang(

), Houzhen Wang, Shaowu Mao

Computer School of Wuhan University, Wuhan 430072, China.

Computer School of Pingdingshan University, Pingdingshan 467001, China.

Keywords:

cryptanalysis, post-quantum cryptography, cryptography, public key encryption, linear equations

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

Download citation

EndNote(RIS)

BibTeX

511

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

CSCD

Abstract Full text About this article

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.

Full text

Abstract

Full text

Outline

About this article

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

Show Author's information Hide Author's Information Jinhui Liu, Aiwan Fan, Jianwei Jia, Huanguo Zhang(

), Houzhen Wang, Shaowu Mao

Computer School of Wuhan University, Wuhan 430072, China.

Computer School of Pingdingshan University, Pingdingshan 467001, China.

Abstract

Keywords: cryptanalysis, post-quantum cryptography, cryptography, public key encryption, linear equations

References(16)

[1]

Cao Z., New Directions of Modern Cryptography. CRC Press, 2012.

Google Scholar

[2]

Mosca M., Post-Quantum Cryptography. Springer International Publishing, 2014.

Google Scholar

[3]

Gaborit P., Post-Quantum Cryptography. Springer Berlin Heidelberg, 2013.

Google Scholar

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

DOI

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

Google Scholar

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

DOI Google Scholar

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

DOI Google Scholar

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

DOI Google Scholar

[9]

Boaz T., Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography, Journal of Cryptology, vol. 28, no. 3, pp. 601-622 , 2015.

DOI Google Scholar

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

DOI Google Scholar

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

DOI

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

DOI Google Scholar

[13]

Myasnikov A., Shpilrain V., and Ushakov A., Noncommutative Cryptography and Complexity of Grouptheoretic Problems. American Mathematical Society, 2011.

Google Scholar

[14]

Gashkov S. and Sergeev I., Complexity of computation in finite fields, Journal of Mathematical Sciences, vol. 191, no. 5, pp. 661-685, 2013.

DOI Google Scholar

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

DOI Google Scholar

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

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 20 January 2016

Accepted: 17 March 2016

Published: 13 June 2016

Issue date: June 2016

Copyright

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Nos. 61303212, 61170080, 61202386, 61332019, U1135004, and 91018008), the National Key Basic Research and Development (973) Program of China (No. 2014CB340600), and the Natural Science Foundation of Hubei Province (Nos. 2011CDB453 and 2014CFB440)