Christian Cachin, Klaus Kursawe, et al.
Journal of Cryptology
We show that there is a set of points p1, p2, . . . , pn such that any arithmetic circuit of depth d for polynomial evaluation (or interpolation) at these points has size Ω (n log n/log(2 + d/log n)). Moreover, for circuits of sub-logarithmic depth d, we obtain a lower bound of Ω(dn1+1/d) on its size.
Christian Cachin, Klaus Kursawe, et al.
Journal of Cryptology
Yvo Desmedt, Rosario Gennaro, et al.
Journal of Cryptology
Shai Halevi, Tzipora Halevi, et al.
CCS 2017
Victor Shoup
ISSAC 1999