Welcome to the resource topic for 2015/1044
Title:
Homomorphic evaluation requires depth
Authors: Andrej Bogdanov, 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.
ePrint: https://eprint.iacr.org/2015/1044
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .