# Orion: A Fully Homomorphic Encryption Compiler for Private Deep Neural
Network Inference

Austin Ebel∗, Karthik Garimella∗, Brandon Reagen
New York University
<EMAIL_ADDRESS>
###### Abstract

Fully Homomorphic Encryption (FHE) has the potential to substantially improve
privacy and security by enabling computation on encrypted data. This is
especially true with deep learning, as today many popular user services are
powered by neural networks. One of the major challenges facing wide-scale
deployment of FHE-secured neural inference is effectively mapping them to the
FHE domain. FHE poses many programming challenges including packing large
vectors, handling expensive rotations, and correctly implementing complex
strided convolutions. This makes programming FHE inferences prone to poor
performance and errors. In this paper we overcome these challenges with Orion,
an automated optimizing FHE compiler for neural inference. Orion automatically
maps PyTorch-specified networks to FHE, handling common layer types and
arbitrary tensor shapes and strides. Moreover, we develop novel optimizations
that balance dense FHE vector packing, efficient rotations, and minimize
operations to improve performance. We have implemented Orion, which will be
open sourced, and evaluated it on common benchmarks used by the FHE deep
learning community. We compare Orion to multiple state-of-the-art solutions
and report iso-accuracy speedups ranging from 2.7$\times$ to 20.5$\times$.

**footnotetext: Equal contribution.

##  I Introduction

The steady increase of outsourced cloud computing services has given rise to
concerns surrounding data privacy, which dictate how and when personal data is
collected, viewed, and used. Furthermore, privacy and security risks are
intensified by data-hungry cloud-based machine learning services that operate
on large volumes of user data. Traditional cryptographic methods protect data
during transmission and storage but must be decrypted in the cloud for
processing, thus exposing data to wrongful use or access. Privacy preserving
computation (PPC) overcomes this by safeguarding user data during computation,
ensuring that data remains encrypted throughout the process. Fully Homomorphic
Encryption (FHE) is a prominent PPC solution that provides secure cloud
computation, enabling functions to be computed on encrypted data without first
decrypting. In this manner, the client’s data, and any outputs obtained
processing their data, remain encrypted and can only be observed in the clear
when the client locally decrypts it using their secret key.

FHE has broad applications ranging from finance to health and other situations
involving sensitive data. Many of these services are now driven by deep
learning, specifically neural networks. Thus, prior work, and our work here,
has focused on optimization techniques to facilitate more efficient processing
of deep learning with FHE. Despite this, the wide-scale deployment of FHE-
enabled private deep learning is limited by extremely high computational costs
and programming challenges of translating plaintext programs to the
constraints of FHE. This has given rise to two major thrusts of research:
hardware accelerators to provide the raw computational performance needs [1,
2, 3, 4, 5, 6] and compilers to effectively translate programs [7, 8, 9, 10,
11], which is also essential for high performance. This paper focuses on
automatically and efficiently mapping neural networks to FHE.

⬇

1net = ResNet20()

2net.eval()

3pred_clear = net(img) # Forward pass (PyTorch).

4

5net.compile() # Generate HE representation.

6net.he() # Set to HE mode.

7pred_he = net(img) # HE-friendly inference.

Listing 1 PyTorch integration with $\mathsf{Orion}$.

Multiple compounding factors make effectively mapping neural networks to FHE
challenging. First, operands in FHE are very large vectors. These vectors
range from lengths of 1024 to 128K, with recent work favoring the larger
lengths [5, 3]. Scalar data are packed into these vectors but cannot be
individually indexed nor partial vectors processed; any function applied to a
vector is applied to all elements. Therefore, each function (i.e., addition
and multiplication) is computationally expensive and if vector elements (i.e.,
_slots_) are not utilized, performance degrades. This makes it imperative to
optimize data packing and layout into FHE vectors. Next, vector elements can
be realigned via rotations. However, these rotations are highly
computationally expensive as each entails a key-switch operation, which can
dominate runtime [12, 3]. Finally, each encrypted vector can only execute
finite computations before decryption fails. To prevent this, bootstrapping
can be used to reset computation support but comes at an extremely high
latency cost [13]. Therefore, careful attention must be placed on the amount
and type of operations performed on FHE vectors. Not only are each of the
above problems difficult to address individually, but they also have competing
objectives. For example, the most dense packing strategies have the highest
slot utilization but necessitate frequent bootstrapping operations. This makes
for a complex optimization landscape and motivates the need for a robust and
automated infrastructure.

To address these challenges we present $\mathsf{Orion}$, an automated and
optimizing compiler for translating plaintext neural networks to FHE. As a
compiler, $\mathsf{Orion}$ takes as input neural network descriptions written
in PyTorch [14] and generates FHE programs written in Lattigo [15]. This
process is shown in Listing 1. $\mathsf{Orion}$ supports major neural network
layers (e.g., fully-connected and convolution) and, for the first time,
handles strided convolutions automatically. $\mathsf{Orion}$ also includes a
set of novel optimizations to speedup neural inference under FHE. First, we
develop three distinct vector packing strategies tailored to needs of
individual neural network layers. Each strategy is tailored for the unique
tradeoff in slot utilization and computational complexity. Second, we consider
recent hoisting [13] optimizations to significantly speedup rotations. The
insight is that rotating the same vector is far faster than rotating distinct
ones; $\mathsf{Orion}$ leverages this by optimizing how data is packed and
rotations are scheduled. Third, we develop a technique to reduce the number of
levels needed to perform a computation by introducing structured sparsity into
ciphertexts. By saving levels, we can significantly reduce the number of
bootstrapping calls. Finally, we observe that there is a tradeoff between
hoisted input rotations and non-hoisted output rotations wherein a few output
rotations can save hundreds of hoisted ones. We explore and optimize this
tradeoff natively in $\mathsf{Orion}$.

We evaluate $\mathsf{Orion}$ using a set of neural networks and
microbenchmarks to highlight the intuitions behind the optimizations and
approaches. In many cases, we find that the densest packing strategies are not
always the most efficient. We compare $\mathsf{Orion}$ to two distinct state
of the art approaches and report significant speedup. $\mathsf{Orion}$, and
all benchmarking infrastructure, will be open-sourced.

We make the following contributions:

  * 1.

We develop $\mathsf{Orion}$: an automated optimizing compiler for FHE neural
network inference that directly integrates into PyTorch.

  * 2.

A collection of new FHE linear algebra techniques that handle arbitrary
matrix-vector products and data layout.

  * 3.

A suite of FHE linear layer microbenchmarks that target both commonly deployed
convolutional and linear layers as well as a set of more challenging and non-
standard layers. Benchmarking $\mathsf{Orion}$, we outperform the state-of-
the-art FFT-based and rotation-based algorithms by $2.7\times$ and
$20.5\times$ at iso-accuracy, respectively.

##  II A Primer on FHE and Deep Learning

In this section we provide a review of the core concepts of FHE and deep
learning needed to understand the contributions and insights of
$\mathsf{Orion}$. We begin by reviewing FHE and specifically the CKKS [16]
scheme, which is widely used for deep learning. Next, we briefly review deep
neural networks.

###  II-A Fully Homomorphic Encryption

Since the first FHE scheme was developed in 2009 [17] many algorithmic
optimizations have been proposed to steadily improve performance. A variety of
schemes now exist including BGV [18], BFV [19, 20], and CKKS [16]. At a high-
level many of the characteristics are the same. For example, they are all
based on the Ring Learning with Errors (RLWE) problem [21], support addition,
multiplication, and rotations and work over large vectors. Recently, CKKS has
emerged as the dominant scheme for deep learning in part due to its native
support of fixed-point arithmetic. We target CKKS with $\mathsf{Orion}$ and
detail it here.

####  II-A1 CKKS Notation

