Paper 2018/952

Approximate Homomorphic Encryption over the Conjugate-invariant Ring

Duhyeong Kim and Yongsoo Song

Abstract

The Ring Learning with Errors (RLWE) problem over a cyclotomic ring has been the most widely used hardness assumption for the construction of practical homomorphic encryption schemes. However, this restricted choice of a base ring may cause a waste in terms of plaintext space usage. For example, an approximate homomorphic encryption scheme of Cheon et al. (ASIACRYPT 2017) is able to store a complex number in each of the plaintext slots since its canonical embedding of a cyclotomic field has a complex image. The imaginary part of a plaintext is not underutilized at all when the computation is performed over the real numbers, which is required in most of the real-world applications such as machine learning. In this paper, we are proposing a new homomorphic encryption scheme which supports arithmetic over the real numbers. Our scheme is based on RLWE over a subring of a cyclotomic ring called conjugate-invariant ring. We show that this problem is no easier than a standard lattice problem over ideal lattices by the reduction of Peikert et al. (STOC 2017). Our scheme allows real numbers to be packed in a ciphertext without any waste of a plaintext space and consequently we can encrypt twice as many plaintext slots as the previous scheme while maintaining the same security level, storage, and computational costs.

Note: Camera-ready version with minor revisions