arXiv:2605.23641v1 [cs.CR] 22 May 2026
Kernel-Based ReLU Approximation for Homomorphic Encryption-Compatible Privacy-preserving Deep Learning Models Dimitrios Sygletos
Dimitra Papatsaroucha
Marios Choudetsanakis
[email protected] Hellenic Mediterranean University Heraklion, Crete, Greece
[email protected] Hellenic Mediterranean University Heraklion, Crete, Greece
[email protected] Hellenic Mediterranean University Heraklion, Crete, Greece
Ilias Politis
Evangelos K. Markakis
[email protected] Research Center "ATHENA" Patras, Western Greece, Greece
[email protected] Hellenic Mediterranean University Heraklion, Crete, Greece
Abstract As privacy concerns in AI technologies continue to grow, Homomorphic Encryption (HE) offers a way to perform computations on encrypted data without the need of decryption during the operations. However, HE is limited to addition and multiplication, making non-linear functions incompatible in their original form. This limitation has become more critical with the widespread use of Large Language Models (LLMs), where the non-linearity of activation functions such as the Rectified Linear Unit (ReLU) poses challenges for deployment in privacy-preserving Natural Language Processing (NLP) settings. This paper proposes a Kernel-based approximation of ReLU, enabling its use within HE-constrained settings and thus contributing a critical step toward supporting privacy-preserving LLMs. A smooth Kernel-based function, mimicking ReLU, is approximated using a second-degree polynomial, inspired by Jackson’s theorem, to achieve low multiplicative depth. The proposed method is trained and assessed directly on token embeddings from pretrained LLMs and evaluated in various scenarios, from simulated and tokenized data to deep learning and transformer models. Results show improved approximation fidelity, supporting the method’s suitability for secure and privacy-preserving inference in various tasks.
Keywords ReLU approximation, privacy preserving inference, large language models, homomorphic encryption, deep learning
1
Introduction
In recent years, Machine Learning (ML) and Deep Learning (DL) have become integral to modern technology, powering applications from spam detection and voice recognition to recommendation systems and real-time translation. A key driver of this progress has been the ability of models to identify complex patterns in large datasets. Large Language Models (LLMs), in particular, have advanced Natural Language Processing (NLP) by using transformer architectures to generate human-like text, forming the backbone of contemporary chatbots. However, when users interact with these systems—whether for casual queries or sensitive tasks such as disclosing personal health information—their data is often transmitted
and processed unencrypted. This raises privacy concerns, as model providers retain access to user inputs. A technology that could address the concern of safeguarding data privacy during operations such as NLP is Homomorphic Encryption (HE), a Privacy-Preserving Technique (PET) enabling computations in the encrypted domain with schemes such as CKKS [3]. HE enables computations to be performed directly on encrypted data, without requiring decryption. However, it comes with significant limitations; most notably, that only addition and multiplication are supported, while DL models often rely on more complex, non-linear operations that are incompatible with these constraints. To convert a DL model into an HE-compatible form, activation functions like ReLU, which introduce the non-linearity essential for DL models to learn complex patterns, must be replaced with alternatives that rely solely on addition and multiplication, such as polynomials. This substitution would allow the model to operate entirely within the encrypted domain, thus preserving data privacy. Approximating the ReLU function, however, presents a challenge due to its non-smoothness. To overcome this challenge, this paper proposes a Kernel-based smoothing technique that transforms the ReLU function into a form that can be more easily approximated by polynomials. The technique draws inspiration from Jackson’s theorem [2, 17], which guarantees that smoother functions can be approximated more accurately by polynomials, with the approximation error decreasing rapidly as the polynomial degree increases. In this study, ReLU is first transformed into a smooth Kernel-based function that is then approximated using a second-degree polynomial after investigating the trade-off between approximation accuracy and computational efficiency among polynomials of various degrees. The primary objective of this work was to approximate ReLU with a HE-compatible polynomial, therefore a number of evaluation experiments were performed and the results demonstrate that the selected polynomial effectively mimics the behavior of ReLU and overcomes approximation challenges, while also maintaining compatibility with HE constraints and competitive performance in plaintext and encrypted environments among other proposed approximations identified through the literature. The remainder of this paper is structured as follows: Section 2 provides background information about the ReLU function, Jackson’s theorem, Kernel Approximations, and Polynomial Regression;
Sygletos and Papatsaroucha, et al.
Section 3 presents relevant work that was identified across the literature regarding the approximation of ReLU using various methods; Section 4 describes the steps that were followed for implementing the proposed approximation. The setup and the evaluation of the experiments are stated in Section 5 while Section 6 provides the concluding remarks of this work.
2 Backround 2.1 ReLU Activation functions are critical components in DL models, as they introduce non-linearity, allowing neural networks to learn complex patterns [15]. ReLU acts as a selective gate in neural networks by preserving positive values while discarding negative ones, as can be seen in (1). Such values represent messages that get transmitted from one layer of the neural network to another: when the message is deemed insignificant (negative), ReLU suppresses its transmission; otherwise, it permits it to go to the subsequent layer. ReLU(𝑥) = max(0, 𝑥)
(1)
This function has become the default activation function in many modern DL architectures, including neural networks and transformers, which form the foundation of modern LLMs. However, when deploying DL models in the encrypted domain, using PETs such as HE, ReLU becomes incompatible due its non-linearity. As HE supports only addition and multiplication, a practical solution is to replace ReLU with a function that can operate in the encrypted domain, such as a polynomial that includes only additions and multiplications and approximates the behavior of ReLU.
2.2
Jackson’s Theorem
In approximation theory, Jackson’s theorem relates the smoothness of a function to how well it can be approximated by polynomials, as it can be seen below.
for generating such smooth approximations as they support learning non-linear relationships in data by implicitly mapping input features into high-dimensional spaces. Instead of explicitly transforming the data, Kernel functions compute inner products in the transformed space directly [18]. In the context of function approximation, Kernel-based methods have demonstrated notable success in capturing non-linear patterns with a relatively small number of parameters. For example, the kernlab package [11] in R provides an implementation of various Kernel methods, including the hyperbolic tangent Kernel (4), which can be trained to approximate activation functions, such as ReLU.
2.4
Polynomial Regression
Polynomial representations offer a way to express smooth functions under HE constraints. Polynomial regression (5) offers a systematic way to approximate smooth functions with a low-degree polynomial as a form of regression analysis, in which the relationship between the independent variable 𝑥 and the dependent variable 𝑦 is modeled as a 𝑛𝑡ℎ 𝑑𝑒𝑔𝑟𝑒𝑒 polynomial. It extends linear regression by introducing polynomial terms to capture nonlinear patterns in the data, while still being linear in the model coefficients. This method serves as a useful reference and approximation tool in many domains, including physics, economics, and ML, particularly when simplicity of the model and computational efficiency are important [7].
3
State of the Art
Across the literature, research has focused on approximating activation functions like ReLU using polynomials composed only of additions and multiplications. A widely used polynomial approximation of ReLU is the X-squared function showcased below in (2) [10, 16]. 𝑓 (𝑥) = 𝑥 2
Theorem 2.1. Let 𝑓 ∈ 𝐶 𝑟 ([𝑎, 𝑏]), where 𝑟 ∈ N, and [𝑎, 𝑏] is a closed interval. Then there exists a polynomial 𝑃𝑛 of degree at most 𝑛 such that: 𝐶 ∥ 𝑓 − 𝑃𝑛 ∥ ∞,[𝑎,𝑏 ] ≤ 𝑟 ∥𝑓 (𝑟 ) ∥ ∞,[𝑎,𝑏 ] 𝑛 where ∥𝑔∥ ∞,[𝑎,𝑏 ] = max𝑥 ∈ [𝑎,𝑏 ] |𝑔(𝑥)| and 𝐶 is a constant depending only on 𝑟 and the length of the interval (𝑏 − 𝑎).
While this function is compatible with HE, it lacks the zeroing behavior of ReLU for negative inputs. As can be seen in Figure 1, the X-squared function maps all inputs, both positive and negative, to positive values, thereby altering the nature of the activation and introducing unintended signal propagation to the subsequent layers.
This indicates that the smoother a function is—in the sense that it has more continuous derivatives—the better it can be approximated by polynomials. The error between the function and its polynomial approximation decreases rapidly as the degree 𝑛 of the polynomial increases. This makes Jackson’s theorem a foundational tool in approximation theory, particularly when analyzing the trade-off between approximation accuracy and polynomial complexity [2, 17].
2.3
Kernel Approximations
Since ReLU is not smooth, directly approximating it with lowdegree polynomials leads to significant error. A way to address this limitation is to first construct a smooth function that closely mimics ReLU. Kernel-based methods provide a suitable framework
(2)
Figure 1: Actual ReLU vs X Squared
Kernel-Based ReLU Approx. for HE-Compatible Privacy-preserving Deep Learning Models
HE libraries like TenSEAL [16] embed the X-squared function within CNNs and [14] evaluated its efficacy based on the prediction results on synthetic datasets, such as MNIST [5]. However, this methodology assessed the approximation indirectly, as it compared classification accuracy of the CNN model, which may not reflect the quality of the approximation itself. In [4] low degree polynomials were proposed, capturing the behavior to common activation functions (e.g., Swish, Softplus, and ReLU). The proposed Minimax method (3) performed well in the image classification task using the MNIST dataset, showing that it could replace the original activation functions; however, with a significant disadvantage as its coefficients are arbitrary real numbers that do not allow for efficient encrypted computation. 𝑝 (𝑥) = 0.125𝑥 2 + 0.5𝑥 + 0.25 (3) An alternative approach utilized Chebyshev polynomials in [12]. While this method provided good approximations, it required polynomials of degree at least three. According to Jackson’s theorem, directly approximating non-smooth functions, such as ReLU, requires higher degree polynomials to achieve acceptable accuracy [2]. Thereby, the reviewed study used polynomials of the 7th and 9th degree, which on one hand optimized the approximation but on the other would increase the computational cost in an HE scheme. As revealed through the literature, most studies have focused on approximating ReLU through functions that either fall short in preserving its essential behavior—as the goal is to approximate a function that is not 𝐶 ∞ (not differentiable at zero)—or evaluated the performance of their proposed approaches within specific model architectures rather than assessing their fidelity on real-world data. The approach proposed in this paper puts forward a Kernel-based method that forms the basis for producing a polynomial approximation of ReLU, designed considering HE constraints and computation costs, which was evaluated by training on real embedding data from pre-trained LLMs and tested in different scenarios.
4
Implementation
In this research, a second-degree polynomial is proposed to be fitted in order to minimize the combinatorial explosion and prohibitive expenses related to high-degree polynomial Kernel mappings. High dimensionality significantly constrains the practical deployment of high-degree Polynomial Kernels, despite their expressive power. The feature space grows at a rate of 𝑂 (𝑛𝑑 ) as the polynomial degree d increases, leading to a substantial increase in the number of terms. According to Ahle et al. [1], the resulting Kernel matrices become so dense that downstream primitives, such as Kernel PCA or Ridge Regression, require quadratic space and time complexity, which can be prohibitive for large-scale datasets, leading standard Kernel methods to lose their computational efficiency. The sub-sections that follow delve into the details of the implementation process regarding input data selection, kernel regression, input data selection, and polynomial regression. In addition, polynomials of various degrees were investigated prior to the seconddegree polynomial selection. The results of this investigation are also provided in the following sections, including the final polynomial that was obtained through the process for effectively mimicking ReLU considering the core objective of this study to support privacy-preserving LLMs.
4.1
Kernel Regression
As already mentioned, the main difference from applying a polynomial regression directly to ReLU is the smoothness of the function. Since ReLU is not 𝐶 ∞ , a more accurate approximation can be obtained by first replacing it with a smooth function. The kernlab package [11] provides various kernel-based ML methods for approximations of functions, assisting in the design of a kernel function mimicking the ReLU function in this work. The kernel function that was trained on the input data was the hyperbolic tangent kernel tanhdot (4). 𝑘 (𝑥, 𝑥 ′ ) = tanh(⟨𝑥, 𝑥 ′ ⟩ + 1)
(4)
As can be seen in Figure 2, this kernel function was selected because the approximation of ReLU is significant, capturing entirely both positive and negative values, where the negative ones are replaced with zero [15].
Figure 2: Actual ReLU vs Kernel Approx.
4.2
Input Data Selection, Polynomial Regression & Optimal Degree Selection
To approximate the output of the kernel function, a polynomial regression (5) model was trained on the kernel function predictions, where 𝑛 is the degree of the polynomial. 𝑦 = 𝛽 0 + 𝛽 1𝑥 + 𝛽 2𝑥 2 + ... + 𝛽𝑛 𝑥 𝑛 + 𝜖
(5)
Regarding input data, embeddings were extracted from RoBERTa1 and DistilBERT2 using the Stanford Sentiment Treebank (SST-2) dataset [19], a widely used benchmark for sentence-level sentiment classification, where each sentence is labeled as either positive or negative. The two LLM models were utilized in their pre-trained state without architectural changes, configured with a batch size of 32 and a max length of 128 tokens. These hyperparameter values reflect a typical industry trade-off that maintains a balance between the requirement for reliable gradient updates and adequate sequence context for successful model convergence, as well as hardware memory efficiency and computational performance. Furthermore, SST-2 was selected due to its standardized structure and demonstrated dependability in capturing an array of linguistic attributes. SST-2 is built from movie reviews but its sentences are short, varied, and linguistically rich, which makes it a standard choice for evaluating language models and transformer architectures. Because SST-2 is part of the GLUE benchmark suite, strong performance on it is often reported in studies as evidence of a 1 https://huggingface.co/FacebookAI/roberta-base 2 https://huggingface.co/distilbert/distilbert-base-uncased
Sygletos and Papatsaroucha, et al.
model’s general NLP capability, such as [6, 20]. Moreover, the inclusion of both RoBERTa and DistilBERT serves a dual purpose: the former represents the upper bound of Transformer-based accuracy through optimized pre-training, while the latter provides insight into model generalization under architectural constraints. This selection ensures that the findings of this study are representative of both high-capacity and resource-optimized models. A non-linear relationship was fitted between the predictions of the kernel function and the actual tokenized vector of the validation set of SST-2, through polynomial regression. The coefficients were estimated using the least-squares method. Regarding optimal polynomial degree selection, polynomials of degrees 2, 3, 4, and 5 were defined and subsequently integrated as a ReLU replacements in plaintext and encrypted environments. These were developed as surrogate models, fitted via Ordinary Least Squares (OLS) to the predictive outputs of a Tanh-kernel Gaussian Process to ensure accuracy during evaluation. Testing was performed on a system equipped with an NVIDIA H100 GPU3 , which was used to accelerate the kernel fitting and polynomial regression steps, while all HE-related computations and performance measurements were executed on the host CPU. Furthermore, encrypted evaluations were performed under the CKKS HE scheme. The polynomials of various degrees were evaluated based on two competing objectives: • Approximation Accuracy: Minimizing the error between the polynomial and the ReLU function (i.e., how closely the polynomial mimics the original ReLU function) to preserve the model’s decision-making capabilities. • Computational Complexity: Minimizing the computational weight of the operation, specifically multiplicative depth and latency, to ensure the model remains efficient. With regard to the first objective, the evaluation was centered around the Mean Square Error (MSE) (6) to assess approximation accuracy. MSE quantifies the average squared difference between predicted and true values, where a lower MSE value indicates better polynomial performance, as it reflects smaller deviations between predictions and true values. 𝑛
MSE =
1 ∑︁ (𝑦𝑖 − 𝑦ˆ𝑖 ) 2 𝑛 𝑖=1
(6)
Regarding the second objective, the performance was further evaluated based on computational performance and resource usage to identify the viability of the operation. This involved the measurement of inference time (i.e., time required to apply the polynomial to perform the prediction), overall training time, and memory usage on unencrypted and encrypted data. These metrics were used to provide a holistic picture of the trade-offs between approximation accuracy and the hardware requirements needed for model deployment. Contrary to the expectation that higher-degree polynomials would provide a better fit, it is observed in Table 1 that lower-degree polynomials provide a significantly more stable approximation. Degree-2 polynomial achieved the lowest MSE in both plaintext and encrypted environments, with a value of 0.056862 in both cases, while higher-order polynomials, particularly Degree-4 and 3 https://www.nvidia.com/en-eu/data-center/h100/
Degree-5, exhibited significant instability when approximating the ReLU function within the target range, leading to exponentially higher error rates. Notably, the transition to the encrypted domain introduced negligible error (less than 10−5 deviation), confirming the stability of the proposed polynomial implementation within the CKKS scheme. Table 1: Approximation Accuracy by Polynomial Degree Polynomial Degree Degree-2 Degree-3 Degree-4 Degree-5
Plaintext MSE
Encrypted MSE
0.056862 0.784026 4.909682 390.4527
0.056862 0.784037 4.909823 390.4659
Furthermore, the computational performance and memory usage footprints of polynomials across different degrees are detailed in Table 2, where it is observed that Encrypted Inference Time is substantially increased as the polynomial degree rises. Notably, the Degree-5 inference duration (0.068582 s) is found to be approximately 14.7 times slower than the Degree-2 inference (0.004646 s), representing a critical bottleneck in HE, as increased multiplicative depth accelerates noise growth. Similarly, the Total Time metric, encompassing the entire pipeline including the overhead of cryptographic setup, encryption, and decryption, showcases an increase as the polynomial degree rises. However, a surprising decline in memory usage is demonstrated for the 4th and 5th polynomial degrees. It would be expected that resource consumption would also increase as the polynomial degree rises, which is the case when comparing the 2nd and 3rd polynomial degrees in terms of memory usage. This counterintuitive trend is likely attributable to implementation-level factors, such as memory allocation and reuse patterns within the runtime environment, rather than a systematic reduction in memory requirements as polynomial degree increases. Although a reduction of 0.002 MB in memory usage is logged for Degree-5, Degree-2 is identified as the actual winner for efficiency. Superior accuracy is achieved by Degree 2 in 1/9th of the time, which would allow for much higher throughput and lower total hardware costs in a production environment. Table 2: Computational Performance and Resource Footprint Degree Encr. Inf. Time (s) Total Time (s) Memory (MB) Degree-2 Degree-3 Degree-4 Degree-5
0.004646 0.022623 0.046998 0.068582
0.172997 0.583531 1.168747 1.515629
0.154295 0.154436 0.152130 0.151991
Based on the evidence provided by the results of the investigation, the Degree-2 polynomial was selected as the final kernel, as it provides the optimal trade-off by delivering the most accurate approximation of the ReLU function among the various-degree polynomials that were tested, while maintaining the lowest computational footprint, establishing an acceptable balance among expressive capability and computational limits. This choice ensures
Kernel-Based ReLU Approx. for HE-Compatible Privacy-preserving Deep Learning Models
that the solution remains efficient even when scaled to complex neural network architectures in the encrypted domain.
4.3
Algorithm & Final Output
The following algorithm details the process described in the above sub-sections, for approximating the ReLU function by first training a Kernel function on embedding data, and then fitting a seconddegree polynomial to its outputs.
Algorithm 1 ReLU Approximation via Kernel and Polynomial Fitting 1: Let Dtrain
𝑁 , D 𝑀 = {(𝑥𝑖 , 𝑦𝑖 )}𝑖=1 val = {(𝑥 𝑗 , 𝑦 𝑗 )} 𝑗=1 , and Dtest = {(𝑥𝑘 , 𝑦𝑘 )}𝑇𝑘=1 , where 𝑦 = ReLU(𝑥) = max(0, 𝑥).
2: Kernel Training: Train a Kernel function 𝐾 (𝑥, 𝑥 ′ ) to approxi-
mate the ReLU function by minimizing: 𝑁
min LKernel = 𝛼
2 1 ∑︁ 𝐾 (𝑥𝑖 ; 𝛼) − 𝑦𝑖 , 𝑁 𝑖=1
where 𝛼 are the Kernel parameters. 3: Kernel Prediction: Use the trained kernel to predict outputs
on the validation set: 𝑦ˆ 𝑗 = 𝐾 (𝑥 𝑗 ; 𝛼 ∗ ),
∀(𝑥 𝑗 , 𝑦 𝑗 ) ∈ Dval
4: Polynomial Fitting: Fit a second-degree polynomial 𝑝 (𝑥) =
𝑎 0 + 𝑎 1𝑥 + 𝑎 2𝑥 2 to the Kernel predictions by minimizing: 𝑀
min Lpoly = 𝑎 0 ,𝑎 1 ,𝑎 2
2 1 ∑︁ 𝑝 (𝑥 𝑗 ) − 𝑦ˆ 𝑗 𝑀 𝑗=1
5: Final Approximation: The approximated ReLU function is
given by:
5.1
Experimental Design
The evaluation consists of six experimental scenarios, each designed to isolate and evaluate specific aspects of the proposed Kernel Polynomial method. A shared testbed and consistent evaluation protocol are maintained across all scenarios to ensure comparability. • Experiments 1 & 2 – Polynomial Approximation Performance: Using tokenized data as a consistent framework, polynomial approximations are evaluated on tokenized data to establish a baseline under controlled conditions (Experiment 1), and subsequently applied to structured data to evaluate the robustness and generalization when handling complex, structured inputs (Experiment 2). • Experiments 3 & 4 - Model Performance: These experiments focus on downstream impact. In Experiment 3, the MNIST dataset is used to measure the predictive accuracy of two DL models, determining how approximations affect standard neural network architectures. In Experiment 4, the assessment is extended to a transformer-based model, evaluating its performance and adaptability across two district datasets: CIFAR-10 and CIFAR-100. • Experiment 5 - Computational Efficiency: The computational cost of the approximations is evaluated across all scenarios. Factors such as runtime and resource utilization are isolated while model and data conditions remain fixed. • Experiment 6 - Encrypted Environment Performance: This experiment evaluates the approximations’ transition to an encrypted environment, quantifying the trade-off between classification accuracy and the computational slowdown caused by cryptographic overhead to validate the practical viability of the approximations. For polynomial approximation performance, evaluation was centered around MSE as defined earlier in (6) while for the DL and transformer models the accuracy metric was used, as defined in (8), as a straightforward measure of overall classification performance by comparing predicted labels with ground-truth targets.
ReLU(𝑥) = 𝑎 0 + 𝑎 1𝑥 + 𝑎 2𝑥 2 Accuracy =
5.2 After applying all the steps of the methodology, the resulting polynomial obtained—hereinafter Kernel Polynomial method—is the one presented in (7) below: 𝑝 (𝑥) = 0.082261 + 0.495588𝑥 + 0.444488𝑥 2
5
(7)
Evaluation
Given that the primary objective of this work was to approximate ReLU with a HE-compatible polynomial, the evaluation encompasses a comprehensive analysis, including MSE assessments as well as model performance and computational cost measurements. The proposed Kernel Polynomial method is compared against existing benchmarks from the literature (described in Section 3) with regard to both approximation accuracy and performance when applied to real-world challenges in both plaintext and encrypted environments.
Number of Correct Predictions Total Number of Predictions
(8)
Experiment Environment
The transformers library [8] was used to tokenize and convert textual input into vector representations. The torch package in Python4 was used to implement and train the DL models, including the Vision Transformer (ViT). Additionally, the NVIDIA H100 GPU was utilized also for the evaluation process of this study, solely to accelerate polynomial regression and kernel fitting in order to establish a consistent benchmarking environment. On the other hand, all HE-related computations were strictly restricted to the host CPU since standard schemes like CKKS currently lack native GPU acceleration. This approach was utilized to ensure a fair comparison between encrypted and plaintext processing, whereby the precise computational overhead is presented without hardwareinduced bias. By focusing on memory usage metrics, a transparent analysis of the cryptographic overhead and resource consumption was achieved without the confounding factors of non-standardized 4 https://www.python.org/
Sygletos and Papatsaroucha, et al.
GPU acceleration. Consequently, the performance results characterize the system’s memory usage, providing an accurate reflection of high computational demands.
5.3
Evaluation Setup
5.3.1 Independent Variables. The features that were consciously adjusted in each of the six experimental scenarios indicate the independent variables in this study. These include the approach to modeling used (polynomial approximation methods, DL models, and a transformer-based model), the type of data used for evaluation (tokenized and structured data), and the specific evaluation focus of each experiment, such as approximation accuracy, model prediction performance, and computational efficiency. A controlled comparison between various modeling and data conditions is possible since each experimental scenario ensures a consistent testbed while representing a unique configuration of these parameters. 5.3.2 Dependent Variables. The defined independent variables have a direct impact on the dependent variables, and they correspond to the performance results measured under each experimental scenario. These refer to quantitative performance metrics such as MSE for evaluating the efficiency of the polynomial approximations, accuracy metrics for evaluating the predictive performance of the DL and transformer models, and computational cost measurements, including runtime and resource utilization. These metrics allow an unbiased assessment of each modeling approach’s performance under the specified experimental conditions.
5.4
Results
5.4.1 Experiment 1: Baseline Approximation Performance. A series of tests was conducted using multiple sample sets drawn from normal distributions to evaluate the stability and robustness of the various approximations. By generating independently sampled inputs with varying random seeds, the aim was to assess whether performance remained consistent across different distributions. The results in Table 3 depict the MSE for the various ReLU approximation methods, included in each row, tested against data samples from Normal Distributions with increasing levels of variance, showcased in each column. The data revealed that the proposed Kernel Polynomial method is the most accurate in low-tomoderate noise scenarios, while FasterCryptoNets demonstrates greater resilience only under the highest variance perturbations (N(0,1)). Nevertheless, the Kernel Polynomial remained the most stable and reliable approximation overall, as its variance consistently remained below 0.5.
5.4.2 Experiment 2: Approximation Performance on Structured Data. To ensure a realistic evaluation, the SST-2 dataset was derived from different pre-trained LLMs (RoBERTa and DistilBERT). The input to each polynomial consisted of the test set including tokenized text values that were not used in the training process. The output corresponded to either the true values of the ReLU activation function or the predictions generated by different approximations. As it can be seen in Table 4, it was concluded that the proposed Kernel Polynomial method outperformed the other approximations, achieving the lowest MSEs in both cases. It can also be observed that Kernel Polynomial showcases a better performance compared to the FasterCryptoNets method that performed slightly better in the previous experiment, while Chebyshev-3 and -5 methods provided the highest MSEs across all approximation methods. Table 4: MSE of different ReLU approximation methods on tokenized vectors from RoBERTa and DistilBERT. Approximation
RoBERTa-MSE
DistilBERT-MSE
Kernel Polynomial X Squared FasterCryptoNets Chebyshev - 3 Chebyshev - 5
0.002 0.016 0.037 1.641 0.629
0.002 0.033 0.024 1.500 0.548
Moreover, Figure 3 presents a graphical representation of the approximations, including the proposed Kernel Polynomial method. On the x-axis, the tokenized vectors are displayed, while on the y-axis, the corresponding output values of each approximation are shown. The solid black line represents the ReLU function. As can be observed, the X-squared function inadequately accounts for negative values and is very far from positive values. Furthermore, the FasterCryptoNet polynomial exhibits linear behavior and does not account for negative values. The red dashed line represents the proposed Kernel Polynomial method that more accurately approximates ReLU. The Chebyshev methods, which exhibited significantly higher MSE, were excluded from the figure for clarity.
Table 3: MSE of different ReLU approximation methods on vectors from various samples of Normal distribution. Approximation
N(0,0.1) N(0,0.2) N(0,0.5) N(0,0.7) N(0,1)
Kernel Polynomial X Squared FasterCryptoNets Chebyshev - 3 Chebyshev - 5
0.002 0.003 0.045 1.726 0.679
0.001 0.012 0.033 1.628 0.620
0.003 0.113 0.018 1.371 0.478
0.018 0.418 0.018 1.228 0.407
0.147 1.904 0.022 1.048 0.327
Figure 3: Actual ReLU vs Approximations. 5.4.3 Experiment 3: Deep Learning Models Performance. The proposed Kernel Polynomial method was assessed alongside the established polynomials from the literature, which were also included in the previous experiments, to determine if model accuracy is maintained when the proposed solution is implemented.
Kernel-Based ReLU Approx. for HE-Compatible Privacy-preserving Deep Learning Models
A variety of neural network structures constitute the fundamental basis of DL models, providing the foundational mechanisms for learning hierarchical and nonlinear representations from data, enabling a wide range of supervised learning tasks. In this work, FeedForward and Convolutional neural networks (CNNs) were selected for conducting Experiment 3. Feedforward neural networks were used as a baseline due to their simplicity and suitability for supervised classification and regression tasks, while CNNs were selected for their effectiveness in capturing hierarchical spatial features through weight sharing and local receptive fields. The results presented in Table 5 demonstrate that the proposed Kernel Polynomial method achieved a high degree of prediction accuracy, comparable to established polynomial methods. Particularly, in the FeedForward model, an accuracy of 99% is achieved by the Kernel Polynomial, which is identical to the performance of X Squared, while both were slightly outperformed by FasterCryptoNets, by a narrow margin of 0.3%. In addition, the Kernel Polynomial method demonstrated the highest performance (99.2%) when employed in the CNN model. The lowest accuracy levels across both architectures were consistently produced by Chebyshev-based approximations. It is confirmed by these findings that a highly effective formulation is provided by the Kernel Polynomial method despite its simpler form, maintaining competitive performance against more complex state-of-the-art approximations. Table 5: Accuracy of the DL models Approximation
FeedForward
CNN
Kernel Polynomial X Squared FasterCryptoNets Chebyshev - 3 Chebyshev - 5
99% 99% 99.3% 98.7% 98.9%
99.2% 99.1% 99.1% 98.4% 97.8%
5.4.4 Experiment 4: Transformer Model Performance. The Vision Transformer (ViT) adapts the transformer architecture from NLP to computer vision by treating images as sequences of patches rather than spatial grids. Instead of relying on convolutional operations, ViT learns global relationships through self-attention, enabling it to model long-range dependencies across an image. To evaluate and utilize the capabilities of the transformer architecture, the CIFAR-10 [13] and CIFAR-100 [13] datasets were utilized. These datasets, developed at the University of Toronto5 as part of the Canadian Institute for Advanced Research (CIFAR6 ), are considered recognized benchmarks to evaluate a transformer’s ability to generalize across both general and detailed image classification tasks. The various levels of complexity provide an effective basis for evaluating the effectiveness of the model while ensuring that the results remain directly comparable with well-established literature in the field. As shown in Table 6, the suggested Kernel Polynomial method achieved performance comparable to other polynomial approximations within the ViT transformer architecture. The X Squared 5 https://www.utoronto.ca/ 6 https://cifar.ca/
approximation had a slightly higher precision of 65.1% on CIFAR-10, marginally outperforming the Kernel Polynomial by 0.4%. On the other hand, the Kernel Polynomial showed better generalization on the CIFAR-100 dataset, with the highest accuracy of 38.5%. In addition, it is worth noting that higher-degree approximations, such as Chebyshev and FasterCryptoNets, did not demonstrate greater accuracy. Table 6: Accuracy of the ViT transformer Approximation
CIFAR 10
CIFAR 100
Kernel Polynomial X Squared FasterCryptoNets Chebyshev - 3 Chebyshev - 5
64.7% 65.1% 64.2% 60.3% 62.0%
38.5% 38.1% 37.7% 33.2% 35.6%
5.4.5 Experiment 5: Computational Efficiency. The computational cost is the quantity of resources required for the completion of a computer operation. Variables such as the training time needed to train and evaluate a model are often interpreted as computational costs. Computational cost is crucial as it has an immediate effect on an approach’s feasibility, efficiency, and scalability, especially when it involves large datasets or complex algorithms. In this experiment, the training cost, measured in execution time (in seconds), was evaluated on the CIFAR-10 and CIFAR-100 datasets to assess the computational overhead associated with each approximation method. The computational cost of training DL models using diverse approximations are demonstrated in Table 7, showcasing that the X Squared approximation achieved the lowest total latency, encompassing both the training phase and the inference time on the test partition. This can be explained by its simple arithmetic polynomial form that only requires element-wise addition and multiplication, avoiding more computationally costly nonlinear operations, such as divisions or exponentials. Notably, even though the proposed Kernel Polynomial was outperformed by X Sqaured in this experiment, a significant difference in training time is observed when the Kernel Polynomial approximation is compared to higher-degree polynomials, highlighting the efficiency of the proposed method despite being only a second-degree polynomial. Table 7: Computational Cost of the DL models Approximation
FeedForward
CNN
Kernel Polynomial X Squared FasterCryptoNets Chebyshev - 3 Chebyshev - 5
100 sec 91 sec 103 sec 107 sec 118 sec
399 sec 357 sec 409 sec 560 sec 956 sec
Furthermore, the results in Table 8 indicate that the Kernel Polynomial method required the lowest training time for ViT transformers on both CIFAR-10 and CIFAR-100, with 936 s and 931
Sygletos and Papatsaroucha, et al.
s, respectively. Comparable performance was observed for the X Squared approximation, with training times of 937 s on CIFAR-10 and 935 s on CIFAR-100. These two approaches demonstrated a clear computational advantage over the remaining approximation methods. In particular, FasterCryptoNets exhibited higher training times on CIFAR-10 and CIFAR-100, with 944 s and 945 s, respeticely, while Chebyshev-3 required 960 s and 950 s. The highest training cost was observed for Chebyshev-5, with execution times of 1094 s on CIFAR-10 and 1091 s on CIFAR-100. Table 8: Computational Cost of the ViT transformers Approximation
CIFAR 10
CIFAR 100
Kernel Polynomial X Squared FasterCryptoNets Chebyshev - 3 Chebyshev - 5
936 sec 937 sec 944 sec 960 sec 1094 sec
931 sec 935 sec 945 sec 950 sec 1091 sec
5.4.6 Experiment 6: Encrypted Environment Performance. This experiment was conducted to serve as the ultimate validation of the proposed Kernel Polynomial method by transitioning from a plaintext baseline to a fully homomorphic encryption environment using the CKKS scheme and the ViT transformer. The experiment focused on two primary objectives: i) the comparison of the classification accuracy of the ViT model before and after encryption, with the goal to observe the "Accuracy Gap" caused by the conversion of weights and activations into the encrypted domain, depicted in Table 9, and ii) the comparison of the Slowdown Factor, defined as the computational expansion and latency increase caused by cryptographic overhead through the measurement of the total time needed to complete the tasks in the encrypted domain compared to the plaintext baseline, depicted in Table 10, to highlight the cost of privacy. These metrics were benchmarked exclusively on the host CPU, despite the use of the NVIDIA H100 system employed for all experiments, to account for the fact that HE-based computations are strictly CPU-bound. Through this experiment, the practical trade offs required to move from theoretical approximation to a deployable, privacy preserving DL solution are isolated, while assessing how the mathematical stability of the second-degree kernel-based polynomial impacts classification accuracy in a high privacy setting. Table 9: Classification Accuracy Gap (Plaintext vs. Encrypted MNIST) Model Approach Plaintext Acc Encrypted Acc Acc. Gap (%) Kernel Polynomial X Squared FasterCryptoNets Chebyshev - 3 Chebyshev - 5
97.3% 97.4% 97.3% 97.3% 97.6%
68.0% 68.0% 66.0% 62.0% 64.0%
-29.3% −29.4% −31.3% −35.3% −33.6%
Despite having similar performance in plaintext, the accuracy of higher-degree approximations, like Chebyshev-3, dropped significantly in the encrypted domain compared to the proposed Kernel
Polynomial, with 62.0% and 68.0%, respectively. In addition, the Kernel Polynomial exhibited the lowest Accuracy Gap compared to all approximations, at 29.3%, suggesting that the added complexity of higher degree polynomial introduces more noise than benefit within the CKKS context. Table 10: Computational Efficiency and Latency Expansion
Model Approach
Total Exp. Enc. Train Slowdown Peak Memory Time (s) Time (s) Factor Usage (MB)
Kernel Polynomial X Squared FasterCryptoNets Chebyshev - 3 Chebyshev - 5
1864.19 1872.86 1917.99 6780.00 11348.86
1597.46 1605.48 1644.31 5808.09 9730.65
18.5× 18.6× 19.0× 67.3× 109.7×
7.83 7.94 7.81 7.81 7.81
Regarding the cost of privacy, the experiment results showcase that replacing a second-degree polynomial with a higher order polynomial significantly raises latency. The models integrating the Chebyshev-3 and Chebyshev-5 approximations were extremely slow compared to model employing the proposed Kernel Polynomial, requiring 6780s and 11348s, respectively, while the proposed method achieved 1864 s of total experiment time, encompassing the entire pipeline of training, inference, and the models encryptiondecryption processes. This demonstrated that as the polynomial degree rises, it becomes significantly more challenging to operate with in an encrypted setting. Notably, the model integrating the Chebyshev-5 polynomial demonstrated an increase in total experiment duration by over 109 times. Additionally, roughly the same amount of memory (7.8 MB) was consumed by all models across all approximations, while only the model employing the X Square approximation required more than 7.9 MB. It is worth noting that the significant disparities in execution time confirm that latency, rather than memory, constitutes the primary bottleneck. Consequently, the suggested Kernel Polynomial can be considered the most effective approach to high-throughput, privacy-preserving applications considering the exponential costs of the higher-degree approximations. During this experiment, the Kernel Polynomial performed more effectively than higher-degree approximations since it maintained an appropriate balance between mathematical stability and the hardware limits of the encrypted domain. Higher-order polynomials, such as the Chebyshev-5, should fit more effectively in theory, however they are prone to Runge’s phenomenon [9], according to which the use of a high-degree polynomial to interpolate a function over equally spaced points causes the error to increase significantly, resulting in extreme oscillations near the edges of the interval. This can also be observed in Table 1 provided earlier in Section 4, where it is depicted that the MSE rises from 0.056 to over 390 as the polynomial degree increases in encrypted environments. Additionally, the fact that higher-degree polynomial operations require a higher multiplicative depth accelerates the noise development in the CKKS encryption scheme, which lowers the signal-to-noise ratio and makes it harder to classify correctly. The linear derivative of the proposed 2nd-degree Kernel Polynomial ensures stable gradient flow from a training perspective, while the exponential
Kernel-Based ReLU Approx. for HE-Compatible Privacy-preserving Deep Learning Models
characteristic of higher-order derivatives poses a risk of gradient explosion. Consequently, the 2nd-degree configuration is identified as the optimal engineering choice, providing a stable activation environment that avoids the exponential computational slowdown and mathematical volatility associated with higher-order approximations.
5.5
Discussion
The experimental results showed that the proposed approximation performed reliably across a range of experiments. In terms of MSE, the proposed Kernel Polynomial method consistently achieved the lowest values in most scenarios, with the exception of situations with a higher variance in Experiment 1, where FasterCryptoNets performed better. However, the results of approximation accuracy for structured data revealed a significant limitation in the FasterCryptoNets approach, since it fails to account for negative values. In contrast, the Kernel Polynomial method provides a more robust and comprehensive approximation for general tokenized datasets since it successfully handles the full range of tokenized values, including negatives. This indicates that the Kernel-based Polynomial is both accurate and stable under typical input conditions. When applied to DL models, the Kernel Polynomial approach provides predictive performance that is consistent across various architectures, such as FeedForward networks, CNNs, and ViT Transformers. Despite the fact that particular benchmarks, like FeedForward networks, indicate a slight advantage at the FasterCryptoNets, the suggested approach is still within the range of 0.3% of the best result and has an great degree of resilience. In addition, the Kernel Polynomial emerges as the superior approximation as model complexity increases toward ViT architectures with the CIFAR100 dataset. This performance indicates that whereas simpler approximations, such as X Squared, can be used to perform shallow tasks, the Kernel Polynomial method can be more easily scaled to high-dimensional feature space without the loss in accuracy, as in Chebyshev approximations. Notably, when moving from plaintext to the encrypted domain, the proposed approach maintains this consistency alongside low encrypted training time, at a low Accuracy Gap and Slowdown Factor, which can be invaluable in large-scale encrypted DL models. In summary, through the evaluation process is demonstrated that the proposed Kernel Polynomial method offers a better option due to its lower MSE values, which confirmed the effectiveness of the approximation in capturing the target behavior with minimal deviation, its overall consistency and the unique advantages it provides, such as lower training time and higher model accuracy, as well as its continued effectiveness even when slightly outperformed. Considering its competitive performance alongside its lower approximation complexity and reduced computational overhead, the proposed Kernel Polynomial represents a robust and efficient activation approximation, considering the primary objective of this study in approximating ReLU with an HE-compatible polynomial.
6
Conclusion
This work introduced a Kernel Polynomial approximation method of the ReLU activation function, designed to be efficient within HE frameworks that can address privacy concerns in NLP settings,
while maintaining high accuracy. Unlike prior approaches, the proposed method was trained on real embedding vectors from pretrained LLMs. Through systematic comparison with existing approximations identified through the literature, including X-Squared, FasterCryptoNets, and Chebyshev polynomials, the proposed method demonstrated significantly lower approximation error across various evaluation experiments, while achieving comparable predictive accuracy when integrated into both DL and transformer architectures, effectively bridging the performance gap between encrypted and unencrypted execution and secure inference in LLMs. The intriguing aspect of the assessment is that polynomials of higher degrees do not inherently guarantee a more precise approximation or better classification accuracy when integrated within NLP tasks. The practical demonstration showcases that for smooth functions, such as Kernel-based functions, exceptionally low approximation errors can be achieved even with lower-degree polynomials while maintaining high classification accuracy and lower computational costs. Future research steps aim to overcome recognized limitations in high-variance contexts through the investigation of adaptive hybrid models. The implementation of the proposed Kernel Polynomial approximation method within LLMs will also be investigated, with an emphasis on enhancing processing speeds through hardware-level HE acceleration and coefficient optimization. Additionally, the resistance of the proposed Kernel Polynomial method to adversarial tokenized inputs will be further examined, since this is an essential requirement for implementation in high-security, privacy-preserving environments. Finally, to further illustrate the adaptability of the method in large-scale encrypted DL, its effectiveness will be evaluated across several data types, beyond image classification that was investigated in this study.
References [1] Thomas D. Ahle, Michael Kapralov, Jakob B. T. Knudsen, Rasmus Pagh, Ameya Velingker, David Woodruff, and Amir Zandieh. 2020. Oblivious Sketching of High-Degree Polynomial Kernels. arXiv:1909.01410 [cs.DS] https://arxiv.org/ abs/1909.01410 [2] E. W. Cheney. 1982. Introduction to Approximation Theory. AMS Chelsea Publishing, 201 Charles Street, Providence, RI 02904-2213, USA. [3] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2016. Homomorphic Encryption for Arithmetic of Approximate Numbers. Cryptology ePrint Archive, Paper 2016/421. https://eprint.iacr.org/2016/421 [4] Edward Chou, Josh Beal, Daniel Levy, Serena Yeung, Albert Haque, and Li FeiFei. 2018. Faster CryptoNets: Leveraging Sparsity for Real-World Encrypted Inference. arXiv:1811.09953 [cs.CR] https://arxiv.org/abs/1811.09953 [5] Li Deng. 2012. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine 29, 6 (2012), 141–142. [6] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. arXiv:1810.04805 [cs.CL] https://arxiv.org/abs/1810.04805 [7] Norman R. Draper and Harry Smith. 1998. Applied Regression Analysis. [8] Hugging Face. 2024. Transformers: State-of-the-art Machine Learning for Pytorch, TensorFlow, and JAX. https://huggingface.co/transformers. Accessed: 2025-05-23. [9] Bengt Fornberg and Julia Zuev. 2007. The Runge phenomenon and spatially variable shape parameters in RBF interpolation. Computers & Mathematics with Applications 54, 3 (2007), 379–398. doi:10.1016/j.camwa.2007.01.028 [10] Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. 2016. CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy. In Proceedings of The 33rd International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 48), Maria Florina Balcan and Kilian Q. Weinberger (Eds.). PMLR, New York, New York, USA, 201–210. https://proceedings.mlr.press/v48/giladbachrach16.html
Sygletos and Papatsaroucha, et al.
[11] Alexandros Karatzoglou, Alex Smola, and Kurt Hornik. 2024. kernlab: KernelBased Machine Learning Lab. https://CRAN.R-project.org/package=kernlab R package version 0.9-33. [12] Tanveer Khan and Antonis Michalas. 2023. Learning in the Dark: PrivacyPreserving Machine Learning using Function Approximation. In 2023 IEEE 22nd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). IEEE Computer Society, Los Alamitos, CA, USA, 62–71. doi:10.1109/TrustCom60117.2023.00031 [13] Alex Krizhevsky. 2009. Learning Multiple Layers of Features from Tiny Images. https://api.semanticscholar.org/CorpusID:18268744 [14] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998. Gradientbased learning applied to document recognition. Proc. IEEE 86, 11 (1998), 2278– 2324. [15] Vinod Nair and Geoffrey E. Hinton. 2010. Rectified Linear Units Improve Restricted Boltzmann Machines. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), Johannes Fürnkranz and Thorsten Joachims (Eds.). Omnipress, Haifa, Israel, 807–814. http://www.icml2010.org/papers/432. pdf
[16] OpenMined and Zama. 2024. TenSEAL: Homomorphic encryption library for PyTorch tensors. https://github.com/OpenMined/TenSEAL. Accessed: 2025-0523. [17] Allan Pinkus. 1985. n-Widths in Approximation Theory. Springer-Verlag, SpringerVerlag Berlin Heidelberg 1985. [18] Bernhard Schölkopf and Alexander J. Smola. 2002. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA. [19] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. 2013. Recursive Deep Models for Semantic Compositionality Over a Sentiment Treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, David Yarowsky, Timothy Baldwin, Anna Korhonen, Karen Livescu, and Steven Bethard (Eds.). Association for Computational Linguistics, Seattle, Washington, USA, 1631–1642. https://aclanthology.org/D13-1170/ [20] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. 2019. GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding. arXiv:1804.07461 [cs.CL] https: //arxiv.org/abs/1804.07461