Homomorphic Encryption (HE) makes it possible to compute on encrypted data without decryption. In lattice-based HE, a ciphertext contains noise, which accumulates along with homomorphic computations. Bootstrapping refreshes the noise and it is possible to perform arbitrary-depth computations on HE with bootstrapping, which we call Fully Homomorphic Encryption (FHE). In this article, we propose a new general bootstrapping technique for RLWE-based schemes and its practical instantiation for FHE. It can be applied to all three RLWE-based leveled FHE schemes: Brakerski-Gentry-Vaikuntanathan (BGV), Brakerski/Fan-Vercauteren (BFV), and Cheon-Kim-Kim-Song (CKKS) with minor deviations in the algorithms. Our new construction of bootstrapping extracts a noiseless ciphertext for a part of the input, scales it, and finally removes it. In contrast with previous bootstrapping algorithms, the proposed method consumes only 1–2 levels and uses smaller parameters. For BGV and BFV, our new bootstrapping does not have any restrictions on a plaintext modulus unlike typical cases of the previous methods. The error introduced by our approach for CKKS is comparable to a rescaling error, allowing us to preserve a large amount of precision after bootstrapping.

Making deep neural networks available as a service introduces privacy problems, for which homomorphic encryption of both model and user data potentially offers the solution at the highest privacy level. However, the difficulty of operating on homomorphically encrypted data has hitherto limited the range of operations available and the depth of networks. We introduce an extended CKKS scheme MatHEAAN to provide efficient matrix representations and operations together with improved noise control. Using the MatHEAAN we developed a deep sequential model with a gated recurrent unit called MatHEGRU. We evaluated the proposed model using sequence modeling, regression, and classification of images and genome sequences. We show that the hidden states of the encrypted model, as well as the results, are consistent with a plaintext model.