# Training Large Scale Polynomial CNNs for E2E Inference over Homomorphic
Encryption

Moran Baruch 1 2 Nir Drucker 1 Gilad Ezov1 Yoav Goldberg2 3 Eyal Kushnir1
Jenny Lerner1 Omri Soceanu1 Itamar Zimerman1
1IBM Research 2Bar-Ilan University 3AI2

###### Abstract

Training large-scale CNNs that during inference can be run under Homomorphic
Encryption (HE) is challenging due to the need to use only polynomial
operations. This limits HE-based solutions adoption. We address this challenge
and pioneer in providing a novel training method for large polynomial CNNs
such as ResNet-152 and ConvNeXt models, and achieve promising accuracy on
encrypted samples on large-scale dataset such as ImageNet. Additionally, we
provide optimization insights regarding activation functions and skip-
connection latency impacts, enhancing HE-based evaluation efficiency. Finally,
to demonstrate the robustness of our method, we provide a polynomial
adaptation of the CLIP model for secure zero-shot prediction, unlocking
unprecedented capabilities at the intersection of HE and transfer learning.

##  1 Introduction

We are interested in the problem of training Convolutional Neural Networks
(CNNs) in a way that allows inference on encrypted data, without the owner of
the model being exposed to either the inputs or the outputs. This is
achievable through Homomorphic Encryption (HE), see e.g., [18, 1, 5]. Most
modern HE schemes, however, limit network operations to polynomials, creating
training and inference challenges.

Training large-scale polynomial CNNs is a challenging task that often fails to
achieve the same performance as the original network. Thus, previous studies
have only achieved promising results on shallow networks [26, 5] and their
methods have not scaled up for larger networks or large datasets such as
ImageNet [19].

The hardness of training polynomial networks is well established, as we
explain in Sect. 2. Previous studies in HE (e.g., [44, 40, 38]) focused on
modifying pre-trained networks by substituting non-polynomial ReLU activations
for polynomial approximations, however, when applied naively to deep networks,
it can cause explosions or imprecise results. In this study, we observe that
one of the factors for those explosions is the input range of the activation,
which dominates the approximation error (Fig. 3). Hence the approximation
requires extremely high-degree polynomials, leading to computational
inefficiencies or instability. To address this, we develop a novel training
method that handles the input range during the fine-tuning process, which
enables approximating activations using low-degree polynomials. This method
allows for the first time the training of HE-friendly CNNs on large-scale
networks like ResNet [31] and ConvNeXt [47], over large datasets such as
ImageNet.

Another challenge for running encrypted inference is reducing the inference
latency costs, which are significantly influenced by two key factors: the
multiplication depth of high-degree polynomials and the HE chain-index
mismatch resulting from skip-connections, as will be identified in Obs. 3.1.

To this end, we propose new design and training techniques for polynomial CNNs
that translate to latency acceleration of the inference process of polynomial
CNNs under HE. Specifically, in Sect. 3.2 we provide a solution to efficiently
handle skip-connections under HE, through chain index-aware design, resulting
in a substantial reduction in inference time. For instance, when employing the
HElayers SDK, a notable speedup factor of 2.5 is achieved. Additionally, in
Sect. 3.3, the paper provides an analysis of selecting an appropriate backbone
to minimize the computational resources needed when using HE.

#### Our Contributions.

  1. 1.

Our main contribution is a novel training method that is grounded by our
insight from Sect. 3.1, which handles the range to the non-polynomial layers.
This method enables us to achieve low-degree polynomial approximation, while
maintaining the accuracy of the original model.

  2. 2.

We provide several insights about the design choices of HE-friendly CNNs,
which can lead to better latency efficiency with a lower approximation error.
Specifically, we refer to techniques such as handling neural activations
(Sect. 3.1), Skip-Connections (SCs) (Sect. 3.2), and the CNN backbone in the
context of HE (Sect. 3.3) .

  3. 3.

Using the above techniques, we demonstrate, for the first time, the
feasibility of training HE-friendly (polynomial) CNNs such as ConvNeXt and
ResNet over large scale datasets. These models achieve comparable accuracy to
state-of-the-art (SOTA) approaches when trained on realistic datasets like
ImageNet (see Tab. 2). Our code is available online 111For reproducing our
main results, please refer to our anonymous repository: shorturl.at/lvNXZ. The
entire Git repository will be shared upon acceptance..

  4. 4.

We extend the capabilities of employing secure transfer learning over HE. This
allows for the first time several key techniques such as encryption of the
entire pre-trained model, fine-tuning the entire model rather than optimizing
the last layer, and exploiting ZSL as an alternative to training on encrypted
data (see Sect. 5). This demonstration represents a significant milestone in
making HE applicable.

#### Empirical Contributions.

We implemented and tested our methods using the HElayers framework [1]; please
see the results in Section 4. Consequently, we report the first non-
interactive Privacy-Preserving Machine Learning (PPML) solution that can run
secure prediction of the above large and accurate CNNs over large-scale
datasets in minutes, which proves the practicality of secure prediction HE-
based solutions. In addition, we take polynomial networks to the next level,
by demonstrating the practicality of our approach on the first secure zero-
shot and multi-modal foundation model over encrypted data using CLIP (Section
5).

##  2 Background

To clarify the difficulty of producing polynomial networks several theoretic
intuitions and proofs were proposed. For example, [74] proved that under some
conditions polynomial Feed-Forward Networks (FFNs) are unstable, and concluded
that the more complicated a polynomial activation is the more likely that it
will face instability. Another paper, [28], suggests that the problem with
polynomial activations is that the gradients and outputs are unbounded and can
be arbitrarily large, in contrast to other activations such as ReLU, GELU,
Sigmoid, or TanH. The paper also points out that in deeper networks
$f_{(d,l)}$ with $l$ layers and $d$-degree polynomial activations, the
gradients explode exponentially in the degree of the entire network, since for
input $x>1,\lim_{x\rightarrow\infty}f_{(n.l)}(x)/x=\infty$. Additionally,
[16], [28] and [27] attempted to implement deep polynomial networks but faced
optimization instability. They resolved the issue by incorporating non-
polynomial components like tanh or max, resulting in a non-polynomial model.

#### Polynomial Approximations.

Instead of training a polynomial network from scratch, a commonly used method
is approximating non-polynomial functions of pre-trained networks using
polynomials. For example, the $\operatorname{ReLU}$ activation function is
approximated by a polynomial in the studies of [42, 65, 53, 33] or is replaced
by a trainable polynomial in [5]. One commonly used way to approximate a
function is by using the well-known Remez algorithm [60] and its follow-up
algorithms [55, 20], which were proved to be optimal tools for finding the
polynomial approximation of a function $f(x)$ given the range of $x$ and
polynomial degree. Nevertheless, the range of the different CNN layers’ input
$x$ may not be known in advance, which may lead to a non-negligible error due
to the approximation’s poor performance outside of the conditional range. See
more details in Appendix. E. One interesting work is [44] that approximated
$\operatorname{ReLU}$ using a composition of 3 polynomials of degrees {15, 27,
29}. While the reported accuracy was only 0.11% lower than State-of-the-Art
(SOTA), the authors of [44] did not test their approach in a low-precision
environment such as HE.

#### Motivation for training polynomial networks.

Our principal motivation in this work is to enable E2E-secure inference (in
contrast to client-aided based solutions, see B) that uses HE. This will allow
data owners to use third-party cloud environments while complying with
regulations such as GDPR [21] and HIPAA [13]. An example of a problem-setting
is provided in Fig. 3. For brevity, we only claim that HE-friendly CNNs should
be polynomial and refer the interested reader to App. A for more details about
HE.

#### Related art.

HE-based secure prediction solutions should be both efficient and accurate. In
App. B we provide a detailed comparison of SOTA HE-based PPML solutions. Here,
we only summarize that the most efficient solutions today [40, 38] both
reported accuracy only for CIFAR-10/100, where [38] mentions that they have
not yet succeeded in training ResNet-18 over ImageNet. In contrast, as
mentioned above, the most accurate attempt to run an HE-friendly inference is
of [44] who did not implement their solution with HE. Followup works e.g.,
[24] claimed that due to the large polynomial degree (e.g., more than 10K),
the solution latency when evaluated under HE is large, and [43] only showed
practicality under HE for ResNet-20 and CIFAR-10. Furthermore, our experiments
(see supplementary material) were not able to reproduce the results of [44]
for ResNet-50/150 over ImageNet, even when using 96-bit floating-point
precision on plaintext. In conclusion, our work provides the first accurate
and performant implementation of large polynomial CNNs on large datasets.

Figure 1: (Motivation) An E2E PPML solution for running CNNs over HE. The flow
involves a client and a cloud server. The client trains a polynomial (HE-
friendly) CNN model, either encrypts it or not, and uploads the model to the
cloud. Then, the client requests from the cloud to run this model on its
behalf. For that, the client encrypts its private samples and uploads them to
the cloud, which processes the encrypted data using the (possibly encrypted)
model, and returns the results to the client for decryption.

