Research On Sampling Algorithms And Applications Based On LWE Problem

With the continuous development of research on quantum computation,the emergence of quantum computer will no longer be empty talk,so the research of new cryptosystem which against quantum attacks has become hotspot.A lot of problems on lattice have been proved to be difficult,and in polynomial time,cannot be solved by quantum computation,so there is a lot of design of cryptosystem based on the difficult problems on lattice.LWE(Learning with error)problem is one of difficult problems on lattice,and security of cryptography system which based on LWE problem can be guaranteed.The sampling efficiency of LWE problem influence application of the corresponding cryptosystem's efficiency.Based on this issue,in this paper,LWE problem's sampling algorithm is studied.In LWE problem,the error factor of LWE problem takes up the most of time of sampling,and the sampling algorithm of LWE problem is flexible,so the research of sampling about the error factor is the main content of research of LWE problem's sampling algorithm.The error factor of LWE problem is sampled from discrete Gaussian distribution,so the research of sampling algorithm on discrete Gaussian distribution is the main target in this paper.In order to design a new and effective LWE problem's sampling algorithm,we first studied the existing LWE problem's sampling algorithms,through the realization of the algorithms we found that the algorithm with best comprehensive properties of the existing LWE problem's sampling algorithms is discrete Ziggurat sampling algorithm,so we focus on this algorithm.Based on the thought of sampling on lattice can be converted to sampling on integer domain,we proposes a new LWE problem's sampling algorithm,which optimize the process of sampling from discrete Gaussian distribution on integer domain.Through the comparison of the new sampling algorithm and discrete Ziggurat sampling algorithm,we found the sampling speed of optimized sampling algorithm in this paper is two times faster than discrete Ziggurat sampling algorithm.A-LWE problem is an extension of LWE problem,which augment the function of information embedded,so the research of secure encryption scheme based on A-LWE problem compared with the existing secure encryption scheme based on LWE problem has more research value.In this paper,the new LWE problem's sampling algorithm is used in the three secure encryption schemes based on A-LWE problem,the experimental results show that in those secure encryption schemes,the efficiency can be improved about 10%-20%with the use of the new LWE problem s sampling algorithm compare to the use of the existing sampling algorithm.