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

作　　者：Jinhui Liu Aiwan Fan Jianwei Jia Huanguo Zhang Houzhen Wang Shaowu Mao 

机构地区：[1]Computer School of Wuhan University,Wuhan 430072,China [2]Computer School of Pingdingshan University,Pingdingshan 467001,China

出　　处：《Tsinghua Science and Technology》2016年第3期344-351,共8页清华大学学报（自然科学版（英文版）

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

摘　　要：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.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.

关 键 词：CRYPTOGRAPHY post-quantum cryptography public key encryption CRYPTANALYSIS linear equations 

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