计算机科学 ›› 2020, Vol. 47 ›› Issue (6A): 344-348.doi: 10.11896/JsJkx.190900154

• 信息安全 • 上一篇    下一篇

三次MI多变量公钥密码体制的安全性分析

张栖, 聂旭云   

  1. 电子科技大学信息与软件工程学院 成都 610054;
    网络与数据安全四川省重点实验室 成都 610054
  • 发布日期:2020-07-07
  • 通讯作者: 聂旭云(xynie@uestc.edu.cn)
  • 作者简介:1106845293@qq.com
  • 基金资助:
    国家自然基金重点国际(地区)合作研究项目(61520106007);四川省国际科技创新合作/港澳台科技创新合作项目(20GJHZ0273)

Cryptanalysis of Cubic MI Multivariate Public Key Signature Cryptosystem

ZHANG Qi and NIE Xu-yun   

  1. University of Electronic Science and Technology of China,Sichuan Key Laboratory of Network and Data Security,Chengdu 610054,China
    Sichuan Key Laboratory of Network and Data Security,Chengdu 610054,China
  • Published:2020-07-07
  • About author:ZHANG Qi, born in 1994, master degree candidate.His main research interests include network security, multivariate public key cryptograghy.
    NIE Xu-yun, born in 1975, Ph.D, associate professor.His main research interests include multivariate public key cryptography, big data security and privacy protection.
  • Supported by:
    This work was supported by MaJor International (Regional) Joint Research ProJect of China National Science Foundation (61520106007) and International Scientific and Technological Innovation Cooperation ProJect in Sichuan Province (20GJHZ0273).

摘要: 三次MI多变量公钥签名体制是经典的多变量密码体制MI体制的改进。通过增加中心映射的次数,将公钥多项式从二次提升到三次来抵抗针对MI体制的线性化方程攻击。文中声称其体制的中心映射虽然满足二次化方程,但对其安全性没有影响。然而经过实验分析,对于以其中心映射构造的公钥加密体制,在找到所有的二次化方程后,结合Grobner基方法即可快速恢复合法密文相应的明文。同时,分析表明其方案实例抵抗最小秩攻击的时间复杂度并没有达到作者声称的O(2222),仅仅只有O(2129)。

关键词: MI, 多变量公钥密码体制, 二次化方程, 秩攻击

Abstract: Cubic MI multivariate public key cryptosystem is an improvement of the classical multivariate public key cryptosystem MI.By increasing the degree of central mapping,the degree of public polynomial is promoted from quadratic to cubic to resist the Linearized Equation attack against MI system.The authors claim that the central mapping of the system satisfies the quadratic equation but has no effect on its security.However,through experimental analysis,for the public key cryptography constructed by its central mapping,after finding all the quadratic equations,the corresponding plaintext of the valid ciphertext can be recovered quickly by combining with the Grobner basis method.Simultaneously,it is also found that the complexity of the scheme instance to resist the minimum rank attack does not reach O(2222),but only O(2129).

Key words: MI, Multivariate public key cryptosystem, Quadratization equation, Rank attack

中图分类号: 

  • TP309.7
