logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 5: 052109(2016) https://doi.org/10.1007/s11432-015-5443-2

Cryptanalysis of an asymmetric cipher protocol using a matrix decomposition problem

More info
  • ReceivedAug 27, 2015
  • AcceptedNov 1, 2015
  • PublishedJan 18, 2016

Abstract

Advances in quantum computation threaten to break public key cryptosystems such as RSA, ECC, and ElGamal that are based on the difficulty of factorization or taking a discrete logarithm, although up to now, no quantum algorithms have been found to be able to solve certain mathematical problems on non-commutative algebraic structures. Against this background, Raulynaitis et al. have proposed a novel asymmetric cipher protocol using a matrix decomposition problem. Their proposed scheme is vulnerable to a linear algebra attack based on the probable occurrence of weak keys in the generation process. In this paper, we show that the asymmetric cipher of the non-commutative cryptography scheme is vulnerable to a linear algebra attack and that it only requires polynomial time to obtain the equivalent keys for some given public keys. We also propose an improvement to enhance the scheme of Raulynaitis et al.


Funded by

National Natural Science Foundation of China(61303212)

National Natural Science Foundation of China(61170080)

National Natural Science Foundation of China(61202386)

state Key Program of National Natural Science of China(61332019)

state Key Program of National Natural Science of China(U1135004)

national Key Basic Research Program of China(2014CB340600)

major Research Plan of the National Natural Science Foundation of China(91018008)

Hubei Natural Science Foundation of China(2011CDB453)

Hubei Natural Science Foundation of China(2014CFB440)


Acknowledgment

Acknowledgments

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


References

[1] Cao Z. New Directions of Modern Cryptography. Boca Raton: CRC Press, 2012. 10-255. Google Scholar

[2] Peikert C. Lattice cryptography for the internet. In: Mosca M, ed. Post-Quantum Cryptography. Waterloo: Springer, 2014. 197-219. Google Scholar

[3] Shi J J, Shi R H, Guo Y, et al. Sci China Inf Sci, 2013, 56: 052115 Google Scholar

[4] Song F. A note on quantum security for post-quantum cryptography. In: Mosca M, ed. Post-Quantum Cryptography. Waterloo: Springer, 2014. 246-265. Google Scholar

[5] Tsaban B. J Cryptol, 2013, 28: 601-622 Google Scholar

[6] Zhang H G, Liu J H, Jia J W, et al. J Cryptol Res, 2014, 1: 341-357 Google Scholar

[7] Mao S W, Zhang H G, Wu W Q, et al. China Commun, 2014, 11: 131-141 Google Scholar

[8] Wang H Z, Zhang H G, Wang Z Y, et al. Sci China Inf Sci, 2011, 54: 1161-1171 Google Scholar

[9] Ling S, Phan D H, Stehlé D, et al. Hardness of k-LWE and applications in traitor tracing. In: Proceedings of Advances in Cryptology-CRYPTO. Berlin: Springer, 2014. 315-334. Google Scholar

[10] Regev O. On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. New York: ACM Press, 2005. 84-93. Google Scholar

[11] Braun J, Buchmann J, Mullan C, et al. Design Code Cryptogr, 2014, 71: 459-478 Google Scholar

[12] Wang S B, Zhu Y, Ma D, et al. Sci China Inf Sci, 2014, 57: 112111 Google Scholar

[13] Albrecht M R, Faugere J C, Fitzpatrick R, et al. Practical cryptanalysis of a public-key encryption scheme based on new multivariate quadratic assumptions. In: Proceedings of Public Key Cryptography-PKC. Berlin: Springer, 2014. 446-464. Google Scholar

[14] Raulynaitis A, Sakalauskas E, Japertas S. Informatica, 2010, 21: 215-228 Google Scholar

[15] Raulynaitis A, Japertas S. Asymmetric cipher protocol using decomposition problem. In: Proceedings of Information Research and Applications, Varna, 2008. 107-111. Google Scholar

[16] Gashkov S B, Sergeev I S. J Math Sci, 2013, 191: 661-685 Google Scholar

[17] Gu L, Zheng S. J Appl Math, 2014, 52: 1-9 Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1