Research And Design Of Fully Homomorphic Encryption Based On Lattice

Fully homomorphic encryption(FHE) can compute arbitrary functions on encrypted data. Such feature of FHE has significance in theory and practical application. It was proposed in 1978 and became an open hard problem in cryptography community till Gentry proposed the first FHE scheme in 2009. After that the development of FHE has made great progress. However, FHE is still facing some problems as follows. First, candidate FHE schemes are few. Second, the efficiency of FHE is a big question. Third, how to ensure the security of FHE scheme. Therefore, it is important to design and improve FHE scheme as well as estimate the parameters of FHE scheme.Lattice-based cryptography is believed to be secure against quantum computers. Lattice cryptography has become one of the most fascinating areas of mathematical cryptography. Furthermore, learn with errors problem(LWE) and ring learn with errors problem(RLWE) serve as the foundation of most lattice-based cryptographic schemes because they are simple in computations and their harness are as hard as approximating several lattice problems in the worst case. LWE and ring LWE problems are called as(ring) LWE below.In this thesis, we focus on the research of FHE based on(ring) learn with errors problem. On the one hand, we propose some FHE schemes with better parameters than previous schemes as well as the optimization from the theoretical point of view. On the other hand, we present the method to estimate the parameters of FHE schemes based on(ring) learn with errors problem from the practical point of view. We give the parameters of each scheme we present. It ensure the systematic and integrity of this thesis.1. The research of estimating the parameters of FHE schemes based on(ring) learn with errors problem. Our main method and results are as follows.(1) We present a method to estimate the parameters of FHE schemes based on(ring) learn with errors problem. In order to be consistent with the practical application, we introduce the advantage of adversary. Given security level, advantage of adversary and Gaussian parameter, the minimal dimension n can be derived from modulus q using our method. Then modulus q can be estimated by the condition of correct decryption among noise growth, circuit depth L and modulus q. Given security level, advantage of adversary and Gaussian parameter, we can obtain different modulus q and minimal dimension n corresponding different circuit depth L. From above concert parameters, the size of public key, secret key and ciphertext can be obtained. We analyze the parameters of the current FHE schemes based on(ring) learn with errors problem. It is the first to give these parameters.(2) According to the main item in the noise of the ciphertext, we present a method to classify the current FHE schemes based on(ring) learn with errors problem. For these schemes, we analyze the noise growth in detail in the homomorphic operations and give the tight bound of noise.2. The research of designing FHE schemes based on(ring) learn with errors problem. Our main method and results are as follows.(1) We present a method to design the FHE scheme without key switching based on(ring) learn with errors problem. This method we call it as lift method. The method is general. The method shows that the FHE scheme without key switching can be achieved without approximate eigenvector method(Gentry proposed in Crypto 2013). Thus the lift method has significance.(2) We present a FHE scheme without key switching based on NTRU encryption scheme. The parameters size of this scheme is smallest among all current FHE schemes.(3) We present a FHE scheme without key switching based on ring learn with errors problem. The parameters size of this scheme is smaller than GSW13 scheme on ring learn with errors problem.(4) We present a FHE scheme without key switching based on learn with errors problem. The parameters size of this scheme is smaller than GSW13 scheme on learn with errors problem.3. The research designing FHE schemes based on binary learn with errors problem as well as the optimization. Our contributions are as follows.(1) We present a FHE scheme with short public key based on binary learn with errors problem. The public key of this scheme is the shortest among all current FHE schemes based on learn with errors problem. The parameters size of this scheme is smaller than Bra12 scheme.(2) We present an optimization to reduce the key size with binary learn with errors problem so that the noise growth can be control. We improve the Bra12 scheme with this optimization.