MinRank analysis of cubic multivariate public key cryptosystem

doi:10.11772/j.issn.1001-9081.2019112052

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 Qi^1,2, NIE Xuyun^1,2

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. 电子科技大学信息与软件工程学院, 成都 610054;
2. 网络与数据安全四川省重点实验室(电子科技大学), 成都 610054

通讯作者: 张栖
作者简介:张栖(1994-),男,四川巴中人,硕士研究生,主要研究方向:网络安全、多变量公钥密码学;聂旭云(1975-),男,江西吉安人,副教授,博士,CCF会员,主要研究方向:多变量公钥密码学、大数据安全、隐私保护。
基金资助:
国家自然科学基金重点国际（地区）合作研究项目（61520106007）；四川省国际科技创新合作/港澳台科技创新合作项目（20GJHZ0273）。

Abstract

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:

TP309.7

ZHANG Qi, NIE Xuyun. MinRank analysis of cubic multivariate public key cryptosystem[J]. Journal of Computer Applications, 2020, 40(7): 1965-1969.

张栖, 聂旭云. 立方多变量公钥密码体制的最小秩分析[J]. 计算机应用, 2020, 40(7): 1965-1969.

References

[1] MATSUMOTO T,IMAI H. Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[C]//Proceedings of the 1988 Workshop on the Theory and Application of Cryptographic Techniques,LNCS 330. Berlin:Springer,1988:419-453.
[2] 胡磊, 聂旭云. 多变量公钥密码发展研究报告(2010-2014)[J]. 中国密码学会通讯,2016(2):15-22. (HU L,NIE X Y. Research report on the development of multivariable public key cryptography(2010-2014)[J]. Communication of Chinese Association for Cryptologic Research,2016(2):15-22.)
[3] KIPNIS A,SHAMIR A. Cryptanalysis of the HFE public key cryptosystem by relinearization[C]//Proceedings of the 19th Annual International Cryptology Conference,LNCS 1666. Berlin:Springer, 1999:19-30.
[4] BETTALE L,FAUGÈRE J C,PERRET L. Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic[J]. Designs,Codes and Cryptography,2013,69(1):1-52.
[5] ZHANG W,TAN C H. Algebraic cryptanalysis of Yasuda,Takagi and Sakurai's signature scheme[C]//Proceedings of the 2014 International Conference on Information Security and Cryptology. Cham:Springer,2014:53-66.
[6] ZHANG W,TAN C H. A secure variant of Yasuda,Takagi and Sakurai's signature scheme[C]//Proceedings of the 17th International Conference on Information Security and Cryptology,LNCS 8949. Cham:Springer,2014:53-66.
[7] KIPNIS A,PATARIN J,GOUBIN L. Unbalanced oil and vinegar signature schemes[C]//Proceedings of the 1999 International Conference on the Theory and Applications of Cryptographic Techniques,LNCS 1592. Berlin:Springer,1999:206-222.
[8] YASUDA T,SAKURAI K. A multivariate encryption scheme with rainbow[C]//Proceedings of the 17th International Conference on Information and Communications Security,LNCS 9543. Cham:Springer,2015:236-251.
[9] PERLNER R,PETZOLDT A,SMITH-TONE D. Total break of the SRP encryption scheme[C]//Proceedings of the 24th International Conference on Selected Areas in Cryptography, LNCS 10719. Cham:Springer,2017:355-373.
[10] IKEMATSU Y, PERLNER R, SMITH-TONE D, et al. HFERP-a new multivariate encryption scheme[C]//Proceedings of the 9th International Conference on Information and Communications Security, LNCS 10786. Cham:Springer, 2018:396-416.
[11] FAUGÈRE J C,EL DIN M S,SPAENLEHAUER P J. Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology[C]//Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. New York:ACM,2010:257-264.
[12] CLOUGH C,BAENA J,DING J,et al. Square,a new multivariate encryption scheme[C]//Proceedings of the 2009 Cryptographers'Track at the RSA Conference,LNCS 5473. Berlin:Springer,2009:252-264.
[13] 鲁刚, 聂旭云, 秦志光, 等. 一种多变量公钥密码体制的安全性分析[J]. 电子科技大学学报,2018,47(2):242-246.(LU G, NIE X Y,QIN Z G,et al. Cryptanalysis of a multivariate public key cryptosystem[J]. Journal of University of Electronic Science and Technology of China,2018,47(2):242-246.)
[14] 鲁刚. 多变量公钥密码体制的设计与安全性分析研究[D]. 成都:电子科技大学,2017:107. (LU G. Research on design and cryptanalysis of multivariate public key cryptosystem[D]. Chengdu:University of Electronic Science and Technology of China,2017:107.)
[15] HILLAR C J,LIM L H. Most tensor problems are NP-hard[J]. Journal of the ACM,2013,60(6):No. 45.
[16] PETZOLDT A,CHEN M S,DING J,et al. HMFEv-an efficient multivariate signature scheme[C]//Proceedings of the 8th International Workshop on Post-Quantum Cryptography,LNCS 10346. Cham:Springer,2017:205-223.

