General function evaluation in a STPC setting via piecewise linear approximation

While in theory any computable functions can be evaluated in a Secure Two Party Computation (STPC) framework, practical applications are often limited for complexity reasons and by the kind of operations that the available cryptographic tools permit. In this paper we propose an algorithm that, given a function f() and an interval belonging to its domain, produces a piecewise linear approximation f() that can be easily implemented in a STPC setting. Two different implementations are proposed: the first one relies completely on Garbled Circuit (GC) theory, while the second one exploits a hybrid construction where GC and Homomorphic Encryption (HE) are used together. We show that from a communication complexity perspective the full-GC implementation is preferable when the input and output variables are represented with a small number of bits, otherwise the hybrid solution is preferable