Bootstrapping of FHE over the Integers with Large Message Space. (29th July 2018)

• Record Type: Journal Article
• Authors: Lian, Zhizhu; Hu, Yupu; Chen, Hu; Wang, Baocang
• Other Names: Lu Rongxing Academic Editor.
• Is Part Of: Security and communication networks. Volume 2018(2018)
• Publication Date: 2018-07-29
• Subjects: Computer networks -- Security measures -- Periodicals; Computer security -- Periodicals; Cryptography -- Periodicals; 005.805
• DOI: 10.1155/2018/6520258
• Languages: English
• ISSNs: 1939-0114

Abstract

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.