Paper 2019/561 Original: eprint.iacr.org/2019/561 ↗

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

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$.