### Faster Bootstrapping of FHE over the integers with large prime message space

Zhizhu Lian, Yupu Hu, Hu Chen, and Baocang Wang

##### Abstract

Bootstrapping of FHE over the integer with large message is a open problem, which is to evaluate double modulo $(c ~\text{mod}~ p )~\mod~ Q$ arithmetic homomorphically for large $Q$. In this paper, we express this double modulo reduction circuit as a arithmetic circuit of degree at most $\theta^2 \log^2\theta/2$, with $O(\theta \log^2\theta)$ multiplication gates, where $\theta= \frac{\lambda}{\log \lambda}$ and $\lambda$ is the security parameter. The complexity of decryption circuit is independent of the message space size $Q$ with a constraint $Q> \theta \log^2\theta/2$.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Fully homomorphic encryptionBootstrappingRestricted depth-3 circuit
Contact author(s)
lzz600 @ 126 com
History
Short URL
https://ia.cr/2019/561

CC BY

BibTeX

@misc{cryptoeprint:2019/561,
author = {Zhizhu Lian and Yupu Hu and Hu Chen and Baocang Wang},
title = {Faster Bootstrapping of FHE over the integers with large prime message space},
howpublished = {Cryptology ePrint Archive, Paper 2019/561},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/561}},
url = {https://eprint.iacr.org/2019/561}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.