Implementation And Analysis Of Rank Attack In Multivariate Public Key Cryptosystem

Multivariable public key cryptosystems have developed rapidly in the last 30 years,and its security is based on the difficulty problem of solving nonlinear multivariable polynomial equations.Since there is no solvable algorithm to solve this problem within polynomial time under the quantum computer model,multivariable public key cryptosystems are considered as an alternative to traditional public key cryptosystems.At present,the methods of the security analysis of the multivariable public key cryptosystems are mainly applicable to the quadratic cases,which can not be guaranteed to be equally applicable to the cubic cases.The minrank attack is a common tool to analyze the quadratic multivariable public key cryptosystems.In this thesis,we successfully apply the minrank attack to the security analysis of cubic multivariate public key cryptosystems.The main works of this thesis are as follows:1.This thesis analyzes the security of the cubic Ml cryptosystem.Compared with the MI cryptosystem,the degree of central mapping is raised from g?+1 to g?+3,and the degree of its public key polynomials is promoted from two to three.The new central mapping can avoid the linearization equations,but through in-depth analysis,it can be found that the improved schemehasaquadratic equations.After finding all the quadratic equations that satisfy the conditions,we can recover the corresponding plaintext of legal ciphertext quickly by combining with Grobner method.At the same time,it is also found that the time complexity of the minrank attack does not reach O(2222),but only O(2129).2.This thesis analyzes the security of the Cubic cryptosystem,which is an improved scheme of the classical multivariable public key cryptosystem Square.By increasing the degree of central mapping,the degree of the public key polynomials are promoted from two to three.Although the minrank attack can be extended from two-dimensional matrices to three-dimensional matrices,it is very difficult to determine the rank of a three-dimensional matrix,and it is also difficult to know the possible maximum rank.Through our thorough analysis,it can be found thatcomputing the differential of the central mapping can yield a coeff-icient matrix that is similar to the coff-icient matrix of the Square scheme.Moreover,after computingthe differential of the public polynomials of the Cubic encryption scheme,we can get a central mapping by reverse deduction,which has the same rank as the differential central mapping,so the private key can be recovered by the minrank attack.3.This thesis analyze the security of the cubic 1-cycle cryptosystem,which is an improved scheme of the classical multivariate public key cryptosystem 1-cycle.Increasing the degree of center mapping and combining the construction of the triangle in MFE system,we can resist the linearization equation attack and differential attack against 1-cycle.However,through our analysis,it can be found that the cofficient matrix of the differential central mapping has the defect of low rank.4.This thesis uses Magm software to implement all the above attacks,which proves the correctness of the theoretical analysis in this thesis.