Figure 2: (Problem) Maximal error when using the $p_{\alpha=7,10,14}$
polynomials of [44] to approximate $\operatorname{ReLU}$ over different ranges
($B$). Small error is achieved through a small range or a large polynomial
degree.

Figure 3: (Solution) range-aware training. Here, accuracy and ranges of
ConvNeXt trained on CIFAR-10.

##  3 Training Method

Our method for generating practical HE-friendly CNNs is based on three
essential factors: a) Minimizing input ranges to activation layers and
generating suitable polynomial approximations based on these ranges (Sect.
3.1); b) Effectively handling of SCs under HE (Sect. 3.2); and c) Choosing the
appropriate backbone architecture (Sect. 3.3).

###  3.1 Input Range Tuning for Accurate Polynomial Approximation of
Activation Functions

Approximating activation functions with polynomials accurately and
efficiently, and applying them in deep CNNs is a hard task. We identified that
the main issue in approximating non-polynomial networks is that the input
range for these polynomial approximations is not known in advance, often
spanning over scale of hundreds [44], and thus the deviation of the original
activation from the approximated activation increases (see Fig. 3, Observation
E.1). In practice, when dealing with large networks with multiple approximated
layers, the error from the initial layers is accumulated and eventually causes
explosions and instability.

Traditionally, to reduce the approximation error and thus the accumulated
error, the network designer is forced to use high-degree polynomials [44].
However, as detailed below, we take a different approach, in which we reduce
the polynomial degree by reducing the input range for every polynomial. This
reduces the accumulated error and hence the chances of a network explosion to
occur.

Alg. 1 provides a high-level overview of our method. Let $\mathcal{M}$ be a
pre-trained non-polynomial model, $\operatorname{NPL}$ be the ordered list of
length $L$, that contains the non-polynomial layers of $\mathcal{M}$. Let
$c_{i}=|\operatorname{NPL}[i]|$ be the number of neurons at layer $i$ in
$\operatorname{NPL}$, $\mathbf{x}^{i}$ be the vector input for that layer and
$d$ be the polynomial degree.

#### The first phase

of the algorithm involves adding a novel regularization term, range loss
($rl$), to $\mathcal{M}$’s original objective function. This loss term aims to
reduce the range of inputs to the $\operatorname{NPL}$ layers around the value
of 0, which can be depicted as
$rl=\lVert(\lVert\mathbf{x}^{i}\rVert_{p})_{0\leq i<L}\rVert_{q}$, where we
often set $p=\infty$ and $q\in\\{1,2,\infty\\}$. The new loss function for
input $(X,y)$ is defined as: $loss(\mathcal{M})=CE(\mathcal{M}(X),y)+w\cdot
rl$, where CE is the Cross Entropy loss on the model.

When using the $L_{1}$ norm for $rl$ and when the size of $\operatorname{NPL}$
increases, the range loss term may become more significant than the original
CE loss, which is why we introduce a weight $w$ to balance the two terms. In
Step 2, the algorithm fine-tunes $\mathcal{M}$ using the new loss function.
This phase ends when the loss is minimized, at which point the activation
functions should expect inputs in the minimal range so that the model
preserves its performance. Fig. 3 demonstrate the effectiveness of this
procedure.

#### In the second phase of Alg

. 1 (Steps 3-4), the framework uses empirical analysis to estimate the input
ranges per layer $[x^{i}_{min}<x^{i}_{max}]_{0\leq i<L}$, with confidence
level $\alpha$. This is done by approximating the ranges of the input to each
activation function by sampling a subset of the training data that has not
been used for training or validation. This stage takes into account the error
generated by the approximation of the previous layer, i.e., it pre-bounds the
error with $e_{i}$ and expects that in the last step, the approximation would
be bounded by $|p_{i}(x)-f_{i}(x)|<e_{i}$.

Algorithm 1 Training HE-friendly CNNs

Input: A pre-trained CNN model ($\mathcal{M}$), a training set
($\mathcal{DS}_{train}$), a small disjoint set ($\mathcal{DS}_{trainRange}$),
and a positive integer degree ($d$).

Output: A trained HE-friendly model $(\mathcal{M}_{HE-f})$.

1: Add a regularization range loss term $rl$ to loss($\mathcal{M}$).

2: Fine-tune $\mathcal{M}$ over $\mathcal{DS}_{train}$ until the input ranges
to the $\operatorname{NPL}$ layers are small enough and the network
performance is satisfying. The resulting model is $\mathcal{M}$’.

3: Evaluate $\mathcal{M}$’ over $\mathcal{DS}_{trainRange}$ and compute the
pairs $(\min{\mathbf{x}^{i}},\max{\mathbf{x}^{i}})_{0\leq i<L}$ per sample.

4: Using the above pairs, estimate the range
$([x^{i}_{min},x^{i}_{max}])_{0\leq i<L}$ for values of $\mathbf{x}^{i}$ with
confidence level $\alpha$.

5: Replace the functions $f_{i}(x)$ of the $\operatorname{NPL}$ layers with
polynomial approximations $P_{i}(x)$ of degree $d$ over the estimated ranges
$[x^{i}_{min},x^{i}_{max}]$. The new model is $\mathcal{M}_{HE-f}$.

6: Fine-tune $\mathcal{M}_{HE-f}$ over $\mathcal{DS}_{train}$ until
convergence.

7: return $\mathcal{M}_{HE-f}$.

#### In the last phase

(Steps 5-6), we replace the original activation functions with polynomial
approximations, using e.g., Remez or the faster but less accurate least-square
polynomial fit function. Each activation layer is replaced by a separate
polynomial that has been designed for the estimated range. The output of the
algorithm is an HE-friendly model $\mathcal{M}_{HE-f}$. However, since the
polynomial activation layers provide only an approximation of the original
activations, the accuracy of the model is normally decreased. Therefore, we
added Step 7 to fine-tune the model for a few more epochs with the added $rl$
term until the desired performance is achieved.

(a) Poly. approx. error

(b) Approx. polynomials

(c) Min/max ranges/epoch

(d) Test accuracy epoch

Figure 4: $\operatorname{ReLU}$ (red) versus $\operatorname{GELU}$ (blue).
Panel (a): Maximum error $|p(x)-f(x)|$ for a different degree of polynomial
approximation $p(x)$ of $\operatorname{ReLU}$/$\operatorname{GELU}$ in
different ranges (x-axis). Panel (b): A 4- degree polynomial approximation of
$\operatorname{ReLU}$/$\operatorname{GELU}$. In both (a) and (b),
$\operatorname{GELU}$ is better approximated. Panel (c) Error range [min, max]
(y-axis) after $l$ training epochs (x-axis). Panel (d): Model accuracy
(y-axis) after training ConvNeXt with
$\operatorname{ReLU}$/$\operatorname{GELU}$ for (x-axis) epochs: In the
initial 10 epochs, max-pooling and LayerNorm are substituted with HE-friendly
components (mean-pooling and BatchNorm). Our range-aware training technique is
then applied from epochs 10 to 50. Finally, at epoch 50, the activations are
replaced by polynomials. While the ranges exhibit similarity, only
$\operatorname{GELU}$ can be precisely approximated.

###  3.2 Efficiently Handling Skip-Connections in HE

CKKS and other HE schemes have a limit on the number of multiplications that
can be performed on a ciphertext, known as the "multiplication chain index”
(a.k.a. modulus chain index) or $\operatorname{CIdx}$. This limit is set by
the client to achieve the desired level of security and performance [3]. Every
ciphertext starts with a $\operatorname{CIdx}$ of $0$. After each
multiplication of two ciphertexts with $\operatorname{CIdx}$ of $x$ and $y$,
the result has a $\operatorname{CIdx}$ of $\max(x,y)+1$. Once a ciphertext’s
$\operatorname{CIdx}$ reaches the limit, it can no longer be multiplied,
unless a costly $\operatorname{Bootstrap}$ operation is performed to reduce
its $\operatorname{CIdx}$, or even reset it back to $0$. One design goal when
generating an HE-based solution is to minimize the number of
$\operatorname{Bootstrap}$ invocations. Hereafter, we define the term
multiplication depth to be the longest chain of sequential multiplication
operations in an HE-evaluated function. As noted above, longer chains, i.e.,
higher multiplication depths, result in more bootstrapping operations. Using
these definitions, we observe that

######  Observation 3.1.

Given a Skip-Connection layer $SC_{f}(x)=x+f(x)$, where $f$ is a combination
of some layers. When running under HE,
$\operatorname{CIdx}\left(SC_{f}(x)\right)\in\\{\operatorname{CIdx}(x),\operatorname{CIdx}(f(x))\\}$
and when $\operatorname{CIdx}(x)\neq\operatorname{CIdx}(f(x))$ the SC
implementation may increase the overall multiplication depth of the network by
$|\operatorname{CIdx}(x)-\operatorname{CIdx}(f(x))|$.

