Bootstrapping of FHE over the Integers with Large Message Space. (29th July 2018) - Lian, Zhizhu; Hu, Yupu; Chen, Hu; Wang, Baocang
Abstract : For the decryption of the fully homomorphic encryption (FHE) over the integers with the message space Z Q, Nuida and Kurosawa proposed a Q 4 λ -multiplicative-degree circuit to compute it at Eurocrypt 2015, where λ is the security parameter and the message size Q is a constant. Since the degree of the decryption circuit is polynomial in Q, the range of the message size Q is limited. In this work, we solve this open problem as long as Q is large enough (larger than λ ). We represent the decryption circuit as a arithmetic polynomial of multiplicative degree 108 · λ   l o g 3 λ, which is independent of the message size Q except a constraint Q > λ . Moreover, the bootstrapping process requires only O ( λ · log ⁡ λ ) number of multiplications to implement the decryption circuit, which is significantly lower than O ( λ 4 ) of Nuida and Kurosawa's work. We also show the efficiency of the FHE scheme with message space Z Q compared to the FHE scheme with binary message space. As a result, we have that the former is preferable.