Cryptology ePrint Archive: Report 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.
Category / Keywords: complexity of cryptography, homomorphic encryption
Original Publication (with minor differences): IACR-TCC-2016
Date: received 27 Oct 2015, last revised 13 Apr 2016
Contact author: chlee at ccs neu edu
Available format(s): PDF | BibTeX Citation
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.
Version: 20160413:173428 (All versions of this report)
Short URL: ia.cr/2015/1044
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]