In practice, the cost of $SC_{f}(x)$ can be even higher because the input $x$
or $f(x)$ may need to go through some transformation before adding it to
$f(x)$. This is the case with the HElayers SDK, which requires input to an
$\operatorname{ADD}$ operator to use the same ciphertext parameters.
Specifically, it applies transformations $g,h$ on $x$, $f(x)$, respectively,
and replaces $S_{f}(x)$ with the operator $S_{f,g,h}(x)=g(x)+h(f(x))$. In this
case, for Observation 3.1, we need to consider $\operatorname{CIdx}(g(x))$
instead of $\operatorname{CIdx}(x)$ and $\operatorname{CIdx}(h(f(x)))$ instead
of $\operatorname{CIdx}(f(x))$.

Given the latency costs associated with implementing SCs under HE, we propose
two methods for placement and removal of SCs, where our goal is to maintain
accuracy while improving latency. Note that this was not required previously
for commonly used networks where addition is free. However, with our methods,
we can offer new network designs that are more suitable for the HE world.

#### Removing Skip-Connections.

Our first method aims to generate a CNN without SCs while maintaining near-
SOTA performance. Removing SCs directly will result in bad performance as
previously demonstrated in the study of He et al. [31] due to the gradient
flow across layers. Therefore, in our method, we start by training a CNN to
achieve SOTA performance while using SCs. We gradually eliminate them by
replacing $S_{f,g,h}(x)$ with a new layer $S^{\prime}_{f,g,h,a}(x)=a\cdot
g(x)+h(f(x))$. We continue training for $N$ more epochs. At every epoch index
$0<E\leq N$, we set $a=(1-\frac{E}{N})$. After $N$ epochs, $a=0$ and the SCs
are removed. Finally, we continue training for several more epochs.

#### Skip-Connection Placement.

When SCs are required, we propose Alg. 2 for designing efficient HE-friendly
CNNs. The algorithm uses as input a network architecture $\mathcal{A}$ and an
HE network analyzer ($\operatorname{HEAnalyzer}$), such as the optimizer of
HElayers. We start by removing all SC layers and feeding the new network
$\mathcal{A}$’ to the analyzer. For every pair of layers in the network $i<j$,
the analyzer computes the latency costs of adjusting the output $x$ and $f(x)$
of layers $i$, $j$, using transformations $g,h$, respectively, and the need
for $\operatorname{Bootstrap}$ operations. It returns the results in the
matrix $costsMatrix$ of size $L\times L$, where $L$ is the number of layers in
$\mathcal{A}$’. For $i\geq j$, $costsMatrix[i][j]=\infty$. Using
$costsMatrix$, we can now place SCs to minimize the latency overhead while
maintaining accuracy. One possible heuristic is to start from layer $i=0$ and
find $j=\operatorname*{arg\,min}_{j}{\left(costsMatrix[i][j]\right)}$, place
an SC between layers $i$ and $j$, and repeat with $i=j+1$. Note that when
adding SC in a way that increases $\operatorname{CIdx}(h(f(x)))$ the costs
matrix should be re-computed. Alg. 2 already considers the bootstrapping costs
discussed earlier, and is most likely to choose SCs for layers with
$\operatorname{CIdx}(g(x))\leq\operatorname{CIdx}(h(f(x)))$.

Figure 5: Latency breakdown for running ResNet-50 over ImageNet using HElayers
1.5.2. Here, $g(x)$ is the SC adaption of HElayers. Other refers to BN, FC,
and AVG-Pool layers.

Algorithm 2 SC HE-friendly design

0:

Input: A network architecture ($\mathcal{A}$) and an HE analyzer
$\operatorname{HEAnalyzer}$.

Output: An HE-friendly NN architecture $\mathcal{A}$’.

0:

1: Set $\mathcal{A}$’ to be $\mathcal{A}$ without SCs.

2: $costsMatrix_{L,L}=\operatorname{HEAnalyzer}(\mathcal{A}^{\prime})$

3: Place SCs in $\mathcal{A}$’ between layers $i,j$ considering the latency
costs $costsMatrix[i,j]$ until reaching the desired accuracy.

4: Return $\mathcal{A}$’

4:

###  3.3 Choosing the Right Backbone

Many variations of ResNet backbones have been proposed over the years [47, 70,
71, 34, 67]. While most prior HE-related works use vanilla ResNet [40, 44, 4]
(see App. B), its superiority has not been proven or explored in the context
of HE. Surprisingly, even seemingly insignificant design choices such as the
backbone choice can have a large performance impact when working with
encrypted data. Therefore, we decided to study and compare three ResNet
backbones: the original ResNet [31], ConvNeXt [47], and DenseNet [34].

#### ConvNeXt.

ConvNeXt is a modern variant of ResNet, which achieves the highest performance
[69]. It involves two relatively minor design decisions that make it
attractive when working over encrypted data: 1) it has a reduced number of
activations; 2) it uses $\operatorname{GELU}$.

Every ConvNeXt block includes only one activation function, as opposed to
three in ResNet blocks. Although this only provides a relatively small
improvement of ($0.7\%$), it has crucial implications in HE since smaller
numbers of non-polynomial components reduce the overall multiplication depth
by a factor of around $3$, making it easier to achieve an HE-friendly network.

ConvNeXt uses the $\operatorname{GELU}$ [32] activation function instead of
$\operatorname{ReLU}$. Fig. 4 Panels (a) and (b) show that
$\operatorname{ReLU}$ is much more difficult to approximate in comparison with
$\operatorname{GELU}$, specifically in the areas near 0, where
$\operatorname{ReLU}$ is not smooth. Panels (c) and (d) show that using
$\operatorname{GELU}$ is more robust, allowing us to reduce the polynomials’
degree. The result is that the overall replacement process is easier, and the
aggregated multiplication depth is smaller.

#### DenseNet.

The DenseNet network uses a unique type of SCs. Each layer receives the
outputs of all preceding layers as inputs, and its output is used as input for
all subsequent layers. While this architecture has advantages in terms of
optimization, it increases the number of bootstrapping operations, since it
forces bootstrapping after almost every DenseNet block. Thus, it is not
recommended for HE-based PPML solutions.

##  4 Experiments and Results

To test our methods, we performed a series of experiments, which we report
next. For brevity, we refer to ResNet-XX as RNXX. All training experiments
used the PyTorch framework.

#### HE-Friendly large-scale CNNs.

We start by evaluating the accuracy of our proposed training method for HE-
friendly models on three datasets: CIFAR-10 [39] and the large-scale datasets:
ImageNet [19] and Places-365 [73]. All datasets were evaluated at a resolution
of $224\times 224\times 3$. The accuracy results, presented in Tab. 2, were
analyzed in three stages: (1) the original, non-HE-friendly model, (2) the
original model after replacing max-pooling with mean-pooling but with non-
polynomial activations, and (3) the proposed HE-friendly model with polynomial
activations. Additionally, we compared our results to those reported by [40],
who evaluated a ResNet-56 model on CIFAR-10 using images of size $32\times
32\times 3$. While they also report on other networks, we compared our results
to their ResNet-56 as it is the closest to ResNet-50. The smaller image size
used by Lee et al. [40] may have contributed to the lower accuracy observed in
their experiments.

During the range minimization phase (Alg. 1, Step 2), the ranges to the
activation layers are large, which leads to the $rl$ loss being significantly
higher than the original model loss. To this end, we set $w$ to be in the
ranges 0.0001-0.001 and 0.01-0.1, before (Step 2) and after (Step 5), resp.,
replacing the $\operatorname{ReLU}$ activation with a polynomial, the exact
value depends on the dataset. The polynomial degree used in these experiments
is set to 18, which provides a good approximation for small ranges of around
$[-10,10]$, as in our case. Tab. 2 shows that the HE-friendly models trained
by our method preserved the original accuracy when applied on CIFAR-10 and
Places-365, and reached 94% accuracy when trained on ImageNet for ResNet-101
and 96% for ConvNext-T.

#### HE-Friendly Skip-Connections.

Tab. 3 demonstrates the effect of using our method of carefully removing SCs
on secure classification latency. For that, we use ResNet-50 and set the
polynomial activation degree to be 2, 8, 16 or 18. We see that using HE-
friendly skip-less models can save up to $75\%$ of the bootstrapping as well
as provide significant speedup. Recall that bootstrapping is a critical
bottleneck in inference under HE, see App. D.

When it comes to accuracy, the situation is more complicated. We used our
training method with only $18$-degree polynomial activation functions. We
found that accuracy degradation is dependent on whether the network starts
with pre-trained weights. Without pre-training, we observe that HE-friendly
ResNet-50 and skip-less HE-friendly ResNet-50 achieve $93.72\%$ and $93.21\%$,
resp., where the total degradation is relatively small ($0.53\%$). In
contrast, when using a pre-trained model, the impact on accuracy is more
significant, see Tab. 1. This phenomenon is somewhat predictable, since
removing the SCs changes the network’s dynamics, thus diminishing the impact
of pre-training data.