TABLE I: CKKS Parameters. Param. | Description
---|---
$\mathbf{m}$ | Message, a vector of real or complex numbers.
$[\mathbf{m}]$ | Plaintext polynomial encoding the message, $\mathbf{m}$.
$[\\![\mathbf{m}]\\!]$ | Ciphertext encrypting the plaintext polynomial, $[\mathbf{m}]$.
$N$ | Power-of-two polynomial ring degree.
$n$ | Length of the vector message, $n\leq N$ (or $\nicefrac{{N}}{{2}}$).
$L$ | Maximum multiplicative level of $[\\![\mathbf{m}]\\!]$.
$\ell$ | Current multiplicative level.
$Q$ | Initial polynomial modulus.
$q_{i}$ | Small moduli in RNS decomposition of $Q=\prod_{i=0}^{L}q_{i}$.
$P$ | Auxiliary modulus used in key-switching.
$\Delta$ | Scaling factor applied to $[\\![\mathbf{m}]\\!]$.
$L_{\text{boot}}$ | Number of levels consumed by bootstrapping.
$L_{\text{eff}}$ | Maximum achievable level after bootstrapping.

We list the relevant CKKS parameters in Table I. To perform FHE operations, a
vector message, $\mathbf{m}$, is converted into a fixed-point (integer)
representation in part by multiplying the message with a large scaling factor,
$\Delta$. This encoded plaintext message, which we denote as $[\mathbf{m}]$,
is an element of the polynomial ring $R_{Q}=\mathbb{Z}_{Q}[X]/(X^{N}+1)$. In
essence, this is another vector of length $N$, where each element is modulo
some large value, $Q$. As we will see, the choice of $N$ is largely
application-dependent and is tied directly to the security of the scheme. For
a polynomial with $N$ coefficients, the corresponding vector must be of length
$n\leq N$ for the specific class of problems we explore in future sections,
and $n\leq\nicefrac{{N}}{{2}}$ otherwise. Following prior work, we refer to
$n$ as the number of slots that the polynomial can encode. A core challenge in
designing efficient HE algorithms is finding a way to tightly pack data within
vector messages to take full advantage of the SIMD-like parallelism provided
by the slots. Poor mapping strategies can result in ciphertexts with unused
slots, which we refer to as slot underutilization throughout.

####  II-A2 Ciphertext Structure

Depending on a problem’s complexity, the value of $Q$ can range from hundreds
to thousands of bits. For efficiency, polynomials are decomposed into an
equivalent RNS (residue number system) representation consisting of many
smaller, machine-word size moduli, $q_{i}$, such that $q_{0}\times
q_{1}\times\ldots\times q_{L}=Q$. Here, $L$ is the maximum multiplicative
level of the polynomial, and several homomorphic operations consume levels to
ensure the scales of polynomials remain in check. Therefore, at any given
time, a polynomial can be at level $\ell$, such that $\hskip
1.00006pt0\leq\ell\leq L$, and we refer to $\ell$ as the remaining number of
levels in the polynomial.

A ciphertext, $[\\![\mathbf{m}]\\!]$, consists of a pair of polynomials
$([\mathbf{a}],[\mathbf{b}]$), where the underlying vector message is encoded
in one of the polynomials alongside the addition of a small amount of random
noise to ensure the security of the RLWE scheme. We sometimes refer to a
ciphertext as $[\\![\mathbf{m}]\\!]_{s}$ to explicitly indicate that
$[\\![\mathbf{m}]\\!]$ is encrypted under secret key, $s$. As with any FHE
scheme, operations performed on ciphertexts have an equivalent effect on the
underlying vector message.

####  II-A3 FHE Operations

We now briefly describe the available operations that can be performed in the
CKKS domain.

Addition CKKS supports point-wise addition between one plaintext and one
ciphertext or between two ciphertexts. When performing addition, each operand
must be at the same number of levels, $\ell$. Following convention from [3],
we refer to plaintext-ciphertext addition as $\mathsf{PAdd}$ and ciphertext-
ciphertext addition as $\mathsf{HAdd}$. Both $\mathsf{PAdd}$ and
$\mathsf{HAdd}$ output a ciphertext.

Algorithm 1
$\mathsf{PMult}([\\![\mathbf{x}]\\!],[\mathbf{y}])=[\\![\mathbf{z}]\\!]$

1:$[\mathbf{a}],[\mathbf{b}]:=[\\![\mathbf{x}]\\!]$ $\triangleright$ Scale:
$\Delta$, Level: $\ell$

2:$[\\![\mathbf{z}]\\!]:=[\mathbf{a\cdot y}],[\mathbf{b\cdot y}]$
$\triangleright$ Scale: $\Delta^{2}$, Level: $\ell$

3:$[\\![\mathbf{z}]\\!]:=\mathsf{Rescale}([\\![\mathbf{z}]\\!])$
$\triangleright$ Scale: $\Delta$, Level: $\ell-1$

4:return $[\\![\mathbf{z}]\\!]$

Multiplication Similar to addition, CKKS also supports point-wise
multiplication between one plaintext and one ciphertext or between two
ciphertexts. These operations are referred to as $\mathsf{PMult}$ and
$\mathsf{HMult}$, respectively. Since model weights need not be encrypted
server-side, many of the computations in private neural network inference are
$\mathsf{PMults}$ where the plaintext represents the weights of a particular
layer and the ciphertext represents the client’s input to that layer. Finally,
recall that messages are encoded with an associated scaling factor, $\Delta$.
Therefore when two polynomials are multiplied, the resulting scale increases
to $\Delta^{2}$, as is typical in fixed-point arithmetic. CKKS supports a
$\mathsf{Rescale}$ procedure that reduces this scale back to roughly $\Delta$
at the cost of consuming one level in the resulting ciphertext. This rescaling
operation is shown for $\mathsf{PMult}$ in Algorithm 1.

Algorithm 2
$\mathsf{HRot}([\\![\mathbf{x}]\\!],r,\mathsf{swk}_{r})=[\\![\mathbf{y}]\\!]$

1:$[\\![\mathbf{y}]\\!]_{s^{\prime}}:=\psi_{r}([\\![\mathbf{x}]\\!]_{s})$
$\triangleright$ Secret key: $s^{\prime}$

2:$[\\![\mathbf{y}]\\!]_{s}:=\mathsf{KeySwitch}([\\![\mathbf{y}]\\!]_{s^{\prime}},\mathsf{swk}_{r})$
$\triangleright$ Secret key: $s$

3:return $[\\![\mathbf{y}]\\!]$

Rotation CKKS also supports ciphertext rotations, denoted as $\mathsf{HRot}$,
in which a permutation to the polynomial coefficients, $\psi_{r}$ is performed
for a given rotation amount, $r$. This has the effect of cyclically shifting
elements in the underlying vector message by $r$ positions. Rotations
transform the ciphertext in such a way that it cannot be decrypted by the
original secret key, $s$. Therefore an expensive key-switching step is
required to convert the ciphertext back to being decryptable by $s$. This
involves performing numerous number theoretic transforms (NTTs, the finite
field equivalent of FFTs), and RNS basis extensions before multiplying with a
large switching key, $\mathsf{swk}$. $\mathsf{HRot}$ is shown in Algorithm 2.

Figure 1: Performance comparison of single and double-hoisted rotations
relative to non-hoisted rotations.

Hoisting: Recently, a performance optimization was developed to amortize
rotations to the same ciphertext. When the same ciphertext is rotated by
different amounts, one can hoist out these expensive operations and perform
them significantly fewer times. The act of (single) hoisting was originally
proposed by Halevi and Shoup [22] and further optimized by Bossuat et al. [13]
in a double-hoisting procedure. Figure 1 illustrates the performance
difference between non-hoisted, single-hoisted, and double-hoisted rotations
as the number of rotations on the same ciphertext is varied. We find double-
hoisting to be $10\times$ ($2\times$) faster than non-hoisted (single-hoisted)
rotations that are present in typical CNN layers. Unlike prior work,
$\mathsf{Orion}$ optimizes mapping strategies to take full advantage of the
performance benefits offered by hoisting, sometimes at the cost of slot
underutilization.

Bootstrapping Finally, for a scheme to be fully homomorphic, it must include a
way of increasing the number of remaining levels; the $\mathsf{Bootstrap}$
operation provides this functionality. Bootstrapping is a computationally
demanding procedure that increases levels but also consumes a fixed number
($L_{\text{boot}}$) of levels in the process. A ciphertext that began at level
$L$ can only reach an effective level, $L_{\text{eff}}=L-L_{\text{boot}}$
after bootstrapping. A typical $L_{\text{boot}}$ is $15$ levels [13].

