International Association
for Cryptologic Research

In this paper, we construct a fully homomorphic encryption (FHE) scheme over integers with the message space $Z_Q$ for any prime $Q$. Even for the binary case $Q=2$, our decryption circuit has a smaller degree than that of the previous scheme; the multiplicative degree is reduced from $O(\\lambda (\\log \\lambda)^2)$ to $O(\\lambda)$, where $\\lambda$ is the security parameter. We also extend our FHE scheme to a batch FHE scheme.