#### HE-Friendly Backbones.

We tested different settings for CNNs, including various sizes of ResNets (18,
50 ,101), ResNet-50 without SCs, ResNet-50 with adaptive removal of SCs, and
two variations of ConvNeXt-Tiny, which is equivalent to ResNet-50: one with a
polynomial degree of 4, and the other with a polynomial degree of 8. All of
the experiments were applied on CIFAR-10 at a resolution of $224\times
224\times 3$. Results are detailed in Tab. 1. We find that the ConvNeXt-Tiny
model with $4$-degree polynomial activations has a significantly lower
multiplication depth compared to the ResNet-50 model with 18-degree polynomial
activations. Despite similar numbers of blocks, FLOPs, and accuracy, the
number of $\operatorname{Bootstrap}$ operations in ConvNeXt-Tiny is reduced
from $7{,}712$ to $1{,}360$. This improvement is significant, as the bootstrap
operation is a major bottleneck in the inference time of deep CNNs, as shown
in the profiling provided in App. D. Results are provided in Tab. 1. When
implementing an HE-friendly ConvNeXt, we replaced the LayerNorm layers with
BatchNorm layers, which resulted in some degradation of accuracy. We also
assume that the replacement also negatively impacts the model’s transfer-
learning capabilities. For a comprehensive overview of the experimental setup
we use for evaluation over HE via HElayers SDK, please see Appendix C

Table 1: Accuracy of HE-friendly backbones over CIFAR-10 $(224\times 224\times 3)$. Arch. | Original | HE-friendly
---|---|---
RN18 | 99.36 | 99.3
RN50 | 99.58 | 99.5
RN101 | 99.8 | 99.58
RN152 | 99.9 | 99.6
RN50 no skip | 93.5 | 93.58
ConvNext-Tinyd=4 | 97.84 | 97.03
ConvNext-Tinyd=8 | 97.84 | 97.34
RN5032×32 | 97.8 | 97.0
RN56-[40]32×32 | 97.8 | 93.27

Table 2: Accuracy results of training ResNet (RN) and ConvNeXt-Tiny (CNXT) over different datasets. The results include the original and our HE-friendly model with poly. activations. Arch. | Dataset | Original | HE-friendly
---|---|---|---
RN50 | Places365 | 55.00 | 54.60
RN50 | ImageNet | 80.86 | 76.20
RN101 | 81.88 | 77.00
CNXT | 82.10 | 79.09

Table 3: The effect of eliminating SCs on latency and $\\#$bootstraps for HE-friendly ResNet-50 with fixed degree poly-activations. Deg. | #Bootstraps | Total
---|---|---
| w/ skip | w/o skip | ratio | speedup
2 | $3{,}328$ | $896$ | 3.71 | 2.53
8 | $5{,}136$ | $3{,}968$ | 1.29 | 1.37
16 | $8{,}480$ | $6{,}976$ | 1.21 | 1.23
18 | $8{,}480$ | $6{,}976$ | 1.21 | 1.21

Table 4: Performance on large images ($224\times 224\times 3$) for ResNet (RN) models with degree $18$ polynomial activations. BTS - Bootstraps Arch. | CPU | GPU |  $\\#$BTS | GPU Mem
---|---|---|---|---
| (Min) | (Min) |  | (GB)
RN$18$ | 29.48 | 7.43 | $1{,}184$ | 127
RN$50$ | 152.0 | 31.03 | $8{,}480$ | 173.37
RN$101$ | 295.64 | 57.31 | $13{,}424$ | 142.1
RN$152$ | 390.65 | 75.81 | $19{,}424$ | 109.7

#### A Comparison with the SOTA.

Lee et al. [40] were the first to report promising latency results when
considering secure evaluation over ResNet-20/110. For example, it takes only
37 minutes to run ResNet-20 on a single CPU thread. However, this
implementation is tailored to datasets such as CIFAR-10/100 with small images
of size $32\times 32$. Our approach relies on a different objective function,
by training low-degree large polynomial CNNs, which allows us to perform
secure prediction over large images. By using the HElayers SDK we can support
larger images that do not fit within a single ciphertext and provide a more
generic solution.

##  5 The Potential of HE-friendly Foundation Models for Transfer Learning

Our method enables the training of large-scale polynomial CNNs on unencrypted
data, which can then be leveraged for new two capabilities in secure transfer
learning: (i) Zero-Shot Learning (ZSL) as an alternative for training over
encrypted data: direct training of polynomial models under HE poses two main
challenges: Firstly, certain training techniques such as batch normalization,
gradient clipping, and CE loss, which are non-polynomial, are not natively
supported under HE. Secondly, the solution’s latency increases linearly with
the number of training iterations. Hence, inspired by recent advancements in
foundation models [8], we propose training an HE-friendly foundation model on
large-scale unencrypted data. This model can be applied to unseen encrypted
data for downstream tasks without additional training, which allows for
avoiding the limitations of polynomial training. (ii) Polynomial pre-trained
models for transfer learning: Previous studies have utilized frozen pre-
trained non-polynomial models as feature extractors, followed by secure
training of logistic regression on top of these representations [41]. This
technique has two major drawbacks: First, the non-polynomial pre-trained model
can not be encrypted via HE and can not be applied over encrypted data at
inference, as it is not polynomial. Our method from Sect. 3 opens the door to
solve this problem by employing polynomial (HE-friendly) pre-trained models.

Second, when considering fine-tuning over encrypted data, instead of utilizing
pre-trained models as freeze feature extractors, our technique allows E2E
secure fine-tuning. This approach allows optimizing the weights of the pre-
trained polynomial model.

#### Experimental Results - Polynomial CLIP.

We focus on a specific model that uses contrastive learning [15, 54, 29] –
CLIP [58]. Fig. 6 illustrates the training and inference flows of using an HE-
friendly CLIP model. A Service Provider (SP) starts from a pre-trained CLIP
model, modifies its visual encoder to become polynomial, and trains the
network. To use the trained model, the service provider shares the text
encoder with the clients and uses the visual encoder locally. We consider our
polynomial visual encoder as the first polynomial foundation model. Despite
its relatively small size (23M parameters), it is one of the largest
polynomials trained, and it was established on 400M (image, text) pairs, and
adapted to become polynomial encoder through the ImageNet-1K dataset.

We chose RN50-CLIP due to its image encoder, which is based on a variation of
ResNet-50 that we have managed to transform into an HE-friendly model. As in
previous studies in HE, which incorporated the softmax computation with the
client side, we also calculated the output attention-pool layer and cosine
similarity on the client side.

Due to the lack of the massive training data used by CLIP, we adapted the
original model into an HE-friendly model by fine-tuning the model through
ImageNet, with the prompts provided by the authors of CLIP. We then evaluated
the model on four datasets, that were used by [58]: CIFAR-10, CIFAR-100,
OxfordPet and STL10. The results are shown in Tab. 5, where we see that even
though the HE-friendly adaptation process has been managed by a low-resource
training set, its prediction capabilities on unseen data remain comparable in
various tasks. Moreover, some degradation is expected as the authors of CLIP
have noted that using pre-trained models trained on ImageNet achieve lower
transfer scores compared to CLIP-based models (see [58], Fig. 12). This is a
first step towards an HE zero-shot transfer and even few-shot learning on
encrypted images. Furthermore, similar to CLIP, linear-probing on top of our
polynomial model leads to improved accuracy, as observed in the second part of
Tab. 5. In contrast to previous adaptations of pre-trained models in HE, our
approach enables complete encryption of the entire model, as mentioned in the
preceding paragraph.

Table 5: ZSL and linear probe performance of HE-friendly RN50-CLIP fine-tuned on ImageNet and evaluated on various datasets. CLIP | CIFAR | CIFAR | STL10 | Pets
---|---|---|---|---
Type | 10 | 100 | [17] | [56]
Zero-Shot Classification
RN50 | 75.6 | 41.6 | 94.3 | 85.4
Poly | 73.3 | 38.4 | 90.7 | 73.9
Linear Probing
RN50 | 88.7 | 70.3 | 96.6 | 88.2
Poly | 89.28 | 67.71 | 96.96 | 90.62
Figure 6: HE-friendly CLIP training + secure ZSL.

##  6 Conclusions

