💻 computer science

Kernel-Based ReLU Approximation for Homomorphic Encryption-Compatible Privacy-preserving Deep Learning Models

This paper proposes a kernel-based, second-degree polynomial approximation of the ReLU activation function to enable the deployment of Large Language Models within Homomorphic Encryption frameworks, thereby facilitating secure and privacy-preserving inference without decryption.

Original authors: Dimitrios Sygletos, Dimitra Papatsaroucha, Marios Choudetsanakis, Ilias Politis, Evangelos K. Markakis

Published 2026-05-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Dimitrios Sygletos, Dimitra Papatsaroucha, Marios Choudetsanakis, Ilias Politis, Evangelos K. Markakis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you want to send a secret message to a friend, but you don't trust the mail carrier. So, you put your message in a locked box (encryption) and send it. The problem is, your friend needs to read the message to do something with it, but they can't open the box without a key, and if they open it, the secret is out.

Homomorphic Encryption (HE) is like a magical lockbox. It allows your friend to perform calculations inside the locked box without ever opening it. They can add numbers or multiply them, and the result inside the box is still correct when they finally open it. This is a huge deal for privacy, especially for Artificial Intelligence (AI), because it means a company can analyze your private data (like your health records or personal chats) without ever seeing the raw data itself.

However, there's a catch. The magic lockbox only understands addition and multiplication. It doesn't understand "thinking" or "decisions."

The Problem: The "ReLU" Gate

Deep Learning models (the brains behind modern AI like chatbots) rely on a special switch called ReLU (Rectified Linear Unit). Think of ReLU as a bouncer at a club:

If a number is positive (a VIP), the bouncer lets it pass through.
If a number is negative (not a VIP), the bouncer stops it completely (turns it to zero).

This "bouncer" behavior is essential for AI to learn complex patterns. But because the bouncer has to make a "stop or go" decision, it's a non-linear, jagged function. The magical lockbox (HE) can't handle this jagged decision-making because it only likes smooth, simple math (adding and multiplying).

The Solution: A Smooth "Fake" Bouncer

The authors of this paper wanted to replace the jagged bouncer with a smooth, polite substitute that the lockbox can understand, but that acts exactly like the original bouncer.

They used a two-step recipe:

Step 1: The "Smoothie" Maker (Kernel Approximation)
First, they realized that trying to approximate the jagged bouncer directly is messy. So, they used a "Kernel" method (a mathematical tool that smooths things out) to turn the jagged ReLU into a smooth, curved hill. Imagine taking a jagged rock and grinding it down into a smooth, round pebble. This pebble still looks like the rock from a distance but is much easier to handle.
Step 2: The Simple Math Trick (Polynomial Regression)
Now that they had a smooth hill, they needed to describe it using only addition and multiplication. They tried different levels of complexity:
- Low degree (Simple): A simple curve (like a parabola).
- High degree (Complex): A very wiggly, complicated curve with many twists.
The Surprise: They expected the complicated, wiggly curves to be more accurate. Instead, they found that the simple, second-degree curve (a simple U-shape) was actually the winner.
- Why? The complex curves were too "jittery." In the world of encrypted math, adding too many twists causes "noise" (static) to build up, eventually drowning out the signal. It's like trying to whisper a secret through a long, winding tunnel; if the tunnel is too twisty, the sound gets lost. The simple curve kept the message clear and the math fast.

What They Tested

The researchers didn't just do this on paper. They tested their "smooth bouncer" in real scenarios:

On Data: They fed it real text data from pre-trained AI models (like RoBERTa and DistilBERT) to see if it could mimic the original bouncer's behavior.
On AI Models: They swapped the real ReLU with their new "smooth bouncer" in different types of AI brains (simple networks, image recognizers, and complex Transformers).
In the Lockbox: They ran everything inside the Homomorphic Encryption lockbox to see how fast it was and how accurate the results remained.

The Results

Accuracy: Their simple, smooth bouncer was almost as good as the real thing and much better than other "smooth" attempts found in previous research.
Speed: Because their solution was mathematically simple, it was incredibly fast. Other methods that tried to use complex, high-degree curves were up to 100 times slower when working inside the encrypted lockbox.
Privacy: They successfully proved that you can run complex AI tasks on encrypted data without losing much accuracy, provided you use the right kind of simple math.

The Bottom Line

This paper introduces a clever way to make AI privacy-friendly. By smoothing out the "bouncer" function and replacing it with a simple, low-complexity curve, they allowed AI to work inside a locked box without breaking the lock or slowing down the process. It's a reminder that sometimes, the simplest solution is the most powerful one.

Technical Summary: Kernel-Based ReLU Approximation for Homomorphic Encryption-Compatible Privacy-Preserving Deep Learning Models

1. Problem Statement

The widespread adoption of Large Language Models (LLMs) and Deep Learning (DL) has heightened privacy concerns, particularly regarding the processing of sensitive user data (e.g., health information) in unencrypted forms. Homomorphic Encryption (HE), specifically schemes like CKKS, offers a solution by enabling computations on encrypted data without decryption. However, HE is fundamentally limited to addition and multiplication operations. This creates a critical incompatibility with standard DL architectures, which rely heavily on non-linear activation functions like the Rectified Linear Unit (ReLU).

