LIU Jinhui, ZHANG Huanguo, JIA Jianwei. Cryptanalysis of Schemes Based on Polynomial Symmetrical Decomposition[J]. Chinese Journal of Electronics, 2017, 26(6): 1139-1146. doi: 10.1049/cje.2017.05.005
Citation: LIU Jinhui, ZHANG Huanguo, JIA Jianwei. Cryptanalysis of Schemes Based on Polynomial Symmetrical Decomposition[J]. Chinese Journal of Electronics, 2017, 26(6): 1139-1146. doi: 10.1049/cje.2017.05.005

Cryptanalysis of Schemes Based on Polynomial Symmetrical Decomposition

doi: 10.1049/cje.2017.05.005
Funds:  This work is 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), and the Hubei Natural Science Foundation of China (No.2011CDB453, No.2014CFB440).
More Information
  • Corresponding author: ZHANG Huanguo (corresponding author) was born in Hebei Province, China, in 1945. He graduated from Xidian University in 1970 with a B.E. degree. He is now a professor and Ph.D. supervisor at the School of Computer, Wuhan University.(
  • Received Date: 2015-10-22
  • Rev Recd Date: 2016-05-11
  • Publish Date: 2017-11-10
  • 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 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.
  • loading
  • Z.F. Cao,New Directions of Modern Cryptography, Boca Raton:CRC Press, 2012.
    L. Gu, L. Wang, Ota K., et al., "New public key cryptosystems based on non-Abelian factorization problems", Security and Communication Networks, Vol.6, No.7, pp.912-922, 2013.
    B. Tsaban, "Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography", Journal of Cryptology, Vol.28, No.3, pp.601-622, 2015.
    F. Armknecht, T. Gagliardoni, S. Katzenbeisser, et al., "General impossibility of group homomorphic encryption in the quantum world", Proc. of Public Key Cryptography 2014, Buenos Aires, Argentina, pp.556-573, 2014.
    J. Liu, A. Fan, J. Jia, et al., "Cryptanalysis of public key cryptosystems based on non-Abelian factorization problems", Tsinghua Science and Technology, Vol.21, No.3, pp.344-351, 2016.
    Felix Fontein, Michael Schneider and Urs Wagner, "PotLLL:A polynomial time version of LLL with deep insertions", Designs, Codes and Cryptography, Vol.73, No.2, pp.355-368, 2014.
    J.H. Liu, H.G. Zhang, J.W. Jia, et al., "Cryptanalysis of an asymmetric cipher protocol using a matrix decomposition problem", Science China Information Sciencs, Vol.59, No.5, pp.1-11, 2016.
    J. Shi, R. Shi, Y. Guo, et al., "Batch proxy quantum blind signature scheme", Science China Information Sciencs, Vol.56, No.5, pp.1-9, 2013.
    Michele Mosca, "Post-quantum cryptography", Proc. of PQCrypto 2014, Waterloo, ON, Canada, pp.1-282, 2014.
    S. Wang, Y. Zhu, D. Ma, et al., "Lattice-based key exchange on small integer solution problem", Science China Information Sciencs, Vol.57, No.11, pp.1-12, 2014.
    T. Hiroki, D. Eleni, T. Rob, et al., "Introduction to the issue on quantum communication and cryptography", Selected Topics in Quantum Electronics, Vol.21, No.3, pp.3-4, 2015.
    A.G. Myasnikov, V. Shpilrain, A. Ushakov, et al., Noncommutative Cryptography and Complexity of Group-theoretic Problems, Providence, RI, USA:American Mathematical Society, 2011.
    H.G. Zhang, W.B. Han, X.J. Lai, et al., "Survey on cyberspace security", Science China Information Sciences, Vol.58, No.11, pp.1-43, 2015.
    M. Habeeb, D. Kahrobaei, C. Koupparis, et al., "Public key exchange using semidirect product of (semi) groups", Proc. of the Applied Cryptography and Network Security, Banff, AB, Canada, pp.475-486, 2013.
    L. Gu and S. Zheng, "Conjugacy systems based on nonabelian factorization problems and their applications in cryptography", Journal of Applied Mathematics, Vol.2014, No.2, pp.1-10, 2014.
    D. Ezhilmaran and V. Muthukumaran, "Key exchange protocol using decomposition problem in near-ring", Gazi University Journal of Science, Vol.29, No.1, pp.123-127, 2016.
    J.H. Liu, H.G. Zhang, J.W. Jia, et al., "Cryptoanalysis of HKKS key exchange protocols", Chinese Journal of Computers, Vol.39, No.3, pp.516-528, 2016. (in Chinese).
    M. Andrecut, "A matrix public key cryptosystem",, arXiv preprint arXiv:1506.00277, pp.1-18, 2015.
    G. Anjaneyulu and A. Sanyasirao, "Distributed group key management protocol over non-commutative division semirings", Indian Journal of Science and Technology, Vol.7, No.6, pp.871-876, 2014.
    M.R. Valluri, "Zero-knowledge authentication schemes using quasi-polynomials over non-commutative Groups", Journal of Information Security and Applications, Vol.1, No.1, pp.43-47, 2014.
    G. Anjaneyulu and A. Vijayabarathi, "New digital signature scheme using multiple private keys over non-commutative division semirings",, IACR Cryptology Print Archive, pp.1-7, 2013.
    G. Anjaneyulu and M. Reddy, "Secured directed digital signature over non-commutative division semirings and Allocation of experimental registration number", International Journal of Computer Science, Vol.9, No.5, pp.376-386, 2012.
    Valluri and R. Maheswara, "Authentication schemes using polynomials over non-commutative rings", International Journal on Cryptography and Information Security, Vol.2, No.4, pp.51-57, 2012.
    A. Dwivedi, "A model of key agreement protocol using polynomials over non-commutative division semirings", Journal of Global Research in Computer Science, Vol.2, No.3, pp.40-42, 2011.
    P. Anjaneyulu and D. Padmavathamma, "New digital signature scheme using polynomials over non-commutative groups", IJCSNS, Vol.8, No.1, pp.245-249, 2008.
    Z. Cao, X. Dong and L. Wang, "New public key cryptosystems using polynomials over non-commutative rings",, IACR Cryptology ePrint Archive, pp.1-30, 2007.
    S.B. Gashkov and I.S. Sergeev, "Complexity of computation in finite fields", Journal of Mathematical Sciences, Vol.191, No.5, pp.661-685, 2013.
    J.Y. Zhao, M.Q. Wang and L. Wen, "Improved linear cryptanalysis of CAST-256", Journal of Computer Science and Technology, Vol.29, No.6, pp.1134-1139, 2014.
    N. Courtois, A. Klimov, J. Patarin, et al., "Efficient algorithms for solving overdefined systems of multivariate polynomial equations", Proc. of Eurocrypt 2000, Bruges, Belgium, pp.392-407, 2010.
    L. Niu, S.H. Tang, X. Li, et al., "Cryptanalysis of a key agreement protocol over the ring of multivariate polynomials", Journal of Computational Information Systems, Vol.10, No.13, pp.5431-5436, 2014.
    J. Faugère, "A new efficient algorithm for computing Gröbner bases (F4)", Journal of Pure and Applied Algebra, Vol.139, No.1, pp.61-88, 1999.
    Y. Sun, D. Lin and D. Wang, "On implementing signature-based Gröbner basis algorithms using linear algebraic routines from M4RI", ACM Communications in Computer Algebra, Vol.49, No.2, pp.63-64, 2015.
    J. Ding and D. Schmidt, "Solving degree and degree of regularity for polynomial systems over a finite fields", Number Theory and Cryptography, Vol.8260, No.5, pp.34-49, 2013.
    A. Rosenmann, "An algorithm for constructing Gröbner and free Schreier bases in free group algebras", Journal of Symbolic Computation, Vol.16, No.6, pp.523-549, 1993.
    D. Micciancio and P. Voulgaris, "A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations", SIAM Journal on Computing, Vol.42, No.3, pp.1364-1391, 2013.
    W. Cao and L. Hu, "Projective interpolation of polynomial vectors and improved key recovery attack on SFLASH", Designs, Codes and Cryptography, No.73, Vol.3, pp.719-730, 2014.
    P. Butkovic, Max-linear Systems:Theory and Algorithms, Springer Science and Business Media, 2010.
  • 加载中


    通讯作者: 陈斌,
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (79) PDF downloads(306) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint