Homomorphic Encryption for Approximate Arithmetic

Abstract

Homomorphic encryption is a cryptosystem which allows us to perform an arithmetic of encrypted data. The technology of homomorphic encryption has a tremendous possibilities in real world applications based on secure outsourcing of computation on public server. However, previous schemes had a common limitation in approximate arithmetic such as real number operations.

In this paper we suggest a method to construct a homomorphic encryption scheme for approximate arithmetic. It supports an approximate addition and multiplication of encrypted messages, together with a new rescaling procedure for managing the magnitude of plaintext. The main idea is to add a noise following significant figures which contain a main message. This noise is originally added to the plaintext for security, but considered to be a part of error occurring during approximate computations that is reduced along with plaintext by rescaling. Consequently, the bit size of ciphertext modulus grows linearly with the depth of the circuit being evaluated due to rescaling procedure, compared to an exponentially large size of previous works. We also propose a new batching technique for a RLWE-based construction. A plaintext polynomial will be mapped to a vector of complex numbers via complex canonical embedding map, which is an isometric ring homomorphism. We show that our scheme can be applied to the efficient evaluation of circuits of approximate numbers including transcendental functions such as multiplicative inverse, exponential function, logistic function and discrete Fourier transform.

We extend the leveled homomorphic encryption scheme into a fully homomorphic encryption. Namely, we propose a new technique to refresh low-level ciphertexts based on Gentry's bootstrapping process. The bootstrapping procedure is required to evaluate the decryption formula homomorphically using arithmetic operations over the integers, and the modular reduction becomes the main bottleneck in bootstrapping. We exploit a scaled sine function as an approximation of the modular reduction circuit and present an efficient strategy to evaluate trigonometric functions recursively. Our method requires only two homomorphic multiplications at each iteration and the computation cost grows linearly with the depth of the decryption formula. We also show how to bootstrap packed ciphertexts on RLWE construction with a proof of concept implementation.

We prove the efficiency of our scheme by applying it to real-world applications. Specifically we use our open source homomorphic encryption library to learn a model of logistic regression using biomedical data. We show that our scheme can evaluate the gradient descent method with 20~25 iterations in a few hours.