The question of whether running real-size HE-based polynomial CNNs is possible
and practical has been studied by many researchers over the last decade.
However, most studies used some sort of relaxation in the form of client-aided
or toy networks and toy datasets to achieve this goal. We answer the above
question affirmatively, working on real-size datasets with standard-size
images of $224\times 224$ and modern CNNs such as ResNet and ConvNeXt. This
achievement unlocked thanks to our method to control and minimize the input
ranges to the non-polynomial activations. We demonstrate that evaluating them
under HE is practical. Specifically, we run ResNet-18/50/101/152 secure
prediction in 7, 31, 57, and 75 minutes, respectively, on a GPU with 128-bit
security. In addition, we discuss two insights that can further improve secure
predictions performance, namely, special handling of SCs and working with
different backbones. For example, we explain the benefits of using ConvNeXt in
the context of HE. Finally, our research opens the door for alternatives to
expensive training under HE. This can be achieved through the introduction of
ZSL-based methods, or by leveraging new transfer learning capabilities.

#### Limitations.

Our work focuses on training modern polynomial CNNs for HE, but we have not
evaluated our method on transformers yet. Transformers face barriers with the
Softmax (attention) operation and layer normalization, which are not easily
approximated. We plan to address these in future research.

## References

  * [1] Aharoni, E., Adir, A., Baruch, M., Drucker, N., Ezov, G., Farkash, A., Greenberg, L., Masalha, R., Moshkowich, G., Murik, D., Shaul, H., Soceanu, O.: HeLayers: A Tile Tensors Framework for Large Neural Networks on Encrypted Data. CoRR abs/2011.0 (2020), https://arxiv.org/abs/2011.01805
  * [2] Akavia, A., Vald, M.: On the privacy of protocols based on cpa-secure homomorphic encryption. IACR Cryptol. ePrint Arch. 2021, 803 (2021), https://eprint.iacr.org/2021/803
  * [3] Albrecht, M., Chase, M., Chen, H., Ding, J., Goldwasser, S., Gorbunov, S., Halevi, S., Hoffstein, J., Laine, K., Lauter, K., Lokam, S., Micciancio, D., Moody, D., Morrison, T., Sahai, A., Vaikuntanathan, V.: Homomorphic encryption security standard. Tech. rep., HomomorphicEncryption.org, Toronto, Canada (November 2018), https://HomomorphicEncryption.org
  * [4] Anonymous: AutoFHE: Automated Adaption of CNNs for Efficient Evaluation over FHE (2022), https://openreview.net/forum?id=Hq16Jk2bVlp
  * [5] Baruch, M., Drucker, N., Greenberg, L., Moshkowich, G.: A Methodology for Training Homomorphic Encryption Friendly Neural Networks. In: Applied Cryptography and Network Security Workshops. pp. 536–553. Springer International Publishing, Cham (2022). doi:10.1007/978-3-031-16815-4_29
  * [6] Boemer, F., Cammarota, R., Demmler, D., Schneider, T., Yalame, H.: Mp2ml: A mixed-protocol machine learning framework for private inference. In: Proceedings of the 2020 Workshop on Privacy-Preserving Machine Learning in Practice. p. 43–45. PPMLP’20, Association for Computing Machinery, New York, NY, USA (2020). doi:10.1145/3411501.3419425
  * [7] Boemer, F., Costache, A., Cammarota, R., Wierzynski, C.: NGraph-HE2: A High-Throughput Framework for Neural Network Inference on Encrypted Data. In: Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography. pp. 45–56. WAHC’19, Association for Computing Machinery, New York, NY, USA (2019). doi:10.1145/3338469.3358944
  * [8] Bommasani, R., Hudson, D.A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M.S., Bohg, J., Bosselut, A., Brunskill, E., et al.: On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258 (2021), https://arxiv.org/abs/2108.07258
  * [9] Brakerski, Z.: Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In: Safavi-Naini, R., Canetti, R. (eds.) Advances in Cryptology – CRYPTO 2012. vol. 7417 LNCS, pp. 868–886. Springer Berlin Heidelberg, Berlin, Heidelberg (2012). doi:10.1007/978-3-642-32009-5_50
  * [10] Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Transactions on Computation Theory 6(3) (jul 2014). doi:10.1145/2633600
  * [11] Cabrero-Holgueras, J., Pastrana, S.: Sok: Privacy-preserving computation techniques for deep learning. Proceedings on Privacy Enhancing Technologies 2021(4), 139–162 (2021), https://www.petsymposium.org/2021/files/papers/issue4/popets-2021-0064.pdf
  * [12] Cai, Y., Zhang, Q., Ning, R., Xin, C., Wu, H.: Hunter: HE-Friendly Structured Pruning for Efficient Privacy-Preserving Deep Learning. In: Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security. pp. 931–945. ASIA CCS ’22, Association for Computing Machinery, New York, NY, USA (2022). doi:10.1145/3488932.3517401
  * [13] Centers for Medicare & Medicaid Services: The Health Insurance Portability and Accountability Act of 1996 (HIPAA) (1996), https://www.hhs.gov/hipaa/
  * [14] Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 409–437. Springer (2017). doi:10.1007/978-3-319-70694-8_15
  * [15] Chopra, S., Hadsell, R., LeCun, Y.: Learning a similarity metric discriminatively, with application to face verification. In: 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05). vol. 1, pp. 539–546. IEEE (2005). doi:10.1109/CVPR.2005.202
  * [16] Chrysos, G.G., Moschoglou, S., Bouritsas, G., Panagakis, Y., Deng, J., Zafeiriou, S.: P-nets: Deep polynomial neural networks. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 7325–7335 (2020)
  * [17] Coates, A., Ng, A., Lee, H.: An analysis of single-layer networks in unsupervised feature learning. In: Gordon, G., Dunson, D., Dudík, M. (eds.) Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 15, pp. 215–223. PMLR, Fort Lauderdale, FL, USA (11–13 Apr 2011), https://proceedings.mlr.press/v15/coates11a.html
  * [18] Dathathri, R., Saarikivi, O., Chen, H., Laine, K., Lauter, K., Maleki, S., Musuvathi, M., Mytkowicz, T.: Chet: An optimizing compiler for fully-homomorphic neural-network inferencing. In: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. p. 142–156. PLDI 2019, New York, NY, USA (2019). doi:10.1145/3314221.3314628
  * [19] Deng, J., Dong, W., Socher, R., Li, L.J., Li, K., Fei-Fei, L.: Imagenet: A large-scale hierarchical image database. In: 2009 IEEE conference on computer vision and pattern recognition. pp. 248–255. Ieee (2009)
  * [20] Egidi, N., Fatone, L., Misici, L.: A New Remez-Type Algorithm for Best Polynomial Approximation. In: Sergeyev, Y.D., Kvasov, D.E. (eds.) Numerical Computations: Theory and Algorithms. pp. 56–69. Springer International Publishing, Cham (2020). doi:10.1007/978-3-030-39081-5_7
  * [21] EU General Data Protection Regulation: Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC (General Data Protection Regulation). Official Journal of the European Union 119 (2016), http://data.europa.eu/eli/reg/2016/679/oj
  * [22] Fan, J., Vercauteren, F.: Somewhat Practical Fully Homomorphic Encryption. Proceedings of the 15th international conference on Practice and Theory in Public Key Cryptography pp. 1–16 (2012), https://eprint.iacr.org/2012/144
  * [23] Folkerts, L., Gouert, C., Tsoutsos, N.G.: REDsec : Running Encrypted DNNs in Seconds. Tech. Rep. Report 2021/1100 (2021), https://eprint.iacr.org/2021/1100
  * [24] Garimella, K., Jha, N.K., Reagen, B.: Sisyphus: A cautionary tale of using low-degree polynomial activations in privacy-preserving deep learning. arXiv preprint arXiv:2107.12342 (2021)
  * [25] Ghodsi, Z., Veldanda, A.K., Reagen, B., Garg, S.: Cryptonas: Private inference on a relu budget. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems. vol. 33, pp. 16961–16971. Curran Associates, Inc. (2020), https://proceedings.neurips.cc/paper/2020/file/c519d47c329c79537fbb2b6f1c551ff0-Paper.pdf
  * [26] Gilad Bachrach, R., Dowlin, N., Laine, K., Lauter, K., Naehrig, M., Wernsing, J.: Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In: International Conference on Machine Learning. pp. 201–210 (2016), http://proceedings.mlr.press/v48/gilad-bachrach16.pdf
  * [27] Gottemukkula, V.: Polynomial activation functions (2020)
  * [28] Goyal, M., Goyal, R., Lall, B.: Improved polynomial neural networks with normalised activations. In: 2020 International Joint Conference on Neural Networks (IJCNN). pp. 1–8. IEEE (2020)
  * [29] Hadsell, R., Chopra, S., LeCun, Y.: Dimensionality reduction by learning an invariant mapping. In: 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06). vol. 2, pp. 1735–1742. IEEE (2006). doi:10.1109/CVPR.2006.100
  * [30] Halevi, S.: Homomorphic Encryption. In: Lindell, Y. (ed.) Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pp. 219–276. Springer International Publishing, Cham (2017). doi:10.1007/978-3-319-57048-8_5
  * [31] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770–778 (2016)
  * [32] Hendrycks, D., Gimpel, K.: Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08415 (2016)
  * [33] Hesamifard, E., Takabi, H., Ghasemi, M.: Cryptodl: Deep neural networks over encrypted data (2017). doi:10.48550/ARXIV.1711.05189, https://arxiv.org/abs/1711.05189
  * [34] Huang, G., Liu, Z., Van Der Maaten, L., Weinberger, K.Q.: Densely connected convolutional networks. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 4700–4708 (2017), https://openaccess.thecvf.com/content_cvpr_2017/html/Huang_Densely_Connected_Convolutional_CVPR_2017_paper.html
  * [35] Jha, N.K., Ghodsi, Z., Garg, S., Reagen, B.: Deepreduce: Relu reduction for fast private inference. In: Meila, M., Zhang, T. (eds.) Proceedings of the 38th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 139, pp. 4839–4849. PMLR (18–24 Jul 2021), https://proceedings.mlr.press/v139/jha21a.html
  * [36] Jiang, X., Kim, M., Lauter, K., Song, Y.: Secure outsourced matrix computation and application to neural networks. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. p. 1209–1222. CCS ’18, New York, NY, USA (2018). doi:10.1145/3243734.3243837
  * [37] Juvekar, C., Vaikuntanathan, V., Chandrakasan, A.: GAZELLE: A low latency framework for secure neural network inference. In: 27th USENIX Security Symposium (USENIX Security 18). pp. 1651–1669. USENIX Association, Baltimore, MD (Aug 2018), https://www.usenix.org/conference/usenixsecurity18/presentation/juvekar
  * [38] Kim, D., Park, J., Kim, J., Kim, S., Ahn, J.H.: HyPHEN: A hybrid packing method and optimizations for homomorphic encryption-based neural networks (2023)
  * [39] Krizhevsky, A., Hinton, G., et al.: Learning multiple layers of features from tiny images (2009), http://www.cs.utoronto.ca/~kriz/learning-features-2009-TR.pdf
  * [40] Lee, E., Lee, J.W., Lee, J., Kim, Y.S., Kim, Y., No, J.S., Choi, W.: Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions. In: Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., Sabato, S. (eds.) Proceedings of the 39th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 162, pp. 12403–12422. PMLR (17–23 Jul 2022), https://proceedings.mlr.press/v162/lee22e.html
  * [41] Lee, G., Kim, M., Park, J.H., Hwang, S.W., Cheon, J.H.: Privacy-Preserving Text Classification on BERT Embeddings with Homomorphic Encryption. NAACL 2022 - 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference pp. 3169–3175 (2022). doi:10.18653/v1/2022.naacl-main.231
  * [42] Lee, J.W., Kang, H., Lee, Y., Choi, W., Eom, J., Deryabin, M., Lee, E., Lee, J., Yoo, D., Kim, Y.S., No, J.S.: Privacy-preserving machine learning with fully homomorphic encryption for deep neural network. IEEE Access 10, 30039–30054 (2022). doi:10.1109/ACCESS.2022.3159694
  * [43] Lee, J.W., Kang, H., Lee, Y., Choi, W., Eom, J., Deryabin, M., Lee, E., Lee, J., Yoo, D., Kim, Y.S., No, J.S.: Privacy-preserving machine learning with fully homomorphic encryption for deep neural network. IEEE Access 10, 30039–30054 (2022). doi:10.1109/ACCESS.2022.3159694
  * [44] Lee, J., Lee, E., Lee, J.W., Kim, Y., Kim, Y.S., No, J.S.: Precise approximation of convolutional neural networks for homomorphically encrypted data. arXiv preprint arXiv:2105.10879 (2021), https://arxiv.org/abs/2105.10879
  * [45] Lehmkuhl, R., Mishra, P., Srinivasan, A., Popa, R.A.: Muse: Secure inference resilient to malicious clients. In: 30th USENIX Security Symposium (USENIX Security 21). pp. 2201–2218. USENIX Association (Aug 2021), https://www.usenix.org/conference/usenixsecurity21/presentation/lehmkuhl
  * [46] Liu, J., Juuti, M., Lu, Y., Asokan, N.: Oblivious Neural Network Predictions via MiniONN Transformations. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. pp. 619–631. CCS ’17, Association for Computing Machinery, New York, NY, USA (2017). doi:10.1145/3133956.3134056
  * [47] Liu, Z., Mao, H., Wu, C.Y., Feichtenhofer, C., Darrell, T., Xie, S.: A convnet for the 2020s. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 11976–11986 (2022)
  * [48] Lloret-Talavera, G., Jorda, M., Servat, H., Boemer, F., Chauhan, C., Tomishima, S., Shah, N.N., Pea, A.J.: Enabling homomorphically encrypted inference for large dnn models. IEEE Transactions on Computers 71(5), 1145–1155 (2022). doi:10.1109/TC.2021.3076123
  * [49] Lou, Q., Bian, S., Jiang, L.: Autoprivacy: Automated layer-wise parameter selection for secure neural network inference. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems. vol. 33, pp. 8638–8647. Curran Associates, Inc. (2020), https://proceedings.neurips.cc/paper/2020/file/6244b2ba957c48bc64582cf2bcec3d04-Paper.pdf
  * [50] Lou, Q., Jiang, L.: HEMET: A Homomorphic-Encryption-Friendly Privacy-Preserving Mobile Neural Network Architecture. In: Meila, M., Zhang, T. (eds.) Proceedings of the 38th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 139, pp. 7102–7110. PMLR (2021), https://proceedings.mlr.press/v139/lou21a.html
  * [51] Lyubashevsky, V., Peikert, C., Regev, O.: On Ideal Lattices and Learning with Errors over Rings. In: Gilbert, H. (ed.) Advances in Cryptology – EUROCRYPT 2010\. pp. 1–23. Springer Berlin Heidelberg, Berlin, Heidelberg (2010). doi:10.1007/978-3-642-13190-5_1
  * [52] Mishra, P., Lehmkuhl, R., Srinivasan, A., Zheng, W., Popa, R.A.: Delphi: A Cryptographic Inference Service for Neural Networks. In: 29th USENIX Security Symposium (USENIX Security 20). pp. 2505–2522. USENIX Association (aug 2020). doi:10.1145/3411501.3419418, https://www.usenix.org/conference/usenixsecurity20/presentation/mishra
  * [53] Mohassel, P., Zhang, Y.: Secureml: A system for scalable privacy-preserving machine learning. In: 2017 IEEE Symposium on Security and Privacy (SP). pp. 19–38 (2017). doi:10.1109/SP.2017.12
  * [54] Oord, A.v.d., Li, Y., Vinyals, O.: Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748 (2018), https://arxiv.org/abs/1807.03748
  * [55] Pachón, R., Trefethen, L.N.: Barycentric-remez algorithms for best polynomial approximation in the chebfun system. BIT Numerical Mathematics 49(4), 721–741 (2009). doi:https://doi.org/10.1007/s10543-009-0240-1
  * [56] Parkhi, O.M., Vedaldi, A., Zisserman, A., Jawahar, C.: Cats and dogs. In: 2012 IEEE conference on computer vision and pattern recognition. pp. 3498–3505. IEEE (2012). doi:10.1109/CVPR.2012.6248092
  * [57] Podschwadt, R., Takabi, D., Hu, P.: Sok: Privacy-preserving deep learning with homomorphic encryption (2021), https://arxiv.org/abs/2112.12855
  * [58] Radford, A., Kim, J.W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., Krueger, G., Sutskever, I.: Learning transferable visual models from natural language supervision. In: Meila, M., Zhang, T. (eds.) Proceedings of the 38th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 139, pp. 8748–8763. PMLR (18–24 Jul 2021), https://proceedings.mlr.press/v139/radford21a.html
  * [59] Rathee, D., Rathee, M., Kumar, N., Chandran, N., Gupta, D., Rastogi, A., Sharma, R.: CrypTFlow2: Practical 2-Party Secure Inference. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 325–342. Association for Computing Machinery, New York, NY, USA (2020), https://doi.org/10.1145/3372297.3417274
  * [60] Remez, E.Y.: Sur la détermination des polynômes d’approximation de degré donnée. Comm. Soc. Math. Kharkov 10(196), 41–63 (1934)
  * [61] Riazi, M.S., Samragh, M., Chen, H., Laine, K., Lauter, K., Koushanfar, F.: XONN: XNOR-based oblivious deep neural network inference. In: 28th USENIX Security Symposium (USENIX Security 19). pp. 1501–1518. USENIX Association, Santa Clara, CA (Aug 2019), https://www.usenix.org/conference/usenixsecurity19/presentation/riazi
  * [62] Riazi, M.S., Weinert, C., Tkachenko, O., Songhori, E.M., Schneider, T., Koushanfar, F.: Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications. In: Proceedings of the 2018 on Asia Conference on Computer and Communications Security. pp. 707–721. ASIACCS ’18, Association for Computing Machinery, New York, NY, USA (2018). doi:10.1145/3196494.3196522
  * [63] Rouhani, B.D., Riazi, M.S., Koushanfar, F.: Deepsecure: Scalable Provably-Secure Deep Learning. In: Proceedings of the 55th Annual Design Automation Conference. DAC ’18, Association for Computing Machinery, New York, NY, USA (2018). doi:10.1145/3195970.3196023
  * [64] Ryffel, T., Tholoniat, P., Pointcheval, D., Bach, F.: AriaNN: Low-Interaction Privacy-Preserving Deep Learning via Function Secret Sharing. Proceedings on Privacy Enhancing Technologies 1, 291–316 (2022)
  * [65] Takabi, D., Podschwadt, R., Druce, J., Wu, C., Procopio, K.: Privacy preserving neural network inference on encrypted data with gpus (2019), https://10.48550/ARXIV.1911.11377
  * [66] Tan, S., Knott, B., Tian, Y., Wu, D.J.: CryptGPU: Fast Privacy-Preserving Machine Learning on the GPU. In: 2021 IEEE Symposium on Security and Privacy (SP). vol. 2021-May, pp. 1021–1038. IEEE (2021). doi:10.1109/SP40001.2021.00098
  * [67] Targ, S., Almeida, D., Lyman, K.: Resnet in resnet: Generalizing residual architectures. arXiv preprint arXiv:1603.08029 (2016), https://arxiv.org/abs/1603.08029
  * [68] Wagh, S., Tople, S., Benhamouda, F., Kushilevitz, E., Mittal, P., Rabin, T.: Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning. Proceedings on Privacy Enhancing Technologies 2021(1), 188–208 (2021). doi:10.2478/popets-2021-0011
  * [69] Woo, S., Debnath, S., Hu, R., Chen, X., Liu, Z., Kweon, I.S., Xie, S.: Convnext v2: Co-designing and scaling convnets with masked autoencoders. arXiv preprint arXiv:2301.00808 (2023), https://arxiv.org/abs/2301.00808
  * [70] Xie, S., Girshick, R., Dollár, P., Tu, Z., He, K.: Aggregated residual transformations for deep neural networks. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 1492–1500 (2017)
  * [71] Zagoruyko, S., Komodakis, N.: Wide residual networks. arXiv preprint arXiv:1605.07146 (2016), https://arxiv.org/abs/1605.07146
  * [72] Zhang, Q., Xin, C., Wu, H.: Gala: Greedy computation for linear algebra in privacy-preserved neural networks. NDSS (2021), https://www.ndss-symposium.org/wp-content/uploads/ndss2021_5C-3_24351_paper.pdf
  * [73] Zhou, B., Lapedriza, A., Khosla, A., Oliva, A., Torralba, A.: Places: A 10 million image database for scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence (2017)
  * [74] Zhou, J., Qian, H., Lu, X., Duan, Z., Huang, H., Shao, Z.: Polynomial activation neural networks: Modeling, stability analysis and coverage bp-training. Neurocomputing 359, 227–240 (2019)

