Constant-Round Multiparty Private Function Evaluation with (Quasi-)Linear Complexities

Private function evaluation (PFE) is a special case of secure multiparty computation. In multiparty PFE, the party P₁ holds its private n-variable function f and private input x₁, while other parties Pi(n≥i≥2) hold their private input x_i. All n participants can jointly evaluate the function f, and learn nothing from the interactions except the result f(x₁,.., x_n) (known to a subset or all of the parties). The existing multiparty PFE protocols (e.g., Mohassel et al. at Eurocrypt’13 and Asiacrypt’14) are with round complexity O(g) (g is the circuit size) which makes them extremely unpractical. In this work, we propose for the first time constant-round multiparty PFE protocols that are secure against any number of corrupted parties under the semi-honest security model. We design our first construction from oblivious evaluation of switching network (OSN) protocol (Mohassel et al. at Eurocrypt’13), which only needs 9 rounds of interaction and can achieve quasi-linear communication and computation complexities (i.e., O(nglog (g) ) ). Our second construction is based on singly homomorphic encryption, which only needs 8 rounds of interaction and can achieve linear complexities. The OSN-based construction also benefits from the design trick that it only relies on symmetric operations (which makes it really efficient in actual executions). We further optimize our constructions by half-gate technology.