Focusing on the issue that current fully homomorphic encryption schemes are not practical, Gentry-Sahai-Waters (GSW) homomorphic encryption scheme was improved and a leveled fully homomorphic encryption scheme based on Ring Learning with Error (Ring-LWE) and GSW was proposed. Firstly, a basic public key encryption scheme was constructed on Ring-LWE problem, the approximate eigenvector method was used to make it have homomorphic addition and multiplication properties, and the randomized function technique was introduced to simplify the analysis of noise blow-up. Secondly, the correctness and security of the proposed scheme was proved, the correctness of homomorphic addition, multiplication and NAND operation was analyzed in detail. Finally, security parameter was set in accordance with the noise blow-up with homomorphic evaluation and the security of Ring-LWE problem, fast Fourier transformation was adopted to reduce the computational complexity of polynomial multiplication, then a leveled fully homomorphic encryption scheme was given. The size of the pubic key in new scheme is shorter than that in GSW and the computational complexity of NAND gate is reduced from Õ(( nL) ^2.37) to Õ( nL ²).

The existing (fully) homomorphic encryption schemes fail to meet practical needs for poor efficiency. To explore new resolution for better homomorphic encryption schemes, the possibility to construct homomorphism on a public key encryption scheme in literature based on Chinese Residue Theorem (CRT) was studied. The possibility of the original scheme to construct the addition and multiplication homomorphic operations was investigated. The original scheme was proved to be unsuitable for constructing homomorphic addition and multiplication operations. Several problems concerning security and efficiency existing in the original scheme were analyzed. Then a revised scheme with tougher security under proper configurations was given, as well as its correctness verification. After that, analysis on security and computing complexity of the revised scheme was given, emphasizing on its ability against the lattice reduction attack. Afterwards, the feasibility of building homomorphic operations on the revised scheme was studied and the main performance comparison between the original and the revised schemes was constructed. Finally, experience on building homomorphism was summarized and some advice on constructing an ideal (fully) homomorphic encryption scheme was presented.