Efficient Homomorphic Integer Polynomial Evaluation Based on GSW FHE. (6th January 2018)

• Record Type: Journal Article
• Authors: Wang, Husen; Tang, Qiang
• Editors: Levi, Albert
• Is Part Of: Computer journal. Volume 61:Number 4(2018)
• Page Start: 575
• Page End: 585
• Publication Date: 2018-01-06
• Subjects: GSW -- homomorphic encryption -- packing -- bootstrapping; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx129
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: In this paper, we introduce new methods to evaluate integer polynomials with the Gentry-Sahai-Waters fully homomorphic encryption (GSW FHE) scheme. Our solution has much slower noise growth and per homomorphic integer multiplication cost, with a ratio O ( ( log k ) w + 1 k w ⋅ n ) in comparison to the original GSW scheme where k is the input plaintext width, n is the LWE dimension and ω = 2.373 . Technically, we reduce the integer multiplication noise by restricting the evaluation to be between two kinds of ciphertexts: one is for the message space Z q and the other is for message space F 2 ⌈ log q ⌉ . To achieve generality, we propose an integer bootstrapping scheme which converts these two kinds of ciphertexts into each other. To solve the ciphertext expansion problem due to ciphertexts in F 2 ⌈ log q ⌉, we propose a solution based on symmetric-key encryption with stream ciphers.