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 ciphertexts, together with the rescaling procedure for managing the magnitude of plaintext. This procedure rescales the ciphertext modulus to a smaller size, which results in rounding of plaintext after homomorphic operations. The main idea is to place a noise after the signicant gures 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 algorithm for our Ring-LWE based construction. In the previous schemes a message has a noise multiplied by the characteristic of the plaintext space and so can be easily annihilated after reversing a packing algorithm. However, it does not work for our scheme with a plaintext of characteristic zero. Instead, we embed messages into Gaussian integers and adopt an isometric ring homomorphism for packing messages, which preserves the size of error and so enables us to remove the errors in the decryption procedure. Specically, a vector of plaintext values is converted into a complex polynomial via the canonical embedding and then discretized to a polynomial over the Gaussian integers. 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 oating-point operations. In addition to the basic approximate circuits, we show that our scheme can be applied to eciently evaluate transcendental functions such as multiplicative inverse, exponentiation, and even fast Fourier transform.