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
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (439.9 KB)
Cite
EndNote(RIS) BibTeX
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.

Keywords

cryptographypost-quantum cryptographypublic key encryptioncryptanalysislinear equations

References

[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 21 Issue 3,
June 2016
Pages 344-351
DOI: 10.1109/TST.2016.7488745
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

689

Views

41

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