立方多变量公钥密码体制的最小秩分析  

MinRank analysis of cubic multivariate public key cryptosystem

作　　者：张栖 聂旭云[1,2] ZHANG Qi;NIE Xuyun(School of Information and Software Engineering,University of Electronic Science and Technology of China,Chengdu Sichuan 610054,China;Sichuan Key Laboratory of Network and Data Security(University of Electronic Science and Technology of China),Chengdu Sichuan 610054,China)

机构地区：[1]电子科技大学信息与软件工程学院,成都610054 [2]网络与数据安全四川省重点实验室(电子科技大学),成都610054

出　　处：《计算机应用》2020年第7期1965-1969,共5页journal of Computer Applications

基　　金：国家自然科学基金重点国际(地区)合作研究项目(61520106007);四川省国际科技创新合作/港澳台科技创新合作项目(20GJHZ0273)。

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

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

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]