Research On Cryptographic Schemes From Lattice Assumptions

With the application of quantum computers,researching a class of public key cryptosystems which can resist the attack of quantum computer is imminent and attracts much attention of scholars.Lattice-based cryptography,as a typical representative of post-quantum cryptography,has become the focus of attention of many scholars,because there is no effective quantum algorithm to solve it due to its structural characteristics.Lattice-based cryptography is based on the NP-hard problem of lattice.Compared with traditional publickey cryptography,lattice-based cryptography has the advantages of resisting attacks from quantum computer,provable security,simple operation and the worst-case to average-case reductions.This dissertation mainly studies the basic problems of lattice-based cryptography,including: generating hard random lattice with short bases,trapdoor functions,lossy trapdoor functions and so on.The concrete content is summarized as follows:1.For the short bases problem on lattice,the dissertation gives a simple and widely used new construction of hard random lattices with short bases by using a fact about matrices,a regular theorem on integers and corollary of regular theorem.Firstly,an important property of matrix is given and proved.Then,the regular theorem on integers is proved and its corollary is given.Finally,a hard random lattices with short bases is constructed.The base-matrix in our construction is a block matrix whose contains four matrix parts,and the element composition of these four matrix parts is given.Finally,the quality of the scheme is analyzed,that is,the norm of the short base in the scheme.The selection of these four matrix parts ensures that the norm of the base matrix is within a smaller bound.Compared with the existing schemes,our hard random lattice with short bases in this dissertation does not use the sampling method of the elements of random matrix in existing schemes and uses Gaussian sampling.This makes the proposed algorithm have wider applications in cryptography.2.A new trapdoor function based on the LWE problem over ring is proposed in this dissertation by establishing the random matrix on the ring.At the same time,the corresponding inversion algorithm is given,which includes two sub-algorithms: trapdoor inversion algorithm and iterative inversion algorithm.Compared with existing trapdoor function schemes,the trapdoor function proposed in this dissertation has larger throughput and expands the parameter,that is,the prime number 2 is extended to arbitrary prime number p,and which makes our scheme more efficient and widely used.3.Based on the polynomial LWE assumption,an efficient encryption algorithm is first proposed in this dissertation and based on the encryption algorithm a class of trapdoor functions is constructed.The lossy trapdoor function can also be constructed by using the encryption algorithm in this dissertation.In the process of encrypting the matrix,the encryption algorithm uses only one vector as the key and one vector as the random vector.Thus,the key quantity and random quantity are saved.Comparing with the existing schemes,it is found that the proposed scheme has many advantages,such as larger input bits,higher efficiency and so on.