The ReLU function, defined as $ReLU(x) = \max(0, x)$ , is non-smooth (not differentiable at zero). Directly approximating such a non-smooth function with low-degree polynomials—required to minimize multiplicative depth in HE—results in significant approximation errors. Existing methods, such as the $x^2$ function or higher-degree Chebyshev polynomials, either fail to capture the zeroing behavior for negative inputs or introduce prohibitive computational costs and instability (e.g., Runge's phenomenon) when deployed in encrypted environments.

2. Methodology

The paper proposes a two-stage Kernel-Based ReLU Approximation method designed to generate a HE-compatible, second-degree polynomial that mimics ReLU behavior with high fidelity and low multiplicative depth.

Smoothing via Kernel Regression: To address the non-smoothness of ReLU, the authors first transform the function into a smooth approximation using a Kernel-based method. Specifically, they employ the hyperbolic tangent kernel ( $k(x, x') = \tanh(\langle x, x' \rangle + 1)$ ) trained on input data. This step leverages the principle that smoother functions can be approximated more accurately by polynomials, as supported by Jackson's Theorem.
Polynomial Fitting: The output of the trained Kernel function is then approximated using a second-degree polynomial ( $p(x) = a_0 + a_1x + a_2x^2$ ) via Ordinary Least Squares (OLS) regression.
Data Source: The method is trained and assessed directly on token embeddings extracted from pre-trained LLMs (RoBERTa and DistilBERT) using the Stanford Sentiment Treebank (SST-2) dataset. This ensures the approximation is grounded in real-world NLP data rather than synthetic distributions.
Degree Selection: The authors systematically evaluated polynomial degrees 2 through 5. They found that while higher degrees theoretically offer better fit, they introduce instability and exponentially higher error rates in encrypted domains due to increased multiplicative depth and noise growth in the CKKS scheme. Consequently, the second-degree polynomial was selected as the optimal trade-off between accuracy and computational efficiency.

The resulting final polynomial is:
$p(x) = 0.082261 + 0.495588x + 0.444488x^2$

3. Key Contributions

A Novel Approximation Strategy: The introduction of a Kernel-based smoothing technique followed by low-degree polynomial fitting, specifically tailored for HE constraints.
Real-World Validation: Unlike prior works that often rely on synthetic data or indirect evaluation via classification accuracy, this method is trained and evaluated on actual token embeddings from pre-trained LLMs.
Comprehensive Benchmarking: The proposed method is rigorously compared against established approximations, including $x^2$ , FasterCryptoNets, and Chebyshev polynomials (degrees 3 and 5), across multiple dimensions: approximation error (MSE), model accuracy (FeedForward, CNN, ViT), and computational cost.

4. Results

The evaluation was conducted across six experimental scenarios, covering both plaintext and encrypted (CKKS) environments:

Approximation Accuracy: The Kernel Polynomial method achieved the lowest Mean Squared Error (MSE) in both plaintext and encrypted environments (0.056862) compared to higher-degree polynomials, which exhibited significant instability (e.g., MSE > 390 for degree 5). In structured data tests using RoBERTa and DistilBERT embeddings, the proposed method maintained an MSE of 0.002, outperforming $x^2$ and FasterCryptoNets.
Model Performance:
- DL Models: In FeedForward and CNN architectures on the MNIST dataset, the Kernel Polynomial achieved 99% and 99.2% accuracy, respectively, comparable to or slightly below the best-performing FasterCryptoNets (99.3%).
- Transformers: On the ViT architecture with CIFAR-10 and CIFAR-100, the method demonstrated strong generalization, achieving 38.5% accuracy on CIFAR-100 (the highest among tested methods), whereas higher-degree approximations like Chebyshev-5 showed lower performance.
Encrypted Environment Performance:
- Accuracy Gap: The proposed method exhibited the smallest accuracy gap between plaintext and encrypted execution (29.3%), outperforming Chebyshev-3 (35.3%) and Chebyshev-5 (33.6%).
- Computational Efficiency: The second-degree polynomial offered a significant speed advantage. The total experiment time for the Kernel Polynomial was 1,864 seconds, whereas Chebyshev-5 required 11,348 seconds (a slowdown factor of ~109x). The method maintained a low multiplicative depth, preventing the rapid noise growth associated with higher-degree polynomials in CKKS.

5. Significance and Claims

The paper claims that the proposed Kernel Polynomial method represents a robust and efficient solution for privacy-preserving inference in LLMs and DL models. Its significance lies in:

Bridging the Gap: It effectively bridges the performance gap between encrypted and unencrypted execution, enabling the deployment of complex models like Transformers in privacy-sensitive NLP settings without the severe accuracy degradation seen in higher-degree approximations.
Optimal Trade-off: The study demonstrates that for smooth, Kernel-based functions, lower-degree polynomials (specifically degree 2) can achieve exceptionally low approximation errors while maintaining high classification accuracy and lower computational costs. This challenges the assumption that higher-degree polynomials are inherently superior for approximation in HE contexts.
Practical Viability: By minimizing multiplicative depth, the method reduces the "cost of privacy" (latency and noise accumulation), making it a viable candidate for high-throughput, secure inference applications.

The authors conclude that while future work may explore adaptive hybrid models and hardware acceleration, the current method successfully addresses the critical challenge of integrating non-linear activation functions into Homomorphic Encryption-compatible deep learning pipelines.