Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR12-157 | 13th April 2016 19:33

#### Homomorphic evaluation requires depth

Revision #2
Authors: Andrej Bogdanov, Chin Ho Lee
Accepted on: 13th April 2016 19:33
Keywords:

Abstract:

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 AC0. In contrast, we observe that there exist ordinary public-key encryption schemes of quasipolynomial security in AC0 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.

Changes to previous version:

The previous version made an unconditional claim about AC^0. We do not know that the claim is false. But this version does not make it.

Revision #1 to TR12-157 | 27th October 2015 20:52

#### Homomorphic evaluation requires depth

Revision #1
Authors: Andrej Bogdanov, Chin Ho Lee
Accepted on: 27th October 2015 20:52
Keywords:

Abstract:

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 $\mathrm{AC}^0$. In contrast, we observe that there exist ordinary public-key encryption schemes of quasipolynomial security in $\mathrm{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.

Changes to previous version:

More general arguments on implementing basic cryptographic operations in AC0.

### Paper:

TR12-157 | 12th November 2012 04:57

#### On the depth complexity of homomorphic encryption schemes

TR12-157
Authors: Andrej Bogdanov, Chin Ho Lee
Publication: 18th November 2012 22:35