Paper 2019/561
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$.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Fully homomorphic encryptionBootstrappingRestricted depth3 circuit
 Contact author(s)
 lzz600 @ 126 com
 History
 20190525: received
 Short URL
 https://ia.cr/2019/561
 License

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} }