TY  - JOUR
AU  - Liu, Jinhui
AU  - Fan, Aiwan
AU  - Jia, Jianwei
AU  - Zhang, Huanguo
AU  - Wang, Houzhen
AU  - Mao, Shaowu
PY  - 2016
TI  - Cryptanalysis of Public Key Cryptosystems Based on Non-Abelian Factorization Problems
JO  - Tsinghua Science and Technology
SN  - 1007-0214
SP  - 344
EP  - 351
VL  - 21
IS  - 3
AB  - 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.
UR  - https://doi.org/10.1109/TST.2016.7488745
DO  - 10.1109/TST.2016.7488745