###  II-B Deep Learning

$\mathsf{Orion}$ targets convolutional neural networks (CNNs), a class of
feed-forward neural networks that consist of a series of linear and non-linear
transformations applied to an input image. Below, we set up our notation and
describe each type of computation we support.

####  II-B1 Linear Layers

Each linear transformation is either a convolution, fully-connected matrix-
vector product, or an average pooling operation. We develop FHE linear algebra
kernels for performing matrix-vector products, and as we will show, express
convolutions as a matrix-vector product, thus supporting all aforementioned
linear operations in $\mathsf{Orion}$.

Convolution A convolutional layer consists of an input image of size
$h_{i}\times w_{i}\times c_{i}$ that is processed through a set of trainable
filters of size $f_{h}\times f_{w}\times c_{i}$. These filters perform
element-wise weighted-summations over localized regions between the image
pixels and the kernel values to produce a single output pixel. The convolution
layer is also defined by a stride ($s_{h},s_{w}$), which denotes the number of
pixels the kernel shifts over in each spatial dimension when performing the
weighted-sum. The convolution is further parameterized by a padding parameter
(denoted as $p$) that adds a set of $p$ zeros to each side of the input image
to increase the resolution of the output image. In order to produce multiple
output channels, there will be $c_{o}$ sets of the filters that are
independently applied to the input image to produce an output image of size
$h_{o}\times w_{o}\times c_{o}$. Finally, there is a separate bias term for
each of the $c_{o}$ output channels. $\mathsf{Orion}$ supports the multiple-
input multiple-output channel case shown in Figure 2.

Figure 2: $\mathsf{Orion}$ supports the multiple-input multiple output channel
(MIMO) convolution that is present in standard CNN networks such as ResNets.

Average Pooling Average Pooling Layers are a special case of convolutions with
a kernel size of $f_{h}\times f_{w}$ where every filter value is
$\nicefrac{{1}}{{(f_{h}\cdot f_{w})}}$. Usually, $s_{h},s_{w}>1$ in order to
decrease the image resolution by a factor of $s_{h}\times s_{w}$.

Fully-Connected Layers An input vector of size $n_{i}$ is transformed via a
trainable weight matrix of size $n_{o}\times n_{i}$ to produce an output
vector of size $n_{o}$. Additionally, we add a bias term of size $n_{o}$ to
the output of the matrix-vector product.

####  II-B2 Non-linear Layers

CKKS only supports addition and multiplication and therefore cannot support
common non-linear activation functions such as $\mathsf{ReLU}$. To this end,
$\mathsf{Orion}$ supports the use of polynomial activation functions [23, 24,
25].

##  III The Orion Compiler

In this section, we provide an overview of the $\mathsf{Orion}$ compiler,
review common FHE matrix-vector products, and introduce our proposed
optimizations.

###  III-A Orion

$\mathsf{Orion}$ is composed of three distinct phases: compilation,
verification, and integration. First, a user specifies their network
architecture in PyTorch, which is then directly compiled and transformed into
a set of layer-wise FHE-equivalent operations as shown in Listing 1. Orion
takes three passes over the network specification. The first pass collects
input and output tensor dimensions for each layer as well as layer type. The
second pass generates the necessary FHE representation to perform FHE
transformations. The final pass prunes any unnecessary level consumption by
examining network inference under the aforementioned intermediate
representation. From here, the user can verify correctness of the underlying
FHE forward-pass implementation by simulating the FHE inference directly in
PyTorch, thus easing the development process. Finally, the generated
representation is interpreted by an FHE library (we currently support Lattigo)
to run FHE inference in the CKKS scheme.

Similar to prior work, we assume a semi-honest threat model between the two
parties meaning that the parties may be corrupted by an adversary, but the
adversary is passive and will follow the prescribed protocol. Furthermore,
this adversary will try to learn as much private information as they can from
the data they receive throughout the faithful execution of the protocol.
Finally, $\mathsf{Orion}$ always operates at $128$ bit security by choosing
the appropriate FHE parameters.

###  III-B FHE Matrix Operations

We now present mapping strategies for computing FHE matrix-vector with CKKS.
We review prior strategies and then show our three methods: $\mathsf{Square}$,
$\mathsf{Hybrid}$++, and $\mathsf{Partitioned}$. We divide each strategy into
three stages: $\mathsf{Setup}$, $\mathsf{Core}$, and $\mathsf{Repair}$. Since
$\mathsf{Orion}$ handles both fully-connected and convolutional layers, we
also explain our conversion strategy for efficiently expressing convolutions
as matrix-vector products. We note that linear transformations performed in
Lattigo further reduce the number of rotations by performing a baby-step
giant-step algorithm (see Algorithm 6 of [13]). Unless stated otherwise, we
assume input and output sizes are powers of two and that all input and output
data fits in a single ciphertext.

Figure 3: The Naive and Halevi-Shoup Diagonal methods for performing matrix-
vector products under FHE. Halevi-Shoup diagonalization techniques removes the
need for expensive output rotations.

Figure 4: An overview of our three proposed mapping strategies. Note that the
$\mathsf{Hybrid}$++ method tightly packs vectors at the cost of performing two
sequential matrix-vector products thus consuming an additional level.

Naive HE Matrix-Vector product. We begin with the most straightforward but
also most inefficient method for performing FHE matrix-vector products.

#### $\mathsf{Setup}$

Each row of the weight matrix $\mathbf{W}$ is encoded as a separate plaintext
polynomial.

#### $\mathsf{Core}$

Each of these $n_{o}$ polynomials is first multiplied by
$[\\![\mathbf{v}]\\!]$ using $\mathsf{PMult}$ (the first row’s
$\mathsf{PMult}$ is shown in Figure 3). The resulting output ciphertext then
contains each of the partial sums for its corresponding dot product. In order
to obtain the full dot product, each ciphertext then goes through a series of
rotation-and-summations. This process is shown at the top of Figure 3 for the
first row, in which two rotations-and-summations are required to align all
elements of the ciphertext to produce the dot product. Notably, these output
rotations cannot be hoisted out as they are applied to intermediate outputs of
the rotation-and-summations.

#### $\mathsf{Repair}$

Each of the $n_{o}$ final ciphertexts must be combined into a single
ciphertext. This process itself requires $n_{o}$ many $\mathsf{PMult}$ calls
between resulting ciphertexts and a selector polynomial (a one-hot vector set
appropriately) and finally $n_{o}-1$ $\mathsf{HAdd}$ calls to produce the
desired ciphertext. This process is shown in the middle row of Figure 3.

The Halevi-Shoup Diagonal Approach. At a high level, this algorithm processes
the matrix in a diagonal order so that each slot in an intermediate ciphertext
contains a partial sum from a different row of the weight matrix. Therefore,
Halevi-Shoup avoids the need to perform the expensive output rotations that
were necessary in the Naive method.

#### $\mathsf{Setup}$

Since the server has access to the plaintext weight matrix $\mathbf{W}$, the
server is able to first reconfigure the weight matrix without incurring any HE
overhead. In particular, the server can first extract the generalized
diagonals of their weight matrix in the plaintext domain. The diagonals are
expressed as
$\mathsf{diag}_{k}=W_{[0,k]},W_{[1,1+k]},\ldots,W_{[n_{i}-1,n_{i}-1+k]}$ where
the second dimension index is computed modulo $n_{i}$, and each of the $n_{o}$
many diagonals will be of length $n_{i}$. The generalized diagonals are then
encoded as separate plaintext vectors. The four extracted diagonals for the
example matrix are shown in bottom row of Figure 3.

#### $\mathsf{Core}$

We can now perform $\mathsf{PMult}$ between the encoded diagonals and the
input ciphertext $[\\![\mathbf{v}]\\!]$. Since $\mathsf{diag}_{k}$ begins with
a weight element in column $k$ of $\mathbf{W}$, the input ciphertext is
rotated up by $k$ slots in order to align the plaintext diagonal and the
ciphertext. For example, $\mathsf{diag}_{2}$ is multiplied by the input
ciphertext rotated up by 2 slots. These rotations can be hoisted out since
they are applied to the input ciphertext. This process will produce $n_{o}$
intermediate ciphertexts that contain the partial sums of the matrix-vector
product. Finally, the ciphertexts can simply be added together using
$\mathsf{HAdd}$ to produce a single ciphertext corresponding to the desired
matrix-vector product as shown in Figure 3 (bottom row).

