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

Available format(s)
Publication info
Published elsewhere. MAJOR revision.The 21st Annual International Conference on Information Security and Cryptology (ICISC 2018)
Keywords
ring learning with errorshomomorphic encryptionreal number arithmetic
Contact author(s)
yongsoosong @ ucsd edu
History
2018-10-29: revised
See all versions
Short URL
https://ia.cr/2018/952

CC BY

BibTeX

@misc{cryptoeprint:2018/952,
author = {Duhyeong Kim and Yongsoo Song},
title = {Approximate Homomorphic Encryption over the Conjugate-invariant Ring},
howpublished = {Cryptology ePrint Archive, Paper 2018/952},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/952}},
url = {https://eprint.iacr.org/2018/952}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.