Efficient Homomorphic Integer Polynomial Evaluation Based on GSW FHE
Husen Wang, Qiang Tang · The Computer Journal · 2017
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((logk)w+1kw⋅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 Zq and the other is for message space F2⌈logq⌉. 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 F2⌈logq⌉, we propose a solution based on symmetric-key encryption with stream ciphers.