Research On Some Kinds Of Multivariate Digital Signature Schemes

The security of multivariate digital signature is based on the problem of solving nonlinearequations in the finite field which has been proved to be a NPC problem,there is no quantumcomputing algorithms to solve this problem in polynomial time.In this paper, some kinds ofmultivariate digital signature schemes are researched, the main results are as follows:1.The security analysis and improvement of Little Dragon Two.The central map of Littledragon two is analyzed,an efficient attack algorithm is given using the information of private keyleaked by the combination of input and output of the central map and the character of differenceof the central map,the computational complexity of which is O （log²（q） n⁶）（n is the number ofinput variables， q is the order of the finite field）;the central map of Little dragon two isre-designed by using the method of external disturbance.The structural defects of previousscheme’s central map are overcame. It is proved that the new scheme can resist high order linearequation attack, rank attacks, XL&Gr bner basis attack, differential attack.2.The research on multivariate digital signature based on mixing two schemes. The methodof designing central map using two kinds of multivariate public key schemes is gived, thestructural defects of previous schemes are overcame.A M-T multivariate digital signature isproposed based on MI and TPM using this method.With the parameterq=2=8, n=11, u=1, r=2,it is proved that the new scheme can resist high order linear equation attack, rank attacks,XL&Gr bner basis attack, differential attack and the security level of this scheme is O(2⁸⁰),signature length is176bit, private key storage size is2KB,which is better than Rainbow andSflash.3.The research on the models of multivariate digital signature shemes. The design methodof the models of multivariate digital signature shemes is researched.First,the security ofmultivariate digital signature models based on secret affine transformation is analyzed，themessage v and the verification middle value wgive the affine transformationT N^-1,soP₁=T ο F ο S Scan be calculated through P2,and the security of this models is degenerated to themultivariate digital signature sheme with private keyT、Sand public key P₁=T ο F ο S，;then thesecret nonlinear transformation is used to replace the affine transformation Tto achieve thedivision of the direct relationship of private key and public key,so the multivariate digitalsignature models based on secret nonlinear transformation is proposed to lift the security level ofmltivariate digital signature scheme.