Cryptology ePrint Archive: Report 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.

Category / Keywords: ring learning with errors, homomorphic encryption, real number arithmetic

Original Publication (with major differences): The 21st Annual International Conference on Information Security and Cryptology (ICISC 2018)

Date: received 5 Oct 2018, last revised 28 Oct 2018

Contact author: yongsoosong at ucsd edu

Available format(s): PDF | BibTeX Citation

Note: Camera-ready version with minor revisions

Version: 20181029:015054 (All versions of this report)

Short URL: ia.cr/2018/952