Cryptanalysis of an asymmetric cipher protocol using a matrix decomposition problem  

作　　者：Jinhui LIU Huanguo ZHANG Jianwei JIA Houzhen WANG Shaowu MAO Wanqing WU 

机构地区：[1]Computer School of Wuhan University, Wuhan 430072, China [2]Key Laboratory of Aerospace Information security and trusted computing Ministry of Education, Wuhan 430072, China

出　　处：《Science China(Information Sciences)》2016年第5期129-139,共11页中国科学（信息科学）（英文版）

基　　金：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);Hubei Natural Science Foundation of China (Grant Nos. 2011CDB453, 2014CFB440)

摘　　要：Advances in quantum computation threaten to break public key cryptosystems such as RSA, ECC, and E1Gamal 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.Advances in quantum computation threaten to break public key cryptosystems such as RSA, ECC, and E1Gamal 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.

关 键 词：CRYPTOGRAPHY post-quantum computational cryptography asymmetric cipher protocol cryptanal-ysis matrix decomposition 

分 类 号：TN918.4[电子电信—通信与信息系统]