When executing neural networks in secure environments—such as over encrypted data using Fully Homomorphic Encryption (FHE) or via Secure Multi-Party Computation (MPC)—we run into a fundamental mathematical barrier.
Standard deep learning architectures rely heavily on non-linear activation functions like ReLU, Sigmoid, GeLU, and Softmax. These functions require operations like conditional branching (for ReLU) or transcendental exponentiation (for Sigmoid and Softmax). However, cryptographic protocols are natively built on finite fields or rings, meaning they naturally support only two operations: addition and multiplication.
To compute a neural network securely, the network must be transformed into an arithmetic circuit. Because polynomials are composed entirely of additions and multiplications, approximating non-linear activations with polynomial functions has emerged as the primary strategy for bridging the gap between deep learning and cryptography.
The Core Trade-off: Degree vs. Cryptographic Cost
The simplest way to make a network crypto-friendly is to replace non-polynomial activations with low-degree polynomials. In a foundational framework, Gilad-Bachrach et al. demonstrated in CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy that a simple square function ($f(x) = x^2$) can replace ReLU in shallow networks while maintaining high classification accuracy. Similarly, Ghodsi et al. utilized quadratic activations in SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud to easily represent networks as verifiable arithmetic circuits.
However, as networks grow deeper and tasks become more complex, low-degree polynomials fail to capture the sharp non-linearities required for high accuracy. This introduces a strict tension between mathematical fidelity and cryptographic overhead:
- Multiplicative Depth (FHE): In homomorphic encryption, multiplying two ciphertexts increases the noise level within the ciphertext. Managing this noise requires larger encryption parameters and expensive "bootstrapping" operations. As Quan et al. explain in CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference, higher-order polynomials recover accuracy loss but increase the circuit's multiplicative depth, severely degrading execution speed.
- Communication Rounds (MPC): In multi-party computation, evaluating high-degree polynomials requires frequent interaction between the computing parties. Li et al. address this bottleneck in MPCFormer: fast, performant and private Transformer inference with MPC by substituting transcendental functions like GeLU and Softmax with quadratic approximations, prioritizing low-degree polynomials specifically to minimize these communication rounds.
Advanced Approximation Paradigms
To navigate this trade-off, researchers have moved beyond simple Taylor series expansions—which only approximate a function well near a single point—toward global and structural approximation techniques.
Minimax and Composite Polynomials
Minimax approximation aims to find a polynomial of a fixed degree that minimizes the maximum absolute error over a chosen interval. In When Homomorphic Encryption Marries Secret Sharing: Secure Large-Scale Sparse Logistic Regression and Applications in Risk Control, Chen et al. applied low-degree minimax polynomials to approximate the sigmoid function, preserving predictive accuracy within an arithmetic constraint budget. For deeper architectures, Kang et al. composed multiple minimax polynomials to approximate ReLU and Softmax, allowing standard architectures like ResNet to operate on fully encrypted data.
To achieve high precision without exploding the polynomial degree, Xu et al. proposed using nested, low-degree composite polynomials. This approach provides exponential convergence toward functions like ReLU and Max-pooling, requiring significantly fewer multiplication operations than a single high-degree polynomial fitting.
Piecewise Polynomials and Splines
Instead of forcing a single polynomial to fit an entire domain, an alternative approach divides the input space into segments. Lu et al. demonstrated in PUMA: Secure Inference of LLaMA-7B in Five Minutes that high-fidelity piecewise polynomial approximations for GeLU allow pre-trained Transformer models to maintain plaintext-level accuracy during secure inference without requiring expensive model retraining.
To optimize this in MPC, Lu et al. also showed in BumbleBee: Secure Two-party Inference Framework for Large Transformers that relaxing comparison precision near the segment boundaries of these piecewise approximations drastically reduces cryptographic costs with negligible impact on final accuracy.
Furthermore, Liu et al. argue in CipherGPT: Secure Two-Party GPT Inference that spline-based linear intervals combined with lookup tables are significantly more efficient for secure multi-party computation than high-degree polynomials, reducing the number of expensive cryptographic rounds while maintaining numerical precision.
Mitigating the Accuracy Gap
Simply swapping an activation function in a pre-trained model typically causes catastrophic accuracy degradation. Because polynomial approximations behave differently than the functions they replace—particularly outside bounded intervals where polynomials can tend toward infinity—the model's weights must adapt to these new mathematical constraints.
As highlighted by Disabato et al., models must be retrained or fine-tuned on plaintext data using the approximated polynomial functions to optimize the weights for the target encryption scheme's constraints.
Standard Inference: [Input] ---> [Linear Layer] ---> [ReLU / Sigmoid] ---> [Output]
|
Incompatible with Crypto Arithmetic
|
v
Secure Inference: [Input] ---> [Linear Layer] ---> [Polynomial/Spline] -> [Output]
^
Optimized via Plaintext Retraining
To automate and optimize this process, Lou et al. introduced a heterogeneous approach in SAFENet: A Secure, Accurate and Fast Neural Network Inference. Recognizing that not all layers or channels are equally sensitive to approximation errors, the authors designed a binary-tree search algorithm that dynamically assigns varying polynomial degrees across different channels. This maximizes computational efficiency where the network is robust and preserves high-degree fidelity only where it is strictly necessary to prevent gradient instability or accuracy loss.