Efficient Homomorphic Integer Polynomial Evaluation Based on GSW FHE. (6th January 2018) - Wang, Husen; Tang, Qiang
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.