International Association
for Cryptologic Research

We show that homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure homomorphic encryption scheme cannot be implemented by circuits of polynomial size and constant depth, i.e., in the class $\\ac^0$. In contrast, we observe that there exist ordinary public-key encryption schemes of quasipolynomial security in $\\ac^0$ assuming noisy parities are exponentially hard to learn. We view this as evidence that homomorphic evaluation is inherently more complex than basic operations in encryption schemes.