##  Appendix A Homomorphic Encryption

We start by describing the high-level background and basic concepts of HE
schemes. HE schemes allow us to perform operations on encrypted data [30].
Modern HE instantiations such as BGV [10], B/FV [22, 9], and CKKS [14] rely on
the complexity of the Ring-LWE problem [51] for security and support Single
Instruction Multiple Data (SIMD) operations. The HE system has an encryption
operation $\operatorname{Enc}:\mathcal{R}_{1}\rightarrow\mathcal{R}_{2}$ that
encrypts input plaintext from the ring $\mathcal{R}_{1}(+,*)$ into ciphertexts
in the ring $\mathcal{R}_{2}(\oplus,\odot)$ and an associated decryption
operation $\operatorname{Dec}:\mathcal{R}_{2}\rightarrow\mathcal{R}_{1}$. An
HE scheme is correct if for every valid input $x,y\in\mathcal{R}_{1}$

$\displaystyle\operatorname{Dec}(\operatorname{Enc}(x))=x$ (1)
$\displaystyle\operatorname{Dec}(\operatorname{Enc}(x)\oplus\operatorname{Enc}(y))=x+y$
(2)
$\displaystyle\operatorname{Dec}(\operatorname{Enc}(x)\odot\operatorname{Enc}(y))=x*y$
(3)