#### $\mathsf{Repair}$

In the example shown above, the Halevi-Shoup algorithm does not require post-
processing as the resulting ciphertext is already tightly packed.

Figure 5: Visualizing the $\mathsf{kn2col}$ method for converting general
convolutions to matrix-vector products.

Proposed Method 1: $\mathbf{Square}$. In the Naive and Halevi-Shoup
algorithms, we have not taken into consideration the full ciphertext
structure. In particular, recall from Section II-A that messages are
necessarily encoded in a fixed number of slots, $n$, and often, $n$ is
typically much larger than the either dimensions of $\mathbf{W}$. Therefore,
to produce a valid matrix-vector product in FHE, we must modify our matrix
such that it always has $n$ columns.

In the $\mathsf{Square}$ method, we embed a weight matrix $\mathbf{W}$ of size
$n_{o}\times n_{i}$ inside a larger matrix of size $n\times n$ (slots-by-
slots). Here, $n_{i}$ need not be equal to $n_{o}$. We visualize this in
Figure 4a, where $n_{i}=4,n_{o}=8$, and $n=8$. This direct embedding produces
many relatively sparse diagonals, each which must be multiplied with the input
vector rotated by the correct amount. However, each of these rotation can be
double-hoisted and therefore their cost can be amortized.

#### $\mathsf{Setup}$

We embed our $n_{o}\times n_{i}$ weight matrix $\mathbf{W}$ into an $n\times
n$ matrix given that $n_{i},n_{o}<n$.

#### $\mathsf{Core}$

We now extract the generalized non-zero diagonals. That is, any generalized
diagonal that contains a non-zero element. We now proceed with the standard
Halevi-Shoup algorithm to perform the matrix-vector product.

#### $\mathsf{Repair}$

The first $n_{o}$ many slots of the output ciphertext contains the desired
matrix-vector product as shown in Figure 4a and does not need any post-
processing.

Proposed Method 2: $\mathbf{Hybrid}$++ Rather than producing many sparse
diagonal as was the case in the $\mathsf{Square}$ method, we can attempt to
pack diagonals more tightly in order to minimize the number of rotations. To
this end, we extend Gazelle’s [26] input-packed $\mathsf{Hybrid}$ method to
work in the FHE domain. In particular, Gazelle’s overall inference protocol
allows for a resulting ciphertext from a matrix-vector product to be sent to
the client who can decrypt, tightly pack, re-encrypt, and transmit a fresh
ciphertext back to the server. In our FHE-only setup, there is no
communication between the two parties until the forward pass is complete.
Therefore in our setup, the server must 1) perform the tight repacking
directly on the resulting ciphertext and 2) take into consideration the
remaining levels in the ciphertext. If all levels are consumed, then the
server must perform bootstrapping to proceed.

#### $\mathsf{Setup}$

The weight matrix $\mathbf{W}$ is of size $n_{o}\times n_{i}$, which is
visualized in Figure 4b, with $n_{o}=4,n_{i}=4$, and $n=8$. To fully utilize
the $n$ slots per polynomial, we split the weight matrix $\mathbf{W}$ into $s$
sub-matrices each of size $\nicefrac{{n_{o}}}{{s}}\times n_{i}$. We then
extract and concatenate the generalized diagonals of each sub-matrix such that
the total length of a generalized diagonal is $n$. Figure 4b show the two
extracted and concatenated generalized diagonals for our example matrix.
Finally, we perform input duplication using rotation-and-summations in order
to fill the ciphertext with copies of the input vector $[\\![\mathbf{v}]\\!]$.

#### $\mathsf{Core}$

Now, we can perform the Halevi-Shoup algorithm on these extracted diagonals by
properly rotating the input ciphertext and calling $\mathsf{PMult}$. However
unlike Halevi-Shoup, we must perform $\log(\nicefrac{{s\cdot
n_{i}}}{{n_{o}}})$ output rotations in order to align the partial sums for a
particular row resulting in a ciphertext that contains the desired outputs. As
shown in Figure 4b, the outputs are not tightly packed in the first $n_{o}$
slots of the resulting ciphertext.

#### $\mathsf{Repair}$

To proceed in the following layer, the desired outputs must be re-aligned to
the top $n_{o}$ slots of the final ciphertext. We make use of a permutation
matrix to 1) select and tightly pack the appropriate slots of the resulting
ciphertext into the first $n_{o}$ slots of the final ciphertext and 2) zero
out the remaining $n-n_{o}$ slots. Importantly, this aligning and re-packing
method consumes a level as this stage itself requires a matrix-vector product.

Proposed Method 3: $\mathbf{Partitioned}$. The $\mathsf{Partitioned}$ method
strikes a balance between the $\mathsf{Square}$ and $\mathsf{Hybrid}$++
methods by more tightly packing the diagonals without consuming an additional
level. This approach is visualized in Figure 4c, where $n_{i}=4,n_{o}=8$, and
$n=8$.

#### $\mathsf{Setup}$

We first split the weight matrix $\mathbf{W}$ into
$\nicefrac{{n_{o}}}{{n_{i}}}$ many sub-matrices, each of size $n_{i}\times
n_{i}$, which are then diagonally aligned inside of an $n_{o}\times n$ matrix.
While this method produces generalized diagonals which are more sparse than
the $\mathsf{Hybrid}$++ approach, it preserves the row order of the weight
matrix and therefore does not require an auxiliary permutation matrix. We
again properly align the input ciphertext with each generalized diagonal.

#### $\mathsf{Core}$

We perform $\mathsf{PMult}$ between the generalized diagonals and the input-
rotated ciphertext. Finally, the resulting intermediate ciphertexts can be
combined using $\mathsf{HAdd}$, resulting in a tightly packed ciphertext
containing the desired output.

#### $\mathsf{Repair}$

If $n_{o}\neq n$, then it is necessary to perform output rotation-and-
summations similar to the $\mathsf{Hybrid}$++ method in order to combine the
appropriate partial sums.

###  III-C Expressing Convolutions as Matrix-Vector Products

In order to perform private CNN inference, we must first transform all
convolutional layers into matrix-vector products that are amenable to FHE, and
the de-facto approach is $\mathsf{im2col}$ (image-to-column). However,
$\mathsf{im2col}$ requires heavy re-structuring of the input ciphertext and
thus incurs a large overhead under FHE.

Figure 6: Overview of $\mathsf{Orion}$’s performance on our microbenchmarks
for the three proposed mapping strategies.

Therefore, an ideal algorithm for converting convolutions to matrix-vector
products in an FHE setting is one that keeps the encrypted output of the
previously layer as a vector in raster-scan fashion and instead expands the
kernel to form the correct matrix. This less-common technique is known as
$\mathsf{kn2col}$ (kernel-to-column), and we refer to the resulting matrices
as Toeplitz matrices following the convention of [27]. To the best of our
knowledge slytHErin [28] is the only prior work which proposes a similar
strategy. We visualize the conversion from a traditional convolution to a
matrix-vector product using the $\mathsf{kn2col}$ method in Fig 5, where
$c_{i}=c_{o}=2$, $w_{i}=h_{i}=3$, $f_{w}=f_{h}=3$, with padding and stride
both set to $1$. In general, the $\mathsf{kn2col}$ matrix will be of size
$c_{o}w_{o}h_{o}\times c_{i}w_{i}h_{i}$, with each row corresponding to one
filter multiplication.

There are several benefits of thinking about expressing convolutions as
matrix-vector products using $\mathsf{kn2col}$. First, this method produces
dense diagonals, and since the number of hoisted ciphertext rotations is equal
to the number of diagonals in a matrix-vector product, dense diagonals ensure
a minimal number of rotations. Second, distinct filter elements lie along the
same diagonal. In effect, this guarantees that the number of diagonals is
independent of the size of the input or output image and instead only depends
on filter size. We close with one implementation detail. Since strided
convolutions create punctures in the underlying ciphertext, it is important to
fill these punctures with computations from other independent convolutional
filters. To this end, we adopt a “multiplexed” packing technique similar to
Lee et al. [29] which consumes an additional level per convolution as we must
undo this packing for future layers.

