1970-01-01

(2026-04) MBU; Scalable and Constant-Round Evaluation of Non-linear Functions in Standard MPC Setting

Min Yang
Dongcan Guo
Zihang Zhou
Jinxuan Du
Qingshu Meng

2026-04-18

Abstract

After more than four decades of research, multi-party computation (MPC) has achieved remarkable success in handling 2-variable multiplication and comparison-based functions (e.g., ReLU) with practical efficiency. However, for general non-linear functions—such as multiplication of many variables, power, exponential, trigonometric functions, sigmoid, softmax, and GeLU—no native MPC algorithm exists as Beaver-based mutiplication that is constant-round, scalable and exact. Existing solutions rely on either polynomial approximations (trading precision for efficiency), iterative multi-round protocols like Multiplication-to-Addition (M2A) conversion (requiring $\log_2 k$ rounds for $k$ parties), or Function Secret Sharing (FSS) with lookup tables (introducing quantization errors and large storage, mainly limited to 2-4 parties). These approaches suffer from fundamental trade-offs among accuracy, communication rounds, and scalability.

In this work, we propose a unified mask-broadcast-unmask design pattern that enables constant-round, scalable and approximation-free evaluation of a wide range of non-linear functions. Our contributions include:

A general multiplication protocol for $k$ variables in one round with optimal $O(kn)$ communication. When $k=2$ , it reduces to the classic Beaver triple multiplication; when each secret has only one non-zero share and $k=2$ , it becomes the well-known M2A protocol.
Power functions ( $x^k$ ) in one round.
Trigonometric functions ( $\sin x, \cos x$ ) and exponential functions ( $a^x$ ) in 4 rounds.
Sigmoid, softmax in 6 rounds.

All these protocols are provably secure in the semi-honest model, support arbitrary number of parties, introduce no approximation error beyond plaintext floating-point rounding, and require only constant communication rounds (1–6) independent of function complexity. Furthermore, by restricting the random mask to a suitable range (e.g., $0 \le r <2^l-2^{l_x}$ ), we can reduce the rounds from 1-6 to 1-3. This work fills the long-standing gap for general non-linear functions in standard MPC settings, making privacy-preserving machine learning more practical for modern DNNs.