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_1$ holds its private n-variable function $f$ and private input $x_1$, while other parties $P_i(n\ge i\ge 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_1,...,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.