and is approximately correct (as in CKKS) if for some small $\epsilon>0$ that
is determined by the key, it follows that
$|x-\operatorname{Dec}(\operatorname{Enc}(x))|\leq\epsilon$. Eqs. 2, and 3 are
modified in the same way. For this paper, we used CKKS for the experiments.

##  Appendix B The HE-based PPML landscape

The HE-based PPML landscape includes interactive/client-aided and non-client-
aided solutions. In addition, some solutions involve Network Architecture
Search (NAS) in their design. We briefly review the two terms below.

#### Client-Aided Solutions.

Some PPML solutions rely solely on HE such as [1, 50]. They are known as non-
interactive or non-client-aided protocols, while others are known as
interactive or client-aided protocols. In the client-aided approach, the
server asks the client for assistance with computation, e.g., computing a non-
polynomial function such as $\operatorname{ReLU}$. Here, the server asks the
client to decrypt the intermediate ciphertext data, perform the
$\operatorname{ReLU}$ computation, and re-encrypt the data using HE. This
approach is implemented, for example, in GAZELLE [37] and nGraph-HE [7]. To
avoid leakage of intermediate results to the client, the server utilizes a
dedicated Multi-Party Computation (MPC) protocol.

The main drawback of client-aided solutions is that the client must stay
online during the computation. Moreover, this approach may involve some
security risks as detailed in [2]. [45] showed that for some cases it can even
facilitate the performance of model-extraction attacks. To avoid such attacks,
we focus on non-client-aided solutions, where inference computation is
performed entirely under encryption, without interaction.

Table 6: A comparison of SOTA PPML solutions. The columns are:
Architecture (Arch.): AlexNet (A); CryptoNets (C); ConvNeXt (CN); DesnseNet-N
(DN); 2 hidden layers (H); InceptionNet (I); Industrial (Ind); Lenet-5 (L);
MiniONN1 (M); MobileNetV2 (M2); ResNet-N (RN); SqueezeNet (S); VGG16 (V).
Image size (IS): MNIST ($28\times 28\times 1$);  CIFAR-10 ($32\times 32\times
3$);  CIFAR-100 ($32\times 32\times 3$);  Tiny-ImageNet ($64\times 64\times
3$);  ImageNet/CXR2 ($224\times 224\times 3$).
Non-interactive (NI): Non-constant round protocol,  Constant round protocol,
non-interactive protocol.
Activation (Act): $\operatorname{ReLU}$ (R); $\operatorname{ReLU}$ 6 (R6),
Square (S); Quadratic approximation (Q); quadratic Trainable coefficients (T);
Medium-degree approximation (M); High-degree approximation (H); SIgn
activation (SI).
Limitation (Lim.): Binarized network (B), Leaks information to the client (L),
Not implemented under HE (N), more than two-party (P+), Pruned (smaller)
network (Pr).
1 A network from [46] with 7 convolutional layers, 7 $\operatorname{ReLU}$
layers, 2 mean-Pooling layers, and 1 fully connected layer.
2 Chest X-Ray dataset large images of size $224\times 224\times 3$.
3 with approximated Softmax.
4 A reduced SqueezeNet variant.
5 The authors benchmarked ImageNet but did not report accuracy results.  Solution | NI | Arch. | IS | Sec. bits | Use NAS | Act. | Lim.
---|---|---|---|---|---|---|---
SecureML [53] |  | H |  | N/A |  | R/S | P+
MP2ML [6] |  | C |  | 128 |  | R |
MiniONN [46] |  | M |  | 128 |  | S |
GAZELLE [37] |  | M | /  | 128 |  | R |
Chameleon [62] |  | M | /  | 128 |  | R | P+
Falcon [68] |  | M | /  | N/A |  | R3 |
Delphi [52] |  | M/R32 | /  | 128 |  | R/R6/Q |
Cryptflow2 [59] |  | S/R50/D121 |  | 128 |  | R |
NGraph-HE [7] |  | C/MN |  | 128 |  | R/T |
CryptGPU [66] |  | V/R152 | \-  | N/A |  | R | P+
Gala [72] |  | A/V/R152 | /  | 128 |  | R |
AriaNN [64] |  | A/V/R18 | \-  | 128 |  | R |
Hunter [12] |  | A/V/R32 | \-  | N/A |  | R | Pr
[48] |  | MN/R50 |  | 128 |  | R6 | L
Deepsecure [63] |  |  $\sim{}$C |  | 128 |  | R |
XONN [61] |  | V | /  | N/A |  | R | B
CryptoNets [26] |  | C |  | N/A |  | S |
[36] |  |  $\sim{}$C |  | 80 |  | S |
RedSEC [23] |  | A | \-  | 128 |  | SI | B
CHET [18] |  | L/Ind/S4 | /  | 128 |  | Q |
HEMET [50] |  | A/S4/I | /  | 128 |  | Q |
HElayers [1] |  | A/S |  | 128 |  | T |
[42] |  | R20 |  | 111.6 |  | H |
AutoFHE [4] |  | R56 |  | 128 |  | H | Pr
[44] |  | V19/R152 | \-  | N/A |  | H | N
Sisyphus [24] |  | R20/R44 | \-  | N/A |  | Q | N
[40] |  | R20/R110 | \-  | 128 |  | H |
HyPHEN [38] |  | R20/R44 | \- 5 | 128 |  | H |
Ours |  | A/V/MN/R32 |  | 128 |  | M |