##  IV Evaluation

In this section, we begin by describing our experimental setup. Next, we run a
set of microbenchmarks through $\mathsf{Orion}$ to better understand trade-
offs between level consumption, mapping strategies, and hoisted versus non-
hoisted rotations. Then, we evaluate $\mathsf{Orion}$ on different neural
networks and compare performance against prior solutions, and finally we
explore the interplay between packing density and rotation procedure.

Figure 7: Breakdown of ResNet-20 layer runtimes for the three proposed mapping
strategies.

###  IV-A Evaluation Setup

We evaluate $\mathsf{Orion}$ using an r7g.16xlarge AWS instance with a
Graviton3 processor clocked at 2.6GHz and 512GB of RAM. We integrate
$\mathsf{Orion}$ into the PyTorch framework; $\mathsf{Orion}$ generates the
required FHE code and configuration parameters to run these networks under
FHE. This representation could then be interpreted by many of the standard FHE
libraries, and here we target Lattigo v4.1 as our backend. To make a fair
comparison with prior work, we rerun Lee et al. [29] and Kim et al. [30] on
the same instance. Reported latencies are singled-threaded and averaged over
$20$ distinct trials.

###  IV-B Microbenchmarks

Despite the growing interest in FHE applications, we find that there is still
a lack of support for a concrete set of microbenchmarks that explore the
tradeoff between level consumption and slot utilization. FHE parameter choice
and tensor shape can have a large impact on performance. Therefore, we begin
our evaluation with microbenchmarks to build intuition about the strengths of
$\mathsf{Orion}$, and will release these implementations (along with the
neural networks presented next) to facilitate commensurable FHE neural
inference research moving forward.

We develop a class of microbenchmarks that fall into three distinct
categories: Traditional kernels reflect common operations found in standard
CNNs. These include same-style (i.e., padded) convolutions on power-of-two
input sizes, strided convolutions, and wide fully-connected layers. Challenge
kernels stress compiler flexibility and performance with non-power-of-two
input sizes, non-square kernels, and arbitrary padding. We find these kernels
to be the most difficult to support as they introduce non-uniform slot
utilization in the resulting ciphertexts. Batched operations pack multiple
inputs into one ciphertext. As multi-key homomorphic schemes [31, 32] become
more prevalent, we expect the importance of batched inferences to grow as
well.

As discussed in Section III, levels can highly impact runtime. Therefore, we
run each kernel at three different levels, $L=L_{\text{min}}$, $8$, and $16$
to rigorously compare our mapping strategies. Here, $L_{\text{min}}$ is the
minimum level that the kernel can be computed for the respective mapping
strategies. Recall that our $\mathsf{Hybrid}$++ method necessarily consumes
two levels per convolution due to the auxiliary repair matrix required to
realign and mask data for the following layer. In contrast, our
$\mathsf{Partitioned}$ method only requires one level at the expense of lower
slot utilization. Therefore, $L_{\text{min}}$ is $1$ for
$\mathsf{Partitioned}$ (and $\mathsf{Square}$) and $2$ for $\mathsf{Hybrid}$++
approach. In all cases, we set $N=2^{16}$, which is a standard polynomial ring
degree for FHE applications that require bootstrapping [29, 30].

Figure 6 details our nine microbenchmarks and reports their runtimes on the
three mapping strategies proposed in Section III. We make key observations
through our microbenchmarks that determine our choice of optimal mapping
strategies in our neural network evaluation.

First, despite a lower slot utilization, our $\mathsf{Partitioned}$ method
consistently outperforms the $\mathsf{Hybrid}$++ (and $\mathsf{Square}$)
method at $L_{\text{min}}$. This outcome is counter-intuitive given that prior
work optimizes for slot utilization (e.g., Gazelle [26] and Lee et al. [29]).
However, the necessary repair matrix in the $\mathsf{Hybrid}$++ method
introduces a trade-off between level consumption and slot utilization.
Although the $\mathsf{Hybrid}$++ method is more tightly packed, it consumes
twice the level as $\mathsf{Partitioned}$, thus doubling the amount of
computation required for the same calculation. Therefore, packing data as
tightly as possible in order to minimize the total number of rotations is not
equivalent to minimizing runtime in FHE settings.

Second, strided convolutions are expensive (often $4\times$ slower than their
non-strided counterparts). Recall from Section III that regardless of mapping
strategy, $L_{\text{min}}=2$, since we must undo the multiplexed packing
technique for future layers. Heuristically, we find that the $\mathsf{Square}$
method minimizes the aggregate runtime of strided convolutions in part due to
a substantially simpler repair matrix, and therefore adopt the
$\mathsf{Square}$ approach for all strided convolutions going forward.
Furthermore, $\mathsf{Orion}$ attempts to perform strided convolutions at the
lowest level possible. This entails judiciously mapping the locations of
$\mathsf{Bootstrap}$ operations.

###  IV-C Benchmarks

We evaluate $\mathsf{Orion}$ on a range of convolutional and fully-connected
neural networks. Our network architectures are as follows. MLP is a three-
layer fully-connected network from SecureML [33] for MNIST [34]. This network
is used in prior work [26, 35] and represents a starting point for our
evaluation. LoLA is a three-layer convolutional neural network from LoLA-
CryptoNets [36] also targeting MNIST. LoLA is our simplest CNN architecture
that consists of one strided convolution and two fully-connected layers. LeNet
(Large) [34] is a four-layer convolutional neural network adopted from CHET
[9] and EVA [10]. It is the largest of their LeNet benchmarks and consists of
two strided-convolutions followed by two fully-connected layers. We modify
LeNet for CIFAR10 rather than MNIST to make it more challenging. ResNets [37]
have seen widespread success in computer vision tasks. ResNets are also the
most complicated neural networks supported by prior hand-crafted FHE
solutions. We evaluate the ResNet-20 architecture on CIFAR10 and ResNet-32 on
CIFAR100, similar to [29].

Table II reports the runtime of each neural network for all three mapping
strategies alongside relevant CKKS parameters. We detail several high-level
insights and observations before exploring the ResNet results in more detail.
First, even our smallest benchmark, MLP, requires a polynomial ring degree,
$N=2^{14}$ to remain 128-bit secure. This is vastly more slots than required,
therefore small networks such as these are ideal for batching. Second, we note
the differences in maximum multiplicative level, $L$, between mapping
strategies. In networks that do not require bootstrapping, our
$\mathsf{Hybrid}$++ approach requires more levels than than $\mathsf{Square}$
and $\mathsf{Partitioned}$. This is the result of the repair matrix. Moreover,
the increase in multiplicative depth leads the $\mathsf{Hybrid}$++ method to
consistently perform worse than $\mathsf{Partitioned}$, and sometimes even
worse than $\mathsf{Square}$. Finally, we observe latencies that are
$15\times$ and $30\times$ lower than the single-threaded results reported in
EVA and CHET, respectively. While there have been several advancements to FHE
algorithms since its publication [12, 13], we suspect a large fraction of
speedup stems from $\mathsf{Orion}$’s support for hoisted rotations.

We now analyze the results of our ResNet-20 implementation in detail and
compare against prior hand-crafted solutions. We divide each linear and
convolutional layer into two segments: one section in which hoisted rotations
are employed to compute the necessary matrix-vector products and another for
operations where hoisting is not possible (e.g., input duplication and output
rotations). Figure 7 shows the per-layer ResNet-20 runtime for all three
methods and is divided into the hoisted and non-hoisted segments.

We note that $\mathsf{Square}$ avoids performing any non-hoisted operations,
albeit at the cost of consistency higher runtimes compared to the
$\mathsf{Hybrid}$++ and $\mathsf{Partitioned}$ methods. This is because
$\mathsf{Square}$ over-provisions unnecessary hoisted rotations and often
exhibits poor slot utilization that leads to high layer runtimes. On the other
hand, $\mathsf{Hybrid}$++ and $\mathsf{Partitioned}$ optimize for both slot
utilization and hoisted rotations.

