Research On Lattice-based Signature Algorithms Under The Improved Standard Model

With the continuous development of quantum computing,the traditional numbertheoretic problems such as large integer factorization problem and discrete logarithm problem have been proved unable to resist quantum attacks,and the cryptosystems based on the above traditional number-theoretic problems have been greatly threatened.In this case,lattice-based cryptosystems with anti quantum attack characteristics came into being.At present,there is no polynomial time quantum algorithm that can solve some lattice problems,so using the difficult problems on the lattice to construct a new public key cryptosystem has become a hot spot in the research of cryptography at home and abroad.Digital signature is a signature verification technology in public key cryptosystem,which is widely used in the field of network information security.In order to solve the problem of large public keys and signature length in existing lattice-based signature schemes in the standard model,this thesis uses the approximate trapdoor technology to improve two lattice-based signature schemes in the standard model.The main contributions of this thesis are as follows:(1)the approximate short integer solution(Approximate SIS)problem is presented and proved to be NP-hard;(2)the approximate trapdoor generation algorithm with tag matrix and the approximate preimage sampling algorithm with tag matrix are proposed,and the correctness of the algorithms is proved;(3)a secure and efficient approximate trapdoor delegation algorithm is proposed;(4)by using the above algorithms,this thesis proposes two improved lattice-based signature schemes in the standard model.Compared with the previous schemes,the sizes of public key and signature are reduced by about half.Based on the hardness of approximate short integer solution problem,it is proved that the improved signature schemes are strongly unforgeable in the standard model.