In Private Inference (PI), a server hosts a proprietary machine learning model and a client holds sensitive data. The goal is to evaluate the model on the data without the server learning the client's input, and without the client learning the model's weights.
While modern cryptography provides the tools to achieve this—primarily through Secure Multi-Party Computation (MPC) and Homomorphic Encryption (HE)—it introduces a bizarre asymmetry: operations that are computationally trivial in standard deep learning become overwhelmingly expensive when encrypted, while massive matrix multiplications become relatively cheap.
The primary culprit behind this performance gap is the non-linear activation function.
The Asymmetry of Encrypted Computation
To understand why non-linearities stall private inference, we must look at how data is represented cryptographically. Most efficient MPC protocols rely on Additive Secret Sharing. A sensitive value $x$ is split into two random-looking shares, $x_1$ and $x_2$, such that $x_1 + x_2 = x \pmod q$. One share is given to the client and the other to the server.
If the model needs to execute a linear layer—such as a convolution or a fully connected layer—the parties can compute it entirely locally. For a weight $W$, the parties compute $W \cdot x_1$ and $W \cdot x_2$ independently. Because matrix multiplication distributes over addition, adding these local results yields the correct encrypted output. No network messages are exchanged.
As noted by Jian Liu et al. in Oblivious Neural Network Predictions via MiniONN transformations, cryptographic primitives are natively optimized for this linear arithmetic. However, this harmony shatters the moment the network encounters a non-linear activation function like a Rectified Linear Unit ($\text{ReLU}(x) = \max(0, x)$).
Evaluating whether an encrypted number is greater than zero cannot be done by simply multiplying or adding secret shares locally. Instead, it requires determining the sign bit of the underlying plaintext. In a cryptographic context, this forces the system to switch from arithmetic representations to boolean representations. As Lucas Fenaux explains in Fast and Private Inference of Deep Neural Networks by Co-designing Activation Functions, these representation conversions require multiple interactive communication rounds between the client and the server.
[Arithmetic Shares] ---> (Interactive Protocol / Garbled Circuit) ---> [Arithmetic Shares]
(Local & Free) (Requires Network Communication) (Local & Free)
Linear Layer ReLU / GeLU / Softmax Linear Layer
This interaction turns network bandwidth into the ultimate bottleneck. Non-linear layers like ReLU, GeLU, Softmax, and LayerNorm frequently account for nearly 90%—and in some architectures, over 99%—of the total data transferred during an inference session, as demonstrated by Meng Hao et al. in Iron: Private Inference on Transformers and Tong Zhou et al. in AdaPI: Facilitating DNN Model Adaptivity for Efficient Private Inference in Edge Computing.
Strategy 1: Polynomial Substitution
If non-linear comparisons are expensive because they require boolean logic, the most direct solution is to replace them with functions that rely purely on addition and multiplication: polynomials.
A low-degree polynomial approximation, such as $f(x) = ax^2 + bx + c$, can be evaluated within arithmetic secret sharing using standard cryptographic multiplication protocols (like Beaver Triples). By substituting ReLUs with polynomials, the heavy communication overhead of boolean circuits is bypassed entirely.
The challenge lies in preserving model accuracy, as standard networks degrade rapidly if their activations are crudely swapped. To address this, Qian Lou et al. developed SAFENet: A Secure, Accurate and Fast Neural Network Inference, which uses a fine-grained, channel-wise polynomial approximation strategy to balance speed and accuracy. Similarly, Hongwu Peng et al. in AutoReP: Automatic ReLU Replacement for Fast Private Network Inference designed an automated, gradient-based selection framework to replace only the most cryptographically expensive ReLUs with distribution-aware polynomials.
For complex architectures like Transformers and Diffusion Models, which rely on transcendental functions like GeLU, SiLU, and Softmax, polynomial substitution is even more critical. Protocols like those designed by Dacheng Li et al. in MPCFORMER: Fast, Performant and Provate Transformer Inference with MPC and Xiaojun Chen et al. in CipherDM: Secure Three-Party Inference for Diffusion Model Sampling rely heavily on tailored quadratic and low-degree Taylor approximations to keep transformer attention blocks "MPC-friendly."
Taking this concept to its logical conclusion, some researchers eliminate standard activations entirely during model design. Jiajie Li et al. proposed xMLP: Revolutionizing Private Inference with Exclusive Square Activation, an architecture built exclusively around square activations ($x^2$), while Wittawat Jitkrittum et al. in HD-cos Networks: Efficient Neural Architectures for Secure Multi-Party Computation substituted ReLUs with cosine functions to maintain training stability without incurring interactive overhead.
Strategy 2: Designing for a ReLU Budget
Instead of modifying a pre-existing model, an alternative paradigm treats cryptographic cost as a first-class constraint during the architectural design phase. This shifts the optimization metric from minimizing floating-point operations (FLOPs) to minimizing the "ReLU budget."
Zahra Ghodsi et al. introduced this paradigm with CryptoNAS: Private Inference on a ReLU Budget. By using Neural Architecture Search (NAS), the framework discovers where ReLUs are strictly necessary for high accuracy and where they can be safely omitted or replaced by linear operations.
Standard NAS Optimization: Minimize Latency = f(FLOPs, Parameter Count)
Crypto NAS Optimization: Minimize Latency = f(Total ReLU Count, Network Rounds)
Building on this, Hongwu Peng et al. developed PASNet: Polynomial Architecture Search Framework for Two-party Computation-based Secure Neural Network Deployment, a hardware-aware NAS framework that optimizes network topologies specifically for trainable second-order polynomials, maximizing throughput when deployed on specialized hardware like FPGAs.
Strategy 3: Cryptographic and Algorithmic Optimizations
When non-linear operations cannot be removed or approximated via polynomials, researchers focus on optimizing the underlying cryptographic execution of the boolean circuits themselves.
Quantized Lookup Tables
Traditional MPC evaluates non-linear functions by passing shares through Garbled Circuits (GC), which treat the function as a massive web of boolean logic gates. Every non-linear gate (like an AND gate) requires exchanging cryptographic tokens, driving up latency.
To bypass this, Max Lam et al. introduced Tabula: Efficiently Computing Nonlinear Activation Functions for Secure Neural Network Inference. Tabula aggressively quantizes activation inputs to 8 bits, allowing the system to replace complex garbled circuits with secure, encrypted lookup tables. This eliminates the need to evaluate functions gate-by-gate, drastically reducing communication overhead.
Stochastic and Partial Approximations
Deep neural networks possess an inherent fault tolerance. Nandan Kumar Jha et al. leveraged this property in Circa: Stochastic ReLUs for Private Deep Learning by replacing exact ReLU comparisons with stochastic versions that use bit-truncation and approximate sign tests, trading deterministic precision for significant cryptographic speedups.
Furthermore, efficiency can be gained by decomposing the activation function itself. As shown by Guowen Xu et al. in SIMC 2.0: Improved Secure ML Inference Against Malicious Clients, complex non-linear functions can be broken down into simpler components so that only the strictly non-linear part undergoes expensive garbling, while the remaining pieces are handled via lightweight protocols.
The Evolving Bottleneck
The concerted effort to minimize non-linear activation overhead has been highly successful, to the point where the primary bottleneck in private inference is beginning to shift.
As Wenxuan Zeng et al. demonstrate in CoPriv: Network/Protocol Co-Optimization for Communication-Efficient Private Inference, in highly optimized modern 2-party computation protocols, the communication cost of non-linear activations has dropped significantly. As a result, optimization strategies that focus exclusively on reducing activation counts are hitting diminishing returns, shifting the primary cryptographic overhead back onto linear operations and fixed-point truncation steps.
Nevertheless, understanding and mitigating the non-linear activation bottleneck remains the foundational breakthrough that transitioned private inference from a theoretical impossibility to a practical reality.
Key Foundational Work
Oblivious Neural Network Predictions via MiniONN transformations (2017) — contributed 1 concept elements to this direction.
Secure Evaluation of Quantized Neural Networks (2019) — contributed 1 concept elements to this direction.