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)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Fully homomorphic encryptionBootstrappingRestricted depth-3 circuit
Contact author(s)
lzz600 @ 126 com
History
2019-05-25: received
Short URL
https://ia.cr/2019/561
License
Creative Commons Attribution
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.