Encryption Algorithm Based On Module-LWE

Quantum computers are developing rapidly,if the number of qubits is sufficient,the quantum Shor algorithm can solve the integer decomposition and discrete logarithm problem in polynomial time.All traditional cryptosystems based on two kinds of problems will be insecure.It takes exponential time for the best known quantum algorithms to solve lattice problems.Lattice cryptography is expected to cope with the attacks of quantum computers and quantum algorithms.Therefore,lattice cryptography has become a research hotspot in the field of information security.Kyber,a key exchange algorithm based on MLWE,is one of the latest lattice encryption algorithms.The encryption efficiency is much higher than the encryption algorithm based on LWE problem and RLWE problem.However,since the algorithm is mainly applied to key encapsulation,there is a disadvantage that the plaintext space is small and the ciphertext expansion rate is large.The first part of the thesis is to improve Kyber algorithm.The new encryption parameter dp is introduced into the Kyber encryption algorithm to expand the plaintext space and reduce the ciphertext expansion rate.In the process of improvement,three key problems have been solved.First,the influence of dp on the correctness of the encryption algorithm is analyzed through strict theoretical derivation and implementation.Second,the ciphertext expansion rate is reduced by optimizing the encryption parameters.Third,the polynomial multiplication is performed by the fast Fourier transform on the complex domain based on the floating-point operation,which avoids the large integer polynomial multiplication on the increased finite field,ensures the computational efficiency of the improved algorithm.And the error caused by floating-point arithmetic is analyzed.The improved algorithm was implemented in C++ and compared with Kyber's experimental data.The ciphertext expansion rate was reduced from 1:25 to 1:4.25.Homomorphic inner product has a wide range of applications in secure multiparty computing,private data mining,outsourced computing,and ranked ciphertext retrieval.However,the most of the existing schemes for computing homomorphic inner product are based on RLWE homomorphic encryption schemes,which generally have the problem of inefficiency.In order to solve the above problems,the second part of the thesis is to construct a MLWE homomorphic product scheme based on the first part's improved algorithm.In this process,three key problems have been solved.First,the tensor product operation on the ciphertext space is given,which corresponding to the integer vector inner product operation on the plaintext space;Second,due to the introduction of the tensor operation,the encryption noise of the homomorphic inner product scheme is changed compared with the improved algorithm proposed in the first part of the thesis,so the correctness and security of the scheme are reanalyzed;Third,two optimized encryption parameters are given,which correspond to the application scenarios of calculating the homomorphic inner product of two different sizes of integer vectors.The scheme was implemented in C++ and large integer calculation library NTL.Compared with other homomorphic encryption schemes,this scheme can efficiently calculate the homomorphic inner product of integer vectors.