Secure Evaluation of Private Functions through Piecewise Linear Approximation

While Secure Multy-Party Computation is a well known solution for cooperative function evaluation on private inputs, few solutions exist that also permit to protect the to-be-evaluated function. In this paper, we propose a solution, based on Garbled Circuit (GC) theory, to provide Secure Function Evaluation of semi-Private Functions through Piecewise Linear Approximation (PLA). We show how to approximate a generic function through a PLA chosen in a set of functions that can be implemented with the same Boolean circuit. The function is protected by hiding the coefficients of the chosen PLA. The class of approximating functions is defined in such a way to allow an efficient implementation by means of GC's. Together with the security provided by Garbled Circuits theory, the security of the protocol is ensured by the very large number of approximating functions belonging to the PLA's set. The paper ends with an investigation of the trade-off between approximation accuracy and protocol settings.