On the exact decryption range for Gentry–Halevi's implementation of fully homomorphic encryption

Journal of mathematical cryptology

article

Masaya Yasuda¹  Kazuhiro Yokoyama²  Takeshi Shimoyama¹  Jun Kogure¹  Takeshi Koshiba³ 

[1] Fujitsu Laboratories Ltd.;Department of Mathematics, Rikkyo University;Division of Mathematics, Graduate School of Science and Engineering, Saitama University

关键词: Fully homomorphic encryption;    ideal lattices;    bootstrapping method;    re-encryption process;   

DOI  :  10.1515/jmc-2013-0024

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

In this paper, we revisit the fully homomorphic encryption (FHE) scheme implemented by Gentry and Halevi, which is just an instantiation of Gentry's original scheme based on ideal lattices. Their FHE scheme starts from a somewhat homomorphic encryption (SHE) scheme, and its decryption range is deeply related with the FHE construction. Gentry and Halevi gave an experimental evaluation of the decryption range, but theoretical evaluations have not been given so far. Moreover, we give a theoretical upper bound, and reconsider suitable parameters for theoretically obtaining an FHE scheme. In particular, while Gentry and Halevi use the Euclidean norm evaluation in the noise management of ciphertexts, our theoretical bound enables us to use the ∞-norm evaluation, and hence it helps to lower the difficulty of controlling the noise density of ciphertexts.

【 授权许可】

CC BY|CC BY-NC-ND