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 a STPC setting. The first protocol relies entirely on Garbled Circuit (GC) theory, while the second one exploits a hybrid construction where GC and Homomorphic Encryption (HE) 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.