Private Function Evaluation with Linear Complexity

Abstract. We present new frameworks for secure function evaluation (SFE) and private function evaluation (PFE) that support both Boolean and arithmetic circuits. While SFE requires multiple parties to jointly compute a public circuit, PFE generalizes SFE by allowing one party to keep the circuit private. Our work achieves the first linear-complexity PFE protocol with respect to both the number of parties n and circuit size m, significantly improving upon prior PFE constructions that require O(m n^2) complexity and are limited to Boolean circuits.