ECCC-Report TR12-157https://eccc.weizmann.ac.il/report/2012/157Comments and Revisions published for TR12-157en-usWed, 13 Apr 2016 19:33:16 +0300
Revision 2
| Homomorphic evaluation requires depth |
Andrej Bogdanov,
Chin Ho Lee
https://eccc.weizmann.ac.il/report/2012/157#revision2We 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.Wed, 13 Apr 2016 19:33:16 +0300https://eccc.weizmann.ac.il/report/2012/157#revision2
Revision 1
| Homomorphic evaluation requires depth |
Andrej Bogdanov,
Chin Ho Lee
https://eccc.weizmann.ac.il/report/2012/157#revision1We 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.Tue, 27 Oct 2015 20:52:58 +0200https://eccc.weizmann.ac.il/report/2012/157#revision1
Paper TR12-157
| On the depth complexity of homomorphic encryption schemes |
Andrej Bogdanov,
Chin Ho Lee
https://eccc.weizmann.ac.il/report/2012/157We show that secure homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure encryption scheme cannot be implemented by constant depth, polynomial size circuits, i.e. in the class AC0. In contrast, we observe that certain previously studied encryption schemes (with quasipolynomial security) can be implemented in AC0. We view this as evidence that encryption schemes that support homomorphic evaluation are inherently more complex than ordinary ones.
Sun, 18 Nov 2012 22:35:47 +0200https://eccc.weizmann.ac.il/report/2012/157