Paper 2019/521

Fully Homomorphic Encryption with k-bit Arithmetic Operations

Benjamin M. Case, Shuhong Gao, 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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
FHElatticeslearning with errors (LWE)ring learning with errors (RLWE)TFHEdata securityRELUmachine learning
Contact author(s)
bmcase @ g clemson edu
bencase93 @ gmail com
History
2019-05-20: received
Short URL
https://ia.cr/2019/521
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/521,
      author = {Benjamin M.  Case and Shuhong Gao and Gengran Hu and Qiuxia Xu},
      title = {Fully Homomorphic Encryption with k-bit Arithmetic Operations},
      howpublished = {Cryptology ePrint Archive, Paper 2019/521},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/521}},
      url = {https://eprint.iacr.org/2019/521}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.