Paper 2026/926

Private Function Evaluation with Linear Complexity

Cong Zhang, Tsinghua University

Anyu Wang, Tsinghua University

Xiaoyun Wang, Tsinghua University

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 \textit{public} circuit, PFE generalizes SFE by allowing one party to keep the circuit \textit{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(mn^2)$ complexity and are limited to Boolean circuits.

Note: This is the full version of the paper with the same title that will appear at CRYPTO 2026.

@misc{cryptoeprint:2026/926,
      author = {Shuaishuai Li and Cong Zhang and Anyu Wang and Xiaoyun Wang},
      title = {Private Function Evaluation with Linear Complexity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/926},
      year = {2026},
      url = {https://eprint.iacr.org/2026/926}
}