Research On Design And Cryptanalysis Of Multivariate Public Key Cryptosystem

With the development of the research on quantum computation,post-quantum public key cryptography has become one hot point in cryptography research.Multivariate public key cryptography is one of the branches of post-quantum public key cryptography.Since there is no proper provable security method for multivariate public key cryptosystem,the security of multivariate public key cryptosystem depends on resisting the existing attack method.At present,due to various algebraic attacks,most quadratic multivariate public key cryptosystems can not be both efficient and secure.In this thesis,we firstly presented the cryptanalysis of some existing multivariate public key cryptosystems,and then we proposed a series of cubic multivariate public key cryptosystems by raising the degree from two to three,which ensure the schemes can be secure against existing attacks.(1)We broke a multivariate public key cryptosystem similar to the l-reversible cycle scheme by linearization equations attack combined with differential attack.Similar to l-reversible cycle scheme,this system also satisfy the linearization equation.After finding all linearization equations,given a valid ciphertext,the original system will be degenerated to Square cryptosystem,which can be broken by differential attack.Then we presented the cryptanalysis of 2 instances of extended multivariate public key cryptosystem by combining the quadratization equation with direct attack method.After finding all quadratization equations,given a valid ciphertext,we can reduce the degree of regularity in the process of solving the system in direct attack,so as to the computation complexity.(2)We proposed a Cubic MFE public key cryptosystem and a digital signature scheme.In these schemes,the product of three two order matrices is designed to construct the cubic polynomials in the central map,and the determinants of the two order matrice were used as the lock polynomials to hide the triangle structure in the central map.When the degree of public key polynomials is raised from two to three,the linearization equations can be avoided effectively,and also the direct attack will be not work.Compared with the Cubic simple matrix encryption scheme,the proposed schemes has smaller key sizes.(3)We proposed the cubic unbalanced oil and vinegar signature system.In thecubic unbalanced oil vinegar system,there exists many cross terms of oil variables,which can resist oil-vinegar separation attack.Furthermore,the number of vinegar variables can be less than the number of oil variables.Compared with the quadratic unbalanced oil vinegar signature system,the signature length of the cubic scheme is much shorter,and the time of key generations is also shorter.Selecting the appropriate parameters,the scheme can also resist the rank attacks and the direct attacks.(4)We proposed two cubic multivariate digital signature schemes.The central map in the first scheme is cubic mapping.Combined with the projection method and minus method,the first scheme can resist the differential attack.And also the system can withstand the other existing attacks with proper parameters.The central map in the second scheme is similar to l-reversible cycle scheme,but the degree is three not two.This improvement can avoid the linearization equations.This scheme can also resist differential attack,direct attack with the appropriate parameters.All cryptosystems and cryptanalysis in this thesis were implemented by Magma on PC.Our works can provide new ideas for the design and the cryptanalysis of multivariate public key cryptosystems.