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

*Zhizhu Lian and Yupu Hu and 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$.

**Category / Keywords: **public-key cryptography / Fully homomorphic encryption, Bootstrapping, Restricted depth-3 circuit

**Date: **received 25 May 2019

**Contact author: **lzz600 at 126 com

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

**Version: **20190525:181023 (All versions of this report)

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

[ Cryptology ePrint archive ]