Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (6A): 344-348.doi: 10.11896/JsJkx.190900154

• Information Security • Previous Articles     Next Articles

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).

PDF (PC)

841

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

CLC Number: 

  • 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] CHAI Hui-min, ZHANG Yong, FANG Min. Aerial Target Grouping Method Based on Feature Similarity Clustering [J]. Computer Science, 2022, 49(9): 70-75.
[2] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[3] QU Qian-wen, CHE Xiao-ping, QU Chen-xin, LI Jin-ru. Study on Information Perception Based User Presence in Virtual Reality [J]. Computer Science, 2022, 49(9): 146-154.
[4] XU Yong-xin, ZHAO Jun-feng, WANG Ya-sha, XIE Bing, YANG Kai. Temporal Knowledge Graph Representation Learning [J]. Computer Science, 2022, 49(9): 162-171.
[5] LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients [J]. Computer Science, 2022, 49(9): 183-193.
[6] LUO Xiong-feng, ZHAI Xiang-ping. Collision Avoidance Planning for Unmanned Aerial Vehicles Based on Spatial Motion Constraints [J]. Computer Science, 2022, 49(9): 194-201.
[7] LENG Dian-dian, DU Peng, CHEN Jian-ting, XIANG Yang. Automated Container Terminal Oriented Travel Time Estimation of AGV [J]. Computer Science, 2022, 49(9): 208-214.
[8] WU Zi-yi, LI Shao-mei, JIANG Meng-han, ZHANG Jian-peng. Ontology Alignment Method Based on Self-attention [J]. Computer Science, 2022, 49(9): 215-220.
[9] KONG Shi-ming, FENG Yong, ZHANG Jia-yun. Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph [J]. Computer Science, 2022, 49(9): 221-227.
[10] LIU Xing-guang, ZHOU Li, LIU Yan, ZHANG Xiao-ying, TAN Xiang, WEI Ji-bo. Construction and Distribution Method of REM Based on Edge Intelligence [J]. Computer Science, 2022, 49(9): 236-241.
[11] SUN Hui-ting, FAN Yan-fang, MA Meng-xiao, CHEN Ruo-yu, CAI Ying. Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC [J]. Computer Science, 2022, 49(9): 242-248.
[12] DOU Jia-wei. Privacy-preserving Hamming and Edit Distance Computation and Applications [J]. Computer Science, 2022, 49(9): 355-360.
[13] WU Hong-xin, HAN Meng, CHEN Zhi-qiang, ZHANG Xi-long, LI Mu-hang. Survey of Multi-label Classification Based on Supervised and Semi-supervised Learning [J]. Computer Science, 2022, 49(8): 12-25.
[14] LI Rong-fan, ZHONG Ting, WU Jin, ZHOU Fan, KUANG Ping. Spatio-Temporal Attention-based Kriging for Land Deformation Data Interpolation [J]. Computer Science, 2022, 49(8): 33-39.
[15] LI Qi-ye, XING Hong-jie. KPCA Based Novelty Detection Method Using Maximum Correntropy Criterion [J]. Computer Science, 2022, 49(8): 267-272.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.