**Fully Homomorphic Encryption with k-bit Arithmetic Operations**

*Benjamin M. Case and Shuhong Gao and Gengran Hu and Qiuxia Xu*

**Abstract: **We present a fully homomorphic encryption scheme continuing the line of works
of Ducas and Micciancio (2015, [DM15]), Chillotti et al. (2016, [CGGI16a]; 2017,
[CGGI17]; 2018, [CGGI18a]), and Gao (2018,[Gao18]). Ducas and Micciancio (2015)
show that homomorphic computation of one bit operation on LWE ciphers can be done
in less than a second, which is then reduced by Chillotti et al. (2016, 2017, 2018) to
13ms. According to Chillotti et al. (2018, [CGGI18b]), the cipher expansion for TFHE
is still 8000. The ciphertext expansion problem was greatly reduced by Gao (2018) to
6 with private-key encryption and 20 for public key encryption. The bootstrapping in
Gao (2018) is only done one bit at a time, and the bootstrapping design matches the
previous two works in efficiency.

Our contribution is to present a fully homomorphic encryption scheme based on these preceding schemes that generalizes the Gao (2018) scheme to perform operations on k-bit encrypted data and also removes the need for the Independence Heuristic of the Chillotti et al. papers. The amortized cost of computing k-bits at a time improves the efficiency. Operations supported include addition and multiplication modulo $2^k$, addition and multiplication in the integers as well as exponentiation, field inversion and the machine learning activation function RELU. The ciphertext expansion factor is also further improved, for $k = 4$ our scheme achieves a ciphertext expansion factor of 2.5 under secret key and 6.5 under public key. Asymptotically as k increases, our scheme achieves the optimal ciphertext expansion factor of 1 under private key encryption and 2 under public key encryption. We also introduces techniques for reducing the size of the bootstrapping key.

Keywords. FHE, lattices, learning with errors (LWE), ring learning with errors (RLWE), TFHE, data security, RELU, machine learning

**Category / Keywords: **public-key cryptography / FHE, lattices, learning with errors (LWE), ring learning with errors (RLWE), TFHE, data security, RELU, machine learning

**Date: **received 18 May 2019

**Contact author: **bmcase at g clemson edu, bencase93 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20190520:202702 (All versions of this report)

**Short URL: **ia.cr/2019/521

[ Cryptology ePrint archive ]