Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (7): 1965-1969.DOI: 10.11772/j.issn.1001-9081.2019112052

• Cyber security • Previous Articles     Next Articles

MinRank analysis of cubic multivariate public key cryptosystem

ZHANG Qi1,2, NIE Xuyun1,2   

  1. 1. School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 610054, China;
    2. Sichuan Key Laboratory of Network and Data Security(University of Electronic Science and Technology of China), Chengdu Sichuan 610054, China
  • Received:2019-12-03 Revised:2020-03-25 Online:2020-07-10 Published:2020-05-19
  • Supported by:
    This work is partially supported by the Major International (Regional) Joint Research Project of the National Natural Science Foundation of China (61520106007), the International Scientific and Technological Innovation Cooperation Project/Scientific and Technological Innovation Cooperation Project with Hong Kong, Macao and Taiwan in Sichuan Province (20GJHZ0273).


张栖1,2, 聂旭云1,2   

  1. 1. 电子科技大学 信息与软件工程学院, 成都 610054;
    2. 网络与数据安全四川省重点实验室(电子科技大学), 成都 610054
  • 通讯作者: 张栖
  • 作者简介:张栖(1994-),男,四川巴中人,硕士研究生,主要研究方向:网络安全、多变量公钥密码学;聂旭云(1975-),男,江西吉安人,副教授,博士,CCF会员,主要研究方向:多变量公钥密码学、大数据安全、隐私保护。
  • 基金资助:

Abstract: The cubic cryptosystem is the improvement of the classical multivariable cryptosystem Square. By increasing the degree of central mapping from square mapping to cubic mapping, the public key polynomial was promoted from quadratic to cubic in order to resist the MinRank attack against the quadratic multivariable public key cryptosystem. Aiming at this system, a MinRank attack combining with difference was proposed to recover its private key. Firstly, the central mapping difference of the system was analyzed, and its rank was determined according to the structure after difference. Then, the difference of the public key was solved and the coefficient matrices of the quadratic term were extracted. After that, a MinRank problem was constructed by the coefficient matrix and the determined rank. Finally, the extended Kipnis-Shamir method was combined to solve the problem. The experimental results show that the private key of cubic cryptosystem can be recovered by using MinRank attack.

Key words: multivariable public key cryptosystem, Square, MinRank attack, MinRank problem, Kipnis-Shamir attack

摘要: 立方加密体制是经典的多变量公钥密码体制Square的改进方案,其中心映射由平方映射改为了立方映射,由此将公钥多项式从二次提升到三次来抵抗针对二次多变量公钥密码体制的最小秩攻击。针对这种体制,提出一种结合差分的最小秩攻击,旨在恢复它的私钥。首先,分析体制的中心映射差分,并根据差分后的结构来确定它的秩;然后,求解公钥差分,并提取二次项的系数矩阵;接着,由系数矩阵以及确定的秩构造一个最小秩问题;最后,结合扩展的Kipnis-Shamir方法对问题进行求解。实验结果表明,利用最小秩攻击可以恢复立方加密体制的私钥。

关键词: 多变量公钥密码体制, Square, 最小秩攻击, 最小秩问题, Kipnis-Shamir攻击

CLC Number: