Cryptanalysis of Schemes Based on Polynomial Symmetrical Decomposition  

作　　者：LIU Jinhui ZHANG Huanguo JIA Jianwei 

机构地区：[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

出　　处：《Chinese Journal of Electronics》2017年第6期1139-1146,共8页电子学报（英文版）

基　　金：supported by the National Natural Science Foundation of China(No.61303212,No.61170080,No.61202386);the State Key Program of National Natural Science of China(No.61332019,No.U1135004);the Major Research Plan of the National Natural Science Foundation of China(No.91018008);the National Basic Research Program of China(973 Program)(No.2014CB340600);the Hubei Natural Science Foundation of China(No.2011CDB453,No.2014CFB440)

摘　　要：Advances in quantum computation threaten to break public key cryptosystems such as RSA,ECC, and El Gamal that are based on the difficulty of factorization or taking a discrete logarithm, although up to now, no quantum algorithms have been found that are able to solve certain mathematical problems on non-commutative algebraic structures. Against this background, some novel public key cryptography based on Polynomial symmetrical decomposition(PSD) problem have been proposed. We find that these schemes are not secure. We present that they are vulnerable to structural attack, linearization equations attack, overdefined systems of multivariate polynomial equations attack and that, they only require polynomial time complexity to retrieve the same secret key for some given public keys respectively.We also propose an improvement to enhance public key cryptography based on PSD problem. In addition, we discuss possible lines of future work.Advances in quantum computation threaten to break public key cryptosystems such as RSA,ECC, and El Gamal that are based on the difficulty of factorization or taking a discrete logarithm, although up to now, no quantum algorithms have been found that are able to solve certain mathematical problems on non-commutative algebraic structures. Against this background, some novel public key cryptography based on Polynomial symmetrical decomposition（PSD） problem have been proposed. We find that these schemes are not secure. We present that they are vulnerable to structural attack, linearization equations attack, overdefined systems of multivariate polynomial equations attack and that, they only require polynomial time complexity to retrieve the same secret key for some given public keys respectively.We also propose an improvement to enhance public key cryptography based on PSD problem. In addition, we discuss possible lines of future work.

关 键 词：CRYPTOGRAPHY Post-quantum computational cryptography Cryptanalysis Polynomial symmetrical decomposition(PSD) problem Computational complexity 

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