Additionally, we see that the $\mathsf{Hybrid}$++ method exhibits the lowest
per-layer latency. However, this method is bottlenecked by an increase in
$\mathsf{Bootstrap}$ operations due to the auxiliary repair matrix consuming
an additional level. While this may initially seem at odds with our
microbenchmark results, we find that an increased frequency in bootstrapping
results in $\mathsf{Hybrid}$++ convolutions being performed at lower levels
than the $\mathsf{Square}$ and $\mathsf{Partitioned}$ alternatives accounting
for the performance differences.

Table III further breaks down ResNet-20 inference latency into the time for
convolutional layers, activation functions, $\mathsf{Bootstrap}$ operations,
and linear layers. We rerun the work by Lee et al. [29] and Kim et al. [30]
for a fair comparison and report their runtimes on the same operations. We
also port the network architecture and CKKS parameters from Lee et al. [29],
denoted as Lee (Opt.) in Table III, to Lattigo to better understand the
balance between convolutional and $\mathsf{Bootstrap}$ runtimes. We find that
$\mathsf{Orion}$ outperforms both state-of-the-art rotation-based and FFT-
based solutions.

First, although FFT-based solutions are mostly rotation-free (i.e., avoid
expensive key-switching operations), they necessitate bootstrapping after
every convolution, regardless of the activation function. Therefore, the
bootstrapping runtime observed from Kim et al. [30] in Table III establishes a
hard lower-bound on their latency. $\mathsf{Orion}$ avoids this by taking a
rotation-based approach, similar to Lee et al. [29]. This gives us the
flexibility to choose the levels at which convolutions are performed and the
locations of $\mathsf{Bootstrap}$ operations to further decrease latency. This
performance increase can be observed in Table III, where all three of
$\mathsf{Orion}$’s mapping strategies achieve $2-3\times$ lower latencies than
just the $\mathsf{Bootstrap}$ runtimes of Kim et al. [30], despite an increase
in convolutional runtime.

Second, although the convolutional runtime of $\mathsf{Hybrid}$++ is faster
than $\mathsf{Partitioned}$, the increase in $\mathsf{Bootstrap}$ operations
from $5$ to $8$ results in an overall higher latency. This further emphasizes
that minimizing level consumption is as important as maximizing slot
utilization in FHE.

Finally, we compare the performance of $\mathsf{Orion}$ to the prior state-of-
the-art rotation-based approach of Lee et. al. [29]. Similar to Kim et. at.
[30], Lee et. al. [29] perform convolutions at the lowest level possible
(i.e., $L_{\text{min}}$). This is primarily due to their use of high-degree
polynomials to approximate the ReLU activation function. Despite
$\mathsf{Orion}$ performing convolutions at much higher levels, we still see
roughly a $15\times$ and $11\times$ improvement in convolutional runtimes in
the $\mathsf{Hybrid}$++ and $\mathsf{Partitioned}$ methods, respectively. In
total, we observe over a $20\times$ speedup in end-to-end latency compared to
Lee et al.[29]. We supplement our analysis by replicating the network
architecture and CKKS parameters from Lee et al. to perform convolutions at
$L_{\text{min}}$. Here, we apply the $\mathsf{Hybrid}$++ approach to all
convolutions, and focus on the trade-off between convolutional and
bootstrapping runtimes. From this, we gain two key insights: 1) bootstrapping
once again dominates runtime, similar to Kim et al. [30]. Therefore rotation-
based approaches are ideal when coupled with the use of lower degree
polynomials as activation functions, which afford a greater flexibility in the
choice of $\mathsf{Bootstrap}$ locations, and 2) Lee et al. [29] optimize for
convolutional runtime at the expense of end-to-end latency. This is seen in
Table III by comparing the $\mathsf{Bootstrap}$ runtime of our optimized
implementation of Lee et al. with all three of $\mathsf{Orion}$’s proposed
mapping strategies. This latency difference suggests that to better balance
the trade-off between convolutional and $\mathsf{Bootstrap}$ runtime (i.e.,
minimize end-to-end latency), convolutions must necessarily be performed at
higher levels than all prior work.

TABLE II: Network architectures and runtimes. Network | Method | $N$ | $L$ | $\log QP$ | Bootstraps | Runtime (s)
---|---|---|---|---|---|---
MLP [33] | $\mathsf{S}$ | $2^{14}$ | $7$ | $437$ | $0$ | $1.09$
$\mathsf{H}$++ | $9$ | $419$ | $1.21$
$\mathsf{P}$ | $7$ | $437$ | $0.62$
LoLA [36] | $\mathsf{S}$ | $2^{14}$ | $8$ | $428$ | $0$ | $1.91$
$\mathsf{H}$++ | $9$ | $419$ | $1.48$
$\mathsf{P}$ | $8$ | $428$ | $1.29$
LeNet (Large) [9] | $\mathsf{S}$ | $2^{15}$ | $11$ | $847$ | $0$ | $14.4$
$\mathsf{H}$++ | $12$ | $831$ | $9.33$
$\mathsf{P}$ | $11$ | $847$ | $9.12$
ResNet-20 [37] | $\mathsf{S}$ | $2^{16}$ | $26$ | $1521$ | $5$ | $155.6$
$\mathsf{H}$++ | $26$ | $1521$ | $8$ | $181.4$
$\mathsf{P}$ | $26$ | $1521$ | $5$ | $139.7$
ResNet-32 [37] | $\mathsf{S}$ | $2^{16}$ | $26$ | $1521$ | $9$ | $287.9$
$\mathsf{H}$++ | $26$ | $1521$ | $14$ | $312.1$
$\mathsf{P}$ | $26$ | $1521$ | $9$ | $260.1$
TABLE III: ResNet-20 comparison with prior work. ResNet-20 Breakdown (secs.) | FFT-Based | Rotation-Based
---|---|---
Kim et. al. [30] |  Lee et. al. [29] |  Lee (Opt.) |  Orion ($\mathsf{S}$) |  Orion ($\mathsf{H}$++) |  Orion ($\mathsf{P}$)
Conv. | $9.88$ | $438.6$ | $18.25$ | $54.2$ | $28.9$ | $40.4$
Act. | $53.78$ | $244.5$ | $3.34$ | $3.45$ | $3.14$ | $3.45$
Boot. | $282.5$ | $2138$ | $344.6$ | $92.6$ | $144.6$ | $92.0$
Linear | $3.52$ | $14.52$ | $0.89$ | $1.99$ | $0.90$ | $0.46$
Other | $21.69$ | $29.11$ | $0.21$ | $3.41$ | $3.85$ | $3.40$
Total (s) | $371.4$ | $2864$ | $367.3$ | $155.6$ | $181.4$ | $139.7$

###  IV-D Dense Packing and Non-Hoisted Rotations

We close with an observation about our $\mathsf{Hybrid}$++ method. Recall from
Section III that when possible, this method packs multiple copies of the same
input into one ciphertext, thereby increasing slot utilization. In this case,
however, increasing slot utilization comes at the cost of increasing the
amount of non-hoisted rotations both in terms of input packing and output
rotations. Therefore, a natural question to ask is whether we should be
tightly packing data, or if the increase in expensive non-hoisted rotations
negates any potential improvements.

We illustrate this trade-off with the $256\times 1024$ FC microbenchmark with
$L=16$ and $N=2^{16}$ ($n=2^{15}$). Recall from Section III that when
$n_{o}<n$, we can pack $\nicefrac{{n}}{{n_{o}}}$ many copies of the same input
into one ciphertext to utilize all available slots; here,
$\nicefrac{{n}}{{n_{o}}}=32$. We explore the impact of more sparsely packing
slots by varying this value from $1$ up to $32$ in Figure 8. We plot both
hoisted and non-hoisted latencies as well as their aggregate runtime. Notably,
past a certain point, the reduction in latency from a more tightly packed
ciphertext is offset by an increase in latency from performing more non-
hoisted rotations. The $\mathsf{Hybrid}$++ method, as described in Section
III, greedily packs the ciphertext and moves beyond the optimal strategy as
shown in Figure 8. For this microbenchmark, we find that the optimal number of
inputs to pack in order to minimize runtime latency is $8$ copies of the input
(Optimized $\mathsf{Hybrid}$++), which results in $75$% of slots going unused.
This optimization, albeit counter-intuitive, is natively supported by
$\mathsf{Orion}$.