####  NAS.

A recent line of work on privacy-preserving NAS [35, 52, 25, 49] aims to find
more efficient PPML architectures by reducing the number of non-polynomial
primitives. Our training method is orthogonal to this research direction,
because a NAS-generated network contains non-polynomial elements, which we can
address with our methods. In fact, our method can benefit from the reduced
number of non-polynomial layers. Another reason for seeing NAS as an
orthogonal approach is that it assumes the existence of a pre-trained
(foundation) model, which spares us a costly training operation required for
novel NAS-based networks.

Tab. 6 presents a rough comparison of SOTA HE-based PPML inference solutions.
Other surveys can be found in [11, 57]. The first group contains
interactive/client-aided solutions that are based on a combination of HE and
MPC techniques such as Garbled Circuitss (GCs), Oblivious Transfers (OTs) or
Shared Secret (SS). The advantage of these solutions is that they can use non-
polynomial operations such as $\operatorname{ReLU}$ and enable the running of
large models such as ResNet-152, while the model performance stays stable. On
the other hand, they often involve high bandwidth, which clients try to avoid.
The second group involves a constant number of iterations that is independent
of the network architecture, thereby reducing the bandwidth costs. The largest
network reported for these solutions is VGG16 over a medium size dataset -
CIFAR-10.

The third and fourth groups include non-interactive, non-client-aided
solutions that are based only on HE, which is also the focus of this paper.
The third group includes solutions without an HE operation known as
bootstrapping. Here, the largest evaluated networks are AlexNet and SqueezeNet
over data with large images of $224\times 224\times 3$. To evaluate larger
networks, a support for bootstrapping is required. The solutions of the last
group are the most relevant for our study. These studies consider HE solutions
with bootstrapping, allowing them to evaluate large networks such as ResNet-20
- ResNet-152. However, the reported results either did not have 128-bits
security [42, 44] as recommended by the standard [3], or did not implement
their solution using HE [44]. In the following paragraphs, we show that there
is a big gap between a cleartext model and an encrytpted model. Finally, we
compare our work to the work of [40], who reported good performance and
latency of a ResNet-50 solution over CIFAR-10. In contrast, we show an
unprecedented scaled version of ResNet-50 over the large images of ImageNet
along with some other applications of our solution in the encrypted domain. We
provide an additional comparison to [40] in Sect. 4.

The above solutions focus mainly on improving latency and bandwidth while
maintaining a decent ML performance. In contrast, other works, such as this
paper and [5] focus mainly on generating HE-friendly models.

##  Appendix C HE-based experiments setup

#### Performance of Predictions over Encrypted Data.

For the following experiments, the models running time is reported for both
the GPU and the CPU hardware, which we describe in App. C. The GPU runs were
based on an average of $500$ samples per dataset, while the CPU runs were
based on only $10$ samples due to the longer processing time. In addition, we
evaluate the accuracy of the model when applied to encrypted and unencrypted
data, and reach an MSE in the range $[1e^{-12},1e^{-10}]$. We evaluated our
models under HE using the HElayers SDK. Tab. 4 summarizes the latency and
memory results of ResNet-18, 50, 101 and 152 with 128-bit security.

For the experiments, we evaluated two different setups: one using a CPU-based
system with 32 CPU cores, 32 threads, and 200 GB of memory that were allocated
to the tested process. In this setup, either AMD EPYC 7763 64-Core processor
or an Intel Xeon E5-2667v2 processor were used. The second setup included both
CPU and GPU resources, where the CPU specification was similar to the first
setup, but an additional single NVIDIA A100-SXM4-80GB GPU with 80GB of memory
was used in some parts of the computation. In these environments, we run
HElayers version $1.52$ and set the underlying HE library to HEaaN. The
concrete HE parameters were set as follows: We used ciphertexts with $2^{15}$
coefficients, a multiplication depth of $12$, fractional part precision of
$42$, and integer part precision of $18$. This context allows us to use up to
$9$ multiplications before bootstrapping is required. The security parameters
were set to provide a solution with $128$-bits security.

When we report results for running the models on GPU, we actually mean that we
are utilizing a combination of both CPU and GPU. Specifically, the
bootstrapping and polynomial activation calculations are performed on the GPU,
while the remaining layers of the models are run on the CPU. This is because
the polynomial HE-friendly models have high memory requirements that cannot be
met by running solely on GPU.

##  Appendix D Extra information

In this section, we provide some graphs that can shed more light on the
phenomena discussed in the paper. Fig. 7 provides a latency breakdown, in
percentage, of the layers that mostly contributed to the latency of evaluating
ResNet-50 over ImageNet under HE. Specifically, we see that the polynomial
activations even though we set their degree to be 18, which is considered
small, still consume 43% of the time. As mentioned above, one research
direction to reduce the degrees of the polynomials is to further reduce the
layers’ input ranges. When considering the potential improvement of reducing
SCs, we need to consider the costs of the bootstrapping operations together
with the costs of the function g(x), which the SC HE implementation uses.
Here, the overall cost is 26% + 11% = 37%.

Figure 7: A generic CNN under HE. Every block is a convolutional layer, where
the different colors and textures represent different tile tensor shapes [1],
i.e., different placement of data inside ciphertexts. The chained index
$\operatorname{CIdx}$ is indicated below every layer output. The figure
includes 3 SCs with different latency costs, see text for more details.

We use Fig. 7 illustrates the logic behind Alg. 2. It shows a generic CNN
implemented under HE. Here, every block is a convolutional layer, where the
different colors and textures represent different tile tensor shapes [1],
i.e., different placement of data inside ciphertexts. Below the output of
every layer, we indicate the chain index $\operatorname{CIdx}$ of the output
ciphertexts. The figure includes 3 SCs, where the cost of SC (a) is low since
the chain indices of the two operands match
$\operatorname{CIdx}(x)=\operatorname{CIdx}(f(x))$ and also the tile tensors
shapes match; (b) has a higher cost because the chain indices do not match,
and because $\operatorname{CIdx}(x)>\operatorname{CIdx}(f(x))$ a bootstrap
operation is required; Finally, the cost of (c) is also high because both the
tile tensor shapes and the chain index do not match. However, here,
$\operatorname{CIdx}(g(x))<\operatorname{CIdx}(f(x))$ so only a HE
$\operatorname{ReScale}$ is required and not a $\operatorname{Bootstrap}$
operation.

##  Appendix E Polynomial Approximation Per Range

As mentioned in the text, algorithms like Remez [60] can derive the optimal
minimax polynomial $p(x)$ of a fixed degree that has the least error distance
from a function $f(x)$ according to some distance metric $d$, i.e., the
solution to
$\operatorname*{arg\,min}\limits_{p}{\max\limits_{x\in[a,b]}{d(p(x),f(x))}}$.
Two parameters affect the accuracy of the approximation - the range $[a,b]$
and the polynomial degree. Higher degrees or smaller ranges result in a more
accurate approximation. However, a higher degree polynomial might harm the
efficiency of the evaluation as larger polynomials require more computations
and often increase the overall noise. Therefore, one of our objectives is to
reduce the input ranges, which in effect allows us to reduce the polynomial
degrees and achieve better efficiency.

######  Observation E.1.

Denote the maximal error of the minimax polynomial of degree $m$ over the
range $[a,b]$ by
$e_{a,b,m}=\min\limits_{p}{\max\limits_{x\in[a,b]}{d(p(x),f(x))}}.$ Then for
all $a_{1}<a_{2}<b_{2}<b_{1}$ it follows that $e_{a_{1},b_{1},m}\geq
e_{a_{2},b_{2},m}$.

###### Proof.

Let $P_{1}(x)$ and $P_{2}(x)$ be the unique minimax polynomials associated
with the ranges $[a_{1},b_{1}]$ and $[a_{2},b_{2}]$, respectively, and assume
that the observation is false, i.e., that
$e_{a_{1},b_{1},m}<e_{a_{2},b_{2},m}$, then $P_{1}$ is also the minimax
polynomial for the range $[a_{2},b_{2}]$, which is a contradiction to the fact
that $P_{2}$ is a minimax polynomial. ∎