Masayuki Abe, Rosario Gennaro, et al.
Eurocrypt 2005
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.
Masayuki Abe, Rosario Gennaro, et al.
Eurocrypt 2005
Jehoshua Bruck, Roman Smolensky
ISIT 1991
Yvo Desmedt, Rosario Gennaro, et al.
Journal of Cryptology
Shai Halevi, Tzipora Halevi, et al.
CCS 2017