Paper 2016/421

Homomorphic Encryption for Arithmetic of Approximate Numbers

Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song

Abstract

We suggest a method to construct a homomorphic encryption scheme for approximate arithmetic. It supports approximate addition and multiplication of encrypted messages, together with the rescaling procedure for managing the magnitude of plaintext. This procedure truncates a ciphertext into a smaller modulus, which results in rounding of plaintext after homomorphic operations. The main idea is to place a noise after the significant figures of message. This noise is added to the plaintext for security, but considered to be part of error occurred during approximate computations, which is reduced along with plaintext by rescaling. As a result, our decryption structure outputs an approximate value of plaintext with the predetermined precision. We also propose a new batching method for RLWE-based construction. A plaintext polynomial of characteristic zero is mapped to a message vector of complex numbers via complex canonical embedding map which is an isometric ring homomorphism. The size of error is preserved during transformation and so it enables us to remove the errors after decryption procedure. Our construction has the bit size of ciphertext modulus linear in the circuit depth due to rescaling procedure while all the previous works either require exponentially large size of modulus or expensive computations such as bootstrapping or bit extraction. One important feature of our method is that the precision loss during evaluation is bounded by circuit depth and it is at most one more bit compared with unencrypted approximate arithmetic such as floating-point operations. In addition to the basic approximate circuits, we show that our scheme can be applied to efficiently evaluate the transcendental functions such as multiplicative inverse, exponential function, logistic function, and discrete Fourier transform.