MinRank analysis of cubic multivariate public key cryptosystem

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	ZHANG Qilin, LI Fangwei, WANG Mingyue. Time of arrival positioning based on time reversal [J]. Journal of Computer Applications, 2021, 41(3): 820-824.
[2]	LU Rongxiu, CHEN Mingming, YANG Hui, ZHU Jianyong. Element component content dynamic monitoring system based on time sequence characteristics of solution images [J]. Journal of Computer Applications, 2021, 41(10): 3075-3081.
[3]	ZHANG Haoran, WANG Xueyuan, LI Xiaoxia. Low SNR denoising algorithm based on adaptive voice activity detection and minimum mean-square error log-spectral amplitude estimation [J]. Journal of Computer Applications, 2020, 40(6): 1763-1768.
[4]	WANG Yongbiao, ZHANG Wenxi, WANG Yahui, KONG Xinxin, LYU Tong. Speech enhancement algorithm based on MMSE spectral subtraction with Laplacian distribution [J]. Journal of Computer Applications, 2020, 40(3): 878-882.
[5]	ZHOU Fei, XIA Pengcheng. Signal strength difference fingerprint localization algorithm based on principal component analysis and chi-square distance [J]. Journal of Computer Applications, 2019, 39(5): 1405-1410.
[6]	CAO Haiyan, FENG Gui, HAN Xue, FANG Dingbang, HUANG Xinda. 3D-HEVC robust video watermarking algorithm based on depth map [J]. Journal of Computer Applications, 2019, 39(3): 869-873.
[7]	WANG Bo, LIU Deliang. Two-dimensional parameter estimation of near-field sources based on iterative adaptive approach [J]. Journal of Computer Applications, 2019, 39(2): 523-527.
[8]	TAN Yongqi, FAN Jiancong, REN Yande, ZHOU Xiaoming. Improved attribute reduction algorithm and its application to prediction of microvascular invasion in hepatocellular carcinoma [J]. Journal of Computer Applications, 2019, 39(11): 3221-3226.
[9]	LI Huimin, ZHANG Zhizhong, LI Linxiao. Channel estimation algorithm based on cell reference signal in LTE-A system [J]. Journal of Computer Applications, 2018, 38(7): 2009-2014.
[10]	SHEN Minjie, ZENG Zhenbing, LIN Wang, YANG Zhengfeng. Safety verification of stochastic continuous system using stochastic barrier certificates [J]. Journal of Computer Applications, 2018, 38(6): 1737-1744.
[11]	SUN Gongwu, XIE Jirong, WANG Junxuan. Ship course identification model based on recursive least squares algorithm with dynamic forgetting factor [J]. Journal of Computer Applications, 2018, 38(3): 900-904.
[12]	LI Yuan, WU Haoyu, ZHANG Cheng, FENG Liwei. Multi-modal process fault detection method based on improved partial least squares [J]. Journal of Computer Applications, 2018, 38(12): 3601-3606.
[13]	XU Lingkai, YANG Rennong, ZUO Jialiang. Air target threat assessment based on improved ACPSO algorithm and LSSVM [J]. Journal of Computer Applications, 2017, 37(9): 2712-2716.
[14]	ZHENG Yifeng, HAO Xueyuan, YAN Xiaohong. New least mean square algorithm with variable step based on underwater acoustic communication [J]. Journal of Computer Applications, 2017, 37(8): 2195-2199.
[15]	XU Wenchao, WANG Guangyan, CHEN Lei. Speech enhancement algorithm based on improved variable-step LMS algorithm in cochlear implant [J]. Journal of Computer Applications, 2017, 37(4): 1212-1216.