Figure 8: Packing density versus latency for $\mathsf{Hybrid}$++.

##  V Related Work

Prior work broadly falls into three categories: FHE-only, hybrid, and
compiler-based solutions. Table IV summaries key prior literature.

For FHE-based protocols, Cryptonets [38] was the seminal paper introducing
private neural network inference via FHE and adopted the use of FHE-amenable
polynomial activation functions. Following this work, several optimizations to
data layouts were proposed to both reduce latency and increase throughput [36,
39]. Since then, Lee et al. [29, 28] proposed high-degree polynomial
activation functions in order to support deeper networks such as ResNets.
HyPHEN [25] uses low-degree polynomials and reduces the number of HE rotations
for their linear algebra kernels. Finally, Kim et al. [30] avoids rotations
entirely by using an FFT-based solution at the cost of introducing a large
number of bootstrap operations.

Besides FHE-only solutions, SecureML [33] proposed a hybrid protocol for
private inference, which leveraged FHE for the linear layers and multi-party
computations (MPC) protocols for non-linear functions prevalent in standard
CNNs such as ReLU. Gazelle [26] further expanded upon the work of SecureML
[33] by proposing several packing strategies for rotation-based matrix-vector
products for computing convolutions and fully-connected layers. Cheetah [40]
proposed both SIMD-Free and Rotation-Free FHE algorithms, but still employ
communication-heavy MPC protocols for computing ReLU. Several prior works also
focus on compiler design in order to lower the barrier of entry for deploying
FHE. CHET [9] builds a domain-specific language to automatically generate a
set of FHE primitives for a given neural network and systematically explores
the FHE parameter space to outperform manually written FHE programs. EVA [10]
extends the work of CHET by optimizing FHE level consumption to further reduce
HE runtime. CHET and EVA specifically target neural network inference, and
compilers that target arbitrary FHE programs also exist [7, 11, 8]. Most
compilers build on top of existing FHE frameworks, e.g., Lattigo [15], SEAL
[41], HELib [42], OpenFHE [43], HEAAN [16].

TABLE IV: Comparison of Prior Work. Prior Work |  Auto- mated |  FHE Only |  Deep Networks |  Batching Support |  Arbitrary Convolutions
---|---|---|---|---|---
Lee et al. [29] |  |  |  |  |
Kim et al. [30] |  |  |  |  |
HyPHEN [25] |  |  |  |  |
Gazelle [26] |  |  |  |  |
Cheetah [40] |  |  |  |  |
SlytHErin [28] |  |  |  |  |
CHET [9] |  |  |  |  |
EVA [10] |  |  |  |  |
HeLayers [44] |  |  |  |  |
HEMET [45] |  |  |  |  |
Porcupine [7] |  |  |  |  |
Coyote [8] |  |  |  |  |
HECO [11] |  |  |  |  |
Orion (ours) |  |  |  |  |

##  VI Conclusion

Recent advancements in Fully Homomorphic Encryption continue to push the field
into the realm of practicality. And while prior work has shown promising
solutions to the use of FHE for neural network inference, they have been
unable able to fully realize the potential of existing FHE techniques due to
complexities such as limited programmability, parameter selection, and slot
utilization, which often require expert knowledge. Our solution,
$\mathsf{Orion}$, solves each of these issues by allowing practitioners to
work in an accessible language such as PyTorch and automatically balances many
of the aforementioned FHE intricacies. Furthermore, our compiler-based
approach outperforms hand-crafted solutions while remaining general purpose
and supports arbitrarily deep networks. Furthermore through our analysis, we
find counter-intuitive tradeoffs between slot utilization, level consumption,
and bootstrapping management. In particular, packing data as tightly as
possible in order to minimize the total number of rotations is not equivalent
to minimizing runtime in FHE settings. Finally, we hope that by open-sourcing
$\mathsf{Orion}$, we ease the development of FHE-based neural network systems
for practitioners and better inform the community about the unique challenges
and opportunities present in FHE.

## Acknowledgements

This work was supported in part by Graduate Assistance in Areas of National
Need (GAANN). The research was developed with funding from DARPA, under the
Data Protection in Virtual Environments (DPRIVE) program, contract
HR0011-21-9-0003. Reagen and Ebel received generous support from the NY State
Center for Advanced Technology in Telecommunications (CATT) and a gift award
from Google. We especially thank Jean-Phillipe Bossuat for the insightful
discussions and valuable feedback. The views, opinions, and/or findings
expressed are those of the authors and do not necessarily reflect the views of
sponsors.

