Grotto: Screaming fast (2+1)-PC or ℤ2n via (2, 2)-DPFs

We introduce Grotto, a framework and C++ library for space- and time-efficient (2+1)-party piecewise polynomial (i.e., spline) evaluation on secrets additively shared over ℤ2n. Grotto improves on the state-of-the-art approaches based on distributed comparison functions (DCFs) in almost every metric, offering asymptotically superior communication and computation costs with the same or lower round complexity. At the heart of Grotto is a novel observation about the structure of the ''tree'' representation underlying the most efficient distributed point functions (DPFs) from the literature, alongside an efficient algorithm that leverages this structure to do with a lightweight DPF what state-of-the-art approaches require comparatively heavyweight DCFs to do. Our open-source Grotto implementation supports dozens of useful functions out of the box, including trigonometric and hyperbolic functions with their inverses; various logarithms; roots, reciprocals, and reciprocal roots; sign testing and bit counting; and over two dozen of the most common univariate activation functions from the deep-learning literature.