Paper 2015/1044

Homomorphic evaluation requires depth

Andrej Bogdanov and Chin Ho Lee

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.

Note: 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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2016
Keywords
complexity of cryptographyhomomorphic encryption
Contact author(s)
chlee @ ccs neu edu
History
2016-04-13: revised
2015-10-28: received
See all versions
Short URL
https://ia.cr/2015/1044
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1044,
      author = {Andrej Bogdanov and Chin Ho Lee},
      title = {Homomorphic evaluation requires depth},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1044},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1044}},
      url = {https://eprint.iacr.org/2015/1044}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.