## References

  * [1] B. Reagen, W.-S. Choi, Y. Ko, V. T. Lee, H.-H. S. Lee, G.-Y. Wei, and D. Brooks, “Cheetah: Optimizing and accelerating homomorphic encryption for private inference,” in _2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_ , 2021, pp. 26–39.
  * [2] A. Feldmann, N. Samardzic, A. Krastev, S. Devadas, R. Dreslinski, K. Eldefrawy, N. Genise, C. Peikert, and D. Sanchez, “F1: A fast and programmable accelerator for fully homomorphic encryption (extended version),” 2021.
  * [3] S. Kim, J. Kim, M. J. Kim, W. Jung, J. Kim, M. Rhu, and J. H. Ahn, “BTS,” in _Proceedings of the 49th Annual International Symposium on Computer Architecture_. ACM, jun 2022. [Online]. Available: https://doi.org/10.1145%2F3470496.3527415
  * [4] N. Samardzic, A. Feldmann, A. Krastev, N. Manohar, N. Genise, S. Devadas, K. Eldefrawy, C. Peikert, and D. Sanchez, “Craterlake: A hardware accelerator for efficient unbounded computation on encrypted data,” in _Proceedings of the 49th Annual International Symposium on Computer Architecture_ , ser. ISCA ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 173–187. [Online]. Available: https://doi.org/10.1145/3470496.3527393
  * [5] D. Soni, N. Neda, N. Zhang, B. Reynwar, H. Gamil, B. Heyman, M. Nabeel, A. A. Badawi, Y. Polyakov, K. Canida, M. Pedram, M. Maniatakos, D. B. Cousins, F. Franchetti, M. French, A. Schmidt, and B. Reagen, “Rpu: The ring processing unit,” 2023.
  * [6] J. Kim, S. Kim, J. Choi, J. Park, D. Kim, and J. H. Ahn, “Sharp: A short-word hierarchical accelerator for robust and practical fully homomorphic encryption,” in _Proceedings of the 50th Annual International Symposium on Computer Architecture_ , ser. ISCA ’23. New York, NY, USA: Association for Computing Machinery, 2023. [Online]. Available: https://doi.org/10.1145/3579371.3589053
  * [7] M. Cowan, D. Dangwal, A. Alaghi, C. Trippel, V. T. Lee, and B. Reagen, “Porcupine: A synthesizing compiler for vectorized homomorphic encryption,” in _Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation_ , ser. PLDI 2021. New York, NY, USA: Association for Computing Machinery, 2021, p. 375–389. [Online]. Available: https://doi.org/10.1145/3453483.3454050
  * [8] R. Malik, K. Sheth, and M. Kulkarni, “Coyote: A compiler for vectorizing encrypted arithmetic circuits,” in _Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3_ , ser. ASPLOS 2023. New York, NY, USA: Association for Computing Machinery, 2023, p. 118–133. [Online]. Available: https://doi.org/10.1145/3582016.3582057
  * [9] R. Dathathri, O. Saarikivi, H. Chen, K. Laine, K. Lauter, S. Maleki, M. Musuvathi, and T. Mytkowicz, “Chet: An optimizing compiler for fully-homomorphic neural-network inferencing,” in _Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation_ , ser. PLDI 2019. New York, NY, USA: Association for Computing Machinery, 2019, p. 142–156. [Online]. Available: https://doi.org/10.1145/3314221.3314628
  * [10] R. Dathathri, B. Kostova, O. Saarikivi, W. Dai, K. Laine, and M. Musuvathi, “EVA: an encrypted vector arithmetic language and compiler for efficient homomorphic computation,” in _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_. ACM, jun 2020. [Online]. Available: https://doi.org/10.1145%2F3385412.3386023
  * [11] A. Viand, P. Jattke, M. Haller, and A. Hithnawi, “Heco: Fully homomorphic encryption compiler,” 2023.
  * [12] K. Han and D. Ki, “Better bootstrapping for approximate homomorphic encryption,” in _Topics in Cryptology – CT-RSA 2020: The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24–28, 2020, Proceedings_. Berlin, Heidelberg: Springer-Verlag, 2020, p. 364–390. [Online]. Available: https://doi.org/10.1007/978-3-030-40186-3_16
  * [13] J.-P. Bossuat, C. Mouchet, J. Troncoso-Pastoriza, and J.-P. Hubaux, “Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys,” in _Advances in Cryptology – EUROCRYPT 2021_ , A. Canteaut and F.-X. Standaert, Eds. Cham: Springer International Publishing, 2021, pp. 587–617.
  * [14] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “Pytorch: An imperative style, high-performance deep learning library,” 2019.
  * [15] “Lattigo v4,” Online: https://github.com/tuneinsight/lattigo, Aug. 2022, ePFL-LDS, Tune Insight SA.
  * [16] J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in _Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I 23_. Springer, 2017, pp. 409–437.
  * [17] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , 2009, pp. 169–178.
  * [18] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic encryption without bootstrapping,” in _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_ , ser. ITCS ’12. New York, NY, USA: Association for Computing Machinery, 2012, p. 309–325. [Online]. Available: https://doi.org/10.1145/2090236.2090262
  * [19] Z. Brakerski, “Fully homomorphic encryption without modulus switching from classical gapsvp,” in _Advances in Cryptology – CRYPTO 2012_ , R. Safavi-Naini and R. Canetti, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 868–886.
  * [20] J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” Cryptology ePrint Archive, Paper 2012/144, 2012, https://eprint.iacr.org/2012/144. [Online]. Available: https://eprint.iacr.org/2012/144
  * [21] V. Lyubashevsky, C. Peikert, and O. Regev, “On ideal lattices and learning with errors over rings,” in _Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29_. Springer, 2010, pp. 1–23.
  * [22] S. Halevi and V. Shoup, “Algorithms in helib,” Cryptology ePrint Archive, Paper 2014/106, 2014, https://eprint.iacr.org/2014/106. [Online]. Available: https://eprint.iacr.org/2014/106
  * [23] K. Garimella, N. K. Jha, and B. Reagen, “Sisyphus: A cautionary tale of using low-degree polynomial activations in privacy-preserving deep learning,” in _ACM CCS Workshop on Private-preserving Machine Learning_ , 2021.
  * [24] J. Park, M. J. Kim, W. Jung, and J. H. Ahn, “Aespa: Accuracy preserving low-degree polynomial activation for fast private inference,” 2022.
  * [25] D. Kim, J. Park, J. Kim, S. Kim, and J. H. Ahn, “Hyphen: A hybrid packing method and optimizations for homomorphic encryption-based neural networks,” 2023.
  * [26] C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan, “GAZELLE: A low latency framework for secure neural network inference,” in _27th USENIX Security Symposium (USENIX Security 18)_. Baltimore, MD: USENIX Association, Aug. 2018, pp. 1651–1669. [Online]. Available: https://www.usenix.org/conference/usenixsecurity18/presentation/juvekar
  * [27] M. Gnacik and K. Łapa, “Using toeplitz matrices to obtain 2d convolution,” 10 2022.
  * [28] F. Intoci, S. Sav, A. Pyrgelis, J.-P. Bossuat, J. R. Troncoso-Pastoriza, and J.-P. Hubaux, “slytherin: An agile framework for encrypted deep neural network inference,” 2023.
  * [29] E. Lee, J.-W. Lee, J. Lee, Y.-S. Kim, Y. Kim, J.-S. No, and W. Choi, “Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions,” in _Proceedings of the 39th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, Eds., vol. 162. PMLR, 17–23 Jul 2022, pp. 12 403–12 422. [Online]. Available: https://proceedings.mlr.press/v162/lee22e.html
  * [30] D. Kim and C. Guyot, “Optimized privacy-preserving cnn inference with fully homomorphic encryption,” _IEEE Transactions on Information Forensics and Security_ , vol. 18, pp. 2175–2187, 2023.
  * [31] H. Chen, W. Dai, M. Kim, and Y. Song, “Efficient multi-key homomorphic encryption with packed ciphertexts with application to oblivious neural network inference,” in _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ , 2019, pp. 395–412.
  * [32] J. Ma, S.-A. Naas, S. Sigg, and X. Lyu, “Privacy-preserving federated learning based on multi-key homomorphic encryption,” _International Journal of Intelligent Systems_ , vol. 37, no. 9, pp. 5880–5901, 2022.
  * [33] P. Mohassel and Y. Zhang, “Secureml: A system for scalable privacy-preserving machine learning,” Cryptology ePrint Archive, Paper 2017/396, 2017, https://eprint.iacr.org/2017/396. [Online]. Available: https://eprint.iacr.org/2017/396
  * [34] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [35] J. Liu, M. Juuti, Y. Lu, and N. Asokan, “Oblivious neural network predictions via minionn transformations,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 619–631. [Online]. Available: https://doi.org/10.1145/3133956.3134056
  * [36] A. Brutzkus, O. Elisha, and R. Gilad-Bachrach, “Low latency privacy preserving inference,” in _International Conference on Machine Learning_ , 2019.
  * [37] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” 2015.
  * [38] R. Gilad-Bachrach, N. Dowlin, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing, “Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy,” in _Proceedings of The 33rd International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, M. F. Balcan and K. Q. Weinberger, Eds., vol. 48. New York, New York, USA: PMLR, 20–22 Jun 2016, pp. 201–210. [Online]. Available: https://proceedings.mlr.press/v48/gilad-bachrach16.html
  * [39] E. Chou, J. Beal, D. Levy, S. Yeung, A. Haque, and L. Fei-Fei, “Faster cryptonets: Leveraging sparsity for real-world encrypted inference,” 2018.
  * [40] Z. Huang, W. jie Lu, C. Hong, and J. Ding, “Cheetah: Lean and fast secure two-party deep neural network inference,” Cryptology ePrint Archive, Paper 2022/207, 2022, https://eprint.iacr.org/2022/207. [Online]. Available: https://eprint.iacr.org/2022/207
  * [41] “Microsoft SEAL (release 4.1),” https://github.com/Microsoft/SEAL, Jan. 2023, microsoft Research, Redmond, WA.
  * [42] S. Halevi and V. Shoup, “Design and implementation of helib: a homomorphic encryption library,” Cryptology ePrint Archive, Paper 2020/1481, 2020, https://eprint.iacr.org/2020/1481. [Online]. Available: https://eprint.iacr.org/2020/1481
  * [43] A. A. Badawi, J. Bates, F. Bergamaschi, D. B. Cousins, S. Erabelli, N. Genise, S. Halevi, H. Hunt, A. Kim, Y. Lee, Z. Liu, D. Micciancio, I. Quah, Y. Polyakov, S. R.V., K. Rohloff, J. Saylor, D. Suponitsky, M. Triplett, V. Vaikuntanathan, and V. Zucca, “Openfhe: Open-source fully homomorphic encryption library,” Cryptology ePrint Archive, Paper 2022/915, 2022, https://eprint.iacr.org/2022/915. [Online]. Available: https://eprint.iacr.org/2022/915
  * [44] E. Aharoni, A. Adir, M. Baruch, N. Drucker, G. Ezov, A. Farkash, L. Greenberg, R. Masalha, G. Moshkowich, D. Murik, H. Shaul, and O. Soceanu, “HeLayers: A tile tensors framework for large neural networks on encrypted data,” _Proceedings on Privacy Enhancing Technologies_ , vol. 2023, no. 1, pp. 325–342, jan 2023. [Online]. Available: https://doi.org/10.56553%2Fpopets-2023-0020
  * [45] Q. Lou and L. Jiang, “Hemet: A homomorphic-encryption-friendly privacy-preserving mobile neural network architecture,” 2021.