Piecewise Function Approximation with Private Data

We present two secure two party computation (STPC) protocols for piecewise function approximation on private data. The protocols rely on a piecewise approximation of the to-be-computed function easing the implementation in an STPC setting. The first protocol relies entirely on garbled circuits (GCs), while the second one exploits a hybrid construction where GC and homomorphic encryption are used together. In addition to piecewise constant and linear approximation, polynomial interpolation is also considered. From a communication complexity perspective, the full-GC implementation is preferable when the input and output variables can be represented with a small number of bits, while the hybrid solution is preferable otherwise. With regard to computational complexity, the full-GC solution is generally more convenient.