[1] MATSUMOTO T,IMAI H.Public Quadratic Polynomial-Tup-les for Efficient Signature-Verification and Message-Encryption.Advances in Cryptology-EUROCRYPT’88,1988:419-453.
[2] PATARIN J.Hidden Fields Equations (HFE) and Isomor-phisms of Polynomials (IP):Two New Families of Asymmetric Algorithms//International Conference on the Theory and Application of Cryptographic Techniques.Springer,Berlin,Heidelberg,1996:33-48.
[3] PATARIN J,GOUBIN L,COURTOIS N.C-+* and HM:Variations Around Two Schemes of T.Matsumoto and H.Imai//International Conference on the Theory and Application of Cryptology and Information Security.Springer,Berlin,Heidelberg,1998:35-50.
[4] DUBOIS V,FOUQUE P A,STERN J.Cryptanalysis ofSFLASH with Slightly Modified Parameters//Proceedings of the 26th annual international conference on Advances in Cryptology.Springer,2007:264-275.
[5] DING J,DUBOIS V,YANG B Y,et al.Could SFLASH be repaired?//International Colloquium on Automata,Languages,and Programming.Springer-Verlag,2009:691-701.
[6] SHUAI T Q,HAN W B,LI Y F,et al.Construction of extended multivariate public key cryptosystems.International Journal of Network Security,2016,18(1):60-67.
[7] LU G,XUE L Y,NIE X Y,et al.Cryptanalysis of Novel Extended Multivariate Public Key Cryptosystem with Invertible Cycle.International Journal of Network Security,2018,20(3):509-514.
[8] KIPNIS A,SHAMIR A.Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization.Advances in Cryptology-CRYPTO’99,Lecture Notes in Computer Science,1999,1666:19-30.
[9] BETTALE L,JEAN-CHARLES F,PERRET L.Cryptanalysis of HFE,multi-HFE and variants for odd and even characteristic.Designs,Codes and Cryptography,2013,69(1):1-52.
[10] BAENA J,CABARCAS D,ESCUDERO D E,et al.Rank Analysis of Cubic Multivariate Cryptosystems//International Conference on Post-quantum Cryptography.Springer,Cham,2018:355-374.
[11] YUAN F,ZHAO S,OU H,et al.A New Public Key Signature Scheme Based on Multivariate Polynomials//Web Information Systems and Mining.Springer Berlin Heidelberg,2012:239-245.
[12] CAO W W,NIE X Y.Cryptanalysis of Two Quartic Encryption Scheme and One Improved MFE Scheme//International Conference on Post-quantum Cryptography.Springer Berlin Heidelberg,2010:41-60.
[13] DING J,SCHMIDT D.Multivariate public key cryptosystems//Springer Science Business Media.LLC,2006:44-63.
[1] 吴苏洁, 周杰, 王学英, 吕智康, 邵根富.
降雨环境下毫米波MIMO信道特性研究
Study on Characteristics of Millimeter-wave MIMO Channel in Rainfall Environment
计算机科学, 2022, 49(7): 297-303. https://doi.org/10.11896/jsjkx.210600075
[2] 张翕然, 刘万平, 龙华.
物联网僵尸网络病毒的传播动力学模型与分析
Dynamic Model and Analysis of Spreading of Botnet Viruses over Internet of Things
计算机科学, 2022, 49(6A): 738-743. https://doi.org/10.11896/jsjkx.210300212
[3] 蒋锐, 徐姗姗, 徐友云.
一种新的基于子连接结构的混合预编码算法
New Hybrid Precoding Algorithm Based on Sub-connected Structure
计算机科学, 2022, 49(5): 256-261. https://doi.org/10.11896/jsjkx.210300138
[4] 吕由, 吴文渊.
基于同态加密的线性系统求解方案
Linear System Solving Scheme Based on Homomorphic Encryption
计算机科学, 2022, 49(3): 338-345. https://doi.org/10.11896/jsjkx.201200124
[5] 线岩团, 高凡雅, 相艳, 余正涛, 王剑.
融合多策略数据增强的低资源依存句法分析方法
Improving Low-resource Dependency Parsing Using Multi-strategy Data Augmentation
计算机科学, 2022, 49(1): 73-79. https://doi.org/10.11896/jsjkx.210900036
[6] 冷悦, 谢亚琴, 李鹏.
卫星双极化MIMO系统极化鉴别率影响分析
Effect of Cross-polarization for Dual-polarized MIMO Channel in Satellite Communications
计算机科学, 2021, 48(6A): 414-419. https://doi.org/10.11896/jsjkx.200900173
[7] 刘丹, 赵森, 颜志良, 赵静, 王会青.
基于堆叠自动编码器的miRNA-疾病关联预测方法
miRNA-disease Association Prediction Model Based on Stacked Autoencoder
计算机科学, 2021, 48(10): 114-120. https://doi.org/10.11896/jsjkx.200900169
[8] 杨春德, 贾竹, 李欣蔚.
基于U-Net++的心电信号识别分类研究
Study on ECG Signal Recognition and Classification Based on U-Net++
计算机科学, 2021, 48(10): 121-126. https://doi.org/10.11896/jsjkx.200700103
[9] 李亚男, 胡宇佳, 甘伟, 朱敏.
基于深度学习的miRNA靶位点预测研究综述
Survey on Target Site Prediction of Human miRNA Based on Deep Learning
计算机科学, 2021, 48(1): 209-216. https://doi.org/10.11896/jsjkx.191200111
[10] 邵超, 马进家.
基于Xie-Beni指数的选择性聚类集成
Selective Clustering Ensemble Based on Xie-Beni Index
计算机科学, 2020, 47(6A): 457-460. https://doi.org/10.11896/JsJkx.190700044
[11] 陈钱, 周杰, 邵根富.
角度域任意功率谱MIMO信道特征计算
MIMO Channels with Arbitrary AoA Power Spectrum for Various Wireless Environments
计算机科学, 2020, 47(6): 271-275. https://doi.org/10.11896/jsjkx.190500022
[12] 李豪,崔新凯,高向川.
大规模MIMO室外无线光通信系统中基于分段高斯近似的最大似然盲检测算法
Maximum Likelihood Blind Detection Algorithm Based on Piecewise Gaussian Approximation for Massive MIMO Outdoor Wireless Optical Communication Systems
计算机科学, 2020, 47(3): 255-260. https://doi.org/10.11896/jsjkx.190200310
[13] 陈曦, 冯梅, 江波.
Kaminsky攻击及其异常行为分析
Analysis of Kaminsky Attack and Its Abnormal Behavior
计算机科学, 2020, 47(11A): 396-401. https://doi.org/10.11896/jsjkx.200100060
[14] 廖勇, 杨馨怡, 夏茂菡, 王博, 李守智, 沈轩帆.
高速移动场景下基于贪婪算法的改进模代数预编码
Improved Tomlinson-Harashima Precoding Based on Greedy Algorithm in High-speed Mobile Scenarios
计算机科学, 2019, 46(8): 121-126. https://doi.org/10.11896/j.issn.1002-137X.2019.08.020
[15] 高沙沙, 王中华.
基于MILS架构的嵌入式操作系统多级安全域动态管理技术
Dynamical Management Technology of Multi-Level Security Domain for Embedded Operating System Based on MILS
计算机科学, 2019, 46(11A): 460-463.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!