# CiFlow: Dataflow Analysis and Optimization of Key Switching for Homomorphic
Encryption

Negar Neda1, Austin Ebel1, Benedict Reynwar2, and Brandon Reagen1  1New York
University, New York, New York, USA, {negar, abe5240<EMAIL_ADDRESS>2Information Sciences Institute, University of Southern California, Arlington,
VA, USA<EMAIL_ADDRESS>
###### Abstract

Homomorphic encryption (HE) is a privacy-preserving computation technique that
enables computation on encrypted data. Today, the potential of HE remains
largely unrealized as it is impractically slow, preventing it from being used
in real applications. A major computational bottleneck in HE is the key-
switching operation, accounting for approximately 70% of the overall HE
execution time and involving a large amount of data for inputs, intermediates,
and keys. Prior research has focused on hardware accelerators to improve HE
performance, typically featuring large on-chip SRAMs and high off-chip
bandwidth to deal with large scale data.

In this paper, we present a novel approach to improve key-switching
performance by rigorously analyzing its dataflow. Our primary goal is to
optimize data reuse with limited on-chip memory to minimize off-chip data
movement. We introduce three distinct dataflows: Max-Parallel (MP), Digit-
Centric (DC), and Output-Centric (OC), each with unique scheduling approaches
for key-switching computations. Through our analysis, we show how our proposed
Output-Centric technique can effectively reuse data by significantly lowering
the intermediate key-switching working set and alleviating the need for
massive off-chip bandwidth. We thoroughly evaluate the three dataflows using
the RPU, a recently published vector processor tailored for ring processing
algorithms, which includes HE. This evaluation considers sweeps of bandwidth
and computational throughput, and whether keys are buffered on-chip or
streamed. With OC, we demonstrate up to 4.16$\times$ speedup over the MP
dataflow and show how OC can save 16$\times$ on-chip SRAM by streaming keys
for minimal performance penalty.

##  I Introduction

Today, many computations are outsourced to the cloud, whether to leverage its
scale or overcome performance constraints of locally available devices (e.g.,
smartphones). Despite the success of this computational model, it remains
vulnerable to attack and does not provide users with strong privacy and
security guarantees over who can view and use their data. Homomorphic
encryption (HE) [1] offers a solution. With HE, functions computed on
ciphertext are also directly applied to the underlying plaintext. This
facilitates direct computation on encrypted data, extending cryptographic
security from communication and storage to include computation for complete
end-to-end secure outsourced computation.

Many HE schemes (e.g., BGV [2], BFV [3, 4], and CKKS [5]) and software
implementations (e.g., OpenFHE [6], Lattigo [7], SEAL [8]) now exist and have
made steady performance improvements over the years. Despite these strides,
all implementations and schemes still carry substantial performance overheads,
limiting HE’s practical deployment. Slowdowns arise from three issues: large
data sizes, complex operations, and additional functions. When encrypting and
processing HE ciphertexts, the data becomes significantly larger than
plaintext, forming large ciphertext vectors of up to 217 elements. Here, each
plaintext element is represented by hundreds to thousands of bits, and special
precomputed keys ($\mathbf{evks}$) are needed for certain operations (i.e.,
multiplication and rotation) that can be upwards of hundreds of MBs. This puts
substantial pressure on the memory system. Next, HE requires complex modular
arithmetic for processing each element, which is not natively supported by
commercial processors. Finally, HE operations are not one-to-one conversions
of plaintext operators; they involve multiple additional functions for
performance (e.g., Number Theoretic Transforms (NTT)) and correctness before
and after the actual operation (e.g., multiplication and rotation). These
factors collectively overwhelm commodity hardware, and prior work has
consistently reported 4-6 orders of magnitude slowdown compared to plaintext
[9, 10, 11, 12].

The slowdown has been addressed by a growing body of prior work on hardware
acceleration for HE. Many solutions now exist that consider fixed-function
pipelines [9], vector architectures [10, 13, 14], and tiled architectures [15,
16]. The architectural approaches taken differ, but the building blocks are
the same: very large on-chip memories and high off-chip bandwidth. For
example, CraterLake [13]) uses 256 MB of on-chip SRAM and assumes two HBM2e
PHYs for a total bandwidth of 1TB/s. BTS [15] and ARK [16] both have 512 MB of
on-chip SRAM and also assume 1TB/s of memory bandwidth. The large on-chip
SRAMs and multiple PHYs result in large chips, adding the cost of the advanced
memory technology results in expensive solutions.

Our hypothesis is that by optimizing HE dataflow, we can capture on-chip reuse
with far less SRAM and simultaneously reduce the off-chip bandwidth
requirements. To understand the potential of optimizing dataflow, we will deep
dive into the _hybrid key-switching algorithm (HKS)_ [17]. HKS is the core
computation of HE and highly complex. The use of HKS in HE is widespread; it
is called after each rotation and homomorphic multiplication and is heavily
used in bootstrapping. For example, recent work has reported that a single HE
ResNet-20 inference takes 3,306 rotations [18], and prior research has further
shown that HKS dominates HE’s runtime [19, 16, 20], and can be up to 70% for
private neural inference [18].

A single HKS execution can involve hundreds of NTTs, hundreds of MBs of input
and output data, nearly 500MB of constant keys, and up to 1GB of intermediate
data. Thus, existing solutions to processing the workload effectively rely on
large on-chip SRAMs and high off-chip bandwidth.

To understand and optimize HKS, we propose three distinct dataflows named:
Max-Parallel (MP), Digit-Centric (DC), and Output-Centric (OC). Our key
insight is that with the OC dataflow, the intermediate state of HKS can be
significantly compressed while still maintaining high parallelism to utilize
computational units. With OC, we can significantly reduce the on-chip SRAM
requirements while maintaining high performance. To demonstrate the potential
of OC, we implement five parameterizations of HKS taken from recently
published work following each of the three presented dataflows on a recent
vector HE accelerator [14]. Using previously validated simulation
infrastructure, we rigorously evaluate the dataflows. First, we assume a large
on-chip SRAM (i.e., 512 MB) as in prior work and assume it can be used to
buffer all ($\mathbf{evks}$) on-chip while leaving a smaller fraction (i.e.,
32MB) for data (i.e., inputs and intermediates). We find that OC consistently
outperforms other dataflows and can deliver up to 4.16$\times$ speedup over MP
using the same bandwidth. Next, given that $\mathbf{evks}$ have no reuse
within HKS, we elect to stream them on-chip and reserve a fraction of off-chip
bandwidth for them. Here again OC performs well; by streaming $\mathbf{evks}$
we are able to reduce the on-chip SRAM requirements by 16$\times$ while still
having 3.3$\times$ less bandwidth compared to MP using 64GB/s bandwidth and
storing $\mathbf{evks}$ on-chip.

In summary our contributions are:

  1. 1.

We propose three different dataflows for HKS algorithm, named Max-Parallel,
Digit-Centric, and Output-Centric. Through our analysis we demonstrate how
strategically scheduling instructions and efficiently reusing loaded and
generated data by OC dataflow can lead to substantial off-chip bandwidth
saving.

  2. 2.

We evaluate two scenarios for handling $\mathbf{evks}$: streaming from off-
chip and on-chip storage with a larger memory. Streaming $\mathbf{evks}$
reduces SRAM area by 16$\times$ and saves 3.3$\times$ bandwidth.

  3. 3.

We evaluate the performance of dataflows across varing off-chip bandwidths and
computational throughput to understand the bandwidth-compute trade-off. We
find OC to be highly effective, matching naive MP HKS implementation with
significant bandwidth saving. Furthermore, increasing accelerator throughput
enhances performance even further.

##  II Background

In this section, we briefly introduce the CKKS HE scheme [5], including its
key parameters and operations, using terminology from ARK[16] and Castro [19]
when applicable. Unlike prior HE schemes, BGV [2] and BFV[3, 4], CKKS operates
on vectors of real or complex numbers, rather than integers. To perform these
operations, a vector message, $\mathbf{m}$, is first encoded into a plaintext
polynomial $R_{Q}=\mathbb{Z}_{Q}[X]/(X^{N}+1)$, represented as $[\mathtt{P}]$.
In essence, this is another vector of length $N$, with each element being an
integer no larger than Q. Depending on a problem’s complexity, the value of
$N$ typically ranges from $2^{11}$ to $2^{17}$, while $Q$ can range from
hundreds to thousands of bits. For a polynomial with $N$ coefficients, a
vector message must be of length $n\leq\nicefrac{{N}}{{2}}$.

Table. I: Relevant CKKS Parameters. Param. | Description
---|---
$\mathbf{m}$ | Message, a vector of real or complex numbers.
$[\\![\mathbf{m}]\\!]$, $[\\![\mathbf{m}]\\!]_{s}$ | Ciphertext encrypting the message, $\mathbf{m}$, under secret key $s$.
$N$ | Power-of-two polynomial ring degree.
$n$ | Length of the vector message, $n\leq\nicefrac{{N}}{{2}}$.
$Q$ | Initial polynomial modulus.
$P$ | Auxiliary modulus used in key-switching.
$L$ | Maximum multiplicative level of $[\\![\mathbf{m}]\\!]$.
$\ell$ | Current multiplicative level and remaining towers.
$K$ | Number of moduli/towers in $P$.
$q_{i}$ | Small moduli in RNS decomposition of $Q=\prod_{i=0}^{L}q_{i}$.
$p_{i}$ | Small moduli in RNS decomposition of $P=\prod_{i=0}^{K-1}p_{i}$.
$\mathtt{P}$ | Polynomial in $\mathbb{Z}[X]/(X^{N}+1)$.
$\mathcal{B_{\ell}}$, $\mathtt{[P]}_{\mathcal{B_{\ell}}}$ | The set of primes $\\{q_{0},q_{1},\ldots,q_{\ell}\\}$, $\mathtt{[P]}_{i\in\mathcal{B_{\ell}}}$.
$\mathcal{C}$, $\mathtt{[P]}_{\mathcal{C}}$ | The set of primes $\\{p_{0},p_{1},\ldots,p_{K-1}\\}$, $\mathtt{[P]}_{i\in\mathcal{C}}$.
$\mathcal{D_{\ell}}$, $\mathtt{[P]}_{\mathcal{D_{\ell}}}$ | The union of $\mathcal{B_{\ell}}\cup\mathcal{C}$, $\mathtt{[P]}_{i\in\mathcal{D_{\ell}}}$.
$dnum$ | Number of digits that $\mathtt{P}$ is decomposed into.
$\alpha$ | The number of towers in each digit, $\lceil\nicefrac{{(L+1)}}{{dnum}}\rceil$.
$\mathbf{evk}$ | Evaluation key used to convert $[\\![\mathbf{m}]\\!]_{s^{\prime}}$ to $[\\![\mathbf{m}]\\!]_{s}$.

A ciphertext, $[\\![\mathbf{m}]\\!]$, consists of a pair of polynomials,
$(C_{0},C_{1})$, where one polynomial contains the message with a small amount
of random noise added to it to ensure the security of the RWLE scheme. For
efficiency, ciphertexts are decomposed into an equivalent RNS representation
[21] consisting of many smaller, machine-word size moduli, $q_{i}$, such that
$R_{q_{0}}\times R_{q_{1}}\times\ldots\times R_{q_{\ell}}=R_{Q}$. Each small
moduli typically ranges from $36$ to $64$ bits [22], with larger moduli being
more robust to accumulated noise. We can think of the RNS representation as an
$N\times\ell$ matrix, with $\ell$ being the number of levels or towers in the
current ciphertext.

CKKS supports several arithmetic operations like addition and multiplications
between plaintext polynomials or ciphertexts. Additions and multiplications
are simple point-wise operations between coefficients and therefore require
the same number of levels in both operands. CKKS also supports rotations that
cyclically rotates elements within the vector message by a specified amount,
$r$. Notably, indexing vector elements is not efficiently supported and
therefore ciphertext rotations are the primary way of computing fully
connected layers and convolutions in neural networks.

Rotations and multiplications transform the ciphertext so that it cannot be
decrypted by the original secret key, $s$. As a result, an auxiliary process
known as “key-switching” is required, which is described in detail in the
following section. This operation involves many NTTs, which are analogous to
FFTs. A naive key-switching implementation can have poor operational intensity
and bottleneck many practical applications. For example, recent work shows
nearly 70% of execution time is spent performing key-switching operations for
ResNet-20 [18].

##  III Hybrid Key Switch

In this section, we will describe the Hybrid key-switching (HKS) algorithm, a
crucial step after performing ciphertext rotations and ciphertext-ciphertext
multiplications. In each case, the operation converts a ciphertext that is
encrypted by a secret key, $s$, into a new ciphertext only decryptable by some
new secret key, $s^{\prime}$. In general, to continue computation, the
ciphertext must be returned to a form decryptable by the original key, $s$.
The act of “switching” the keys from $s’$ back to $s$ is known as key-
switching. This is achieved by multiplying the ciphertext
$[\\![\mathbf{m}]\\!]_{s^{\prime}}$, with a special evaluation key,
$\mathbf{evk}$, which re-encrypts it from $s^{\prime}$ to $s$. However, this
process comes with an exceedingly high level of noise, which keeps growing
with consecutive use of the key-switching algorithm. Techniques proposed by
Fan [4] and later by Han [17] address this issue by performing the
$\mathbf{evk}$ multiplication at a higher modulus. Specifically, from Table I,
this multiplication is performed on polynomials, $[\mathtt{P}]_{\mathcal{D}}$
(modulo $PQ_{\ell}$), for some large integer $P$ rather than just $Q_{\ell}$.
While this substantially reduces noise growth, it adds complex NTTs and RNS
basis extensions both to convert polynomials from their current level,
$Q_{\ell}$ to $PQ_{\ell}$ (named ModUp), and then back to $Q_{\ell}$ (named
ModDown) after multiplication with $\mathbf{evk}$.

HKS [17] is a generalization of existing key-switching techniques that let the
user trade off the complexity of key-switching with the size of the
$\mathbf{evk}$. It has been widely adopted both in software implementations
[23, 24] and in recent HE accelerators [13, 15, 16, 20] yet the aforementioned
trade off, especially in hardware, is still not well understood.

###  III-A Overview

Broadly, HKS is composed of two phases that we denote as ModUp and ModDown,
introduced above. The ModUp phase can be broken down into five consecutive
stages, P1-P5 and the ModDown phase into four, P1-P4. We use terms such as
ModDown_Pi to refer to the i’th stage of the ModDown phase. These stages can
be seen in Figure 2. We loosely adopt this terminology from Han [17] to
intuitively represent that the first phase of HKS is geared towards extending
the RNS base from $Q_{\ell}$ to $PQ_{\ell}$, whereas the second phase is
focused on reducing the modulus back from $PQ_{\ell}$ to $Q_{\ell}$.

We consider an input polynomial as a matrix of size $(N\times\ell)$ which
changes shape throughout the key-switching process, depending on the chosen
parameters. Figure 2 represents the HKS dataflow for a specific parameter set,
however, the core stages of HKS remain the same across different parameter
choices. In Section V-D, we explore a wider range of parameter sets and note
that the insights we gain from analyzing this specific case remain applicable.
We highlight a single tower of the input polynomial in red in Figure 2, with
the widths of subsequent stages accurately reflecting the change in sizes of
the original $(N\times\ell)$ input polynomial. For example, a preliminary step
in HKS decomposes the input polynomial into $dnum$ digits, each of size
roughly, $\alpha=\lceil\nicefrac{{(L+1)}}{{dnum}}\rceil$, reshaping the input
matrix to $(N\times\ell)$. In Figure 2, for which $dnum=3$, the input
polynomial is decomposed into three different colored digits, with each digit
being $11$ towers wide.

Figure. 1: Hybrid key-switching dataflow diagram for parameters, $\ell=33,\
\alpha=11,\ dnum=3.$

Figure. 2: High-level ModUp timing diagrams for the three proposed dataflows.

###  III-B ModUp

$\mathbf{(P1)}\hskip 1.99997pt\textit{INTT}$: Following the initial digit
decomposition step, each tower must undergo an INTT which converts the
polynomial from the evaluation domain to the coefficient domain. This
conversion has a complexity of $\mathcal{O}(N\log N)$, similar to the FFT, and
is applied separately to all $\ell$ towers.

$\mathbf{(P2)}\hskip 1.99997pt\textit{BConv}$: Each digit, now in the
coefficient domain, goes through a basis conversion to change the set of
primes representing a polynomial. The number of towers is extended from
$\alpha$ to $\beta$, where $\beta=\ell+K-\alpha$, and K is the number of
towers in moduli $P$. The number of modular multiplications in this stage is
roughly $N\times\alpha\times\beta$ for each of the $dnum$ digits.

$\mathbf{(P3)}\hskip 1.99997pt\textit{NTT}$: After basis extension, the digits
once again return to the evaluation domain through the NTT. The computational
complexity, similar to the INTT stage, is$\mathcal{O}(N\log N)$, performed
independently for $\beta\times dnum$ towers. This output is concatenated with
the original digit to form a new polynomial modulo $PQ_{\ell}$. Our new matrix
is now of size $dnum\times N\times(\ell+K)$.

$\mathbf{(P4)}\hskip 1.99997pt\textit{Apply Key}$: Now that the polynomial is
in a larger modulus, we can multiply it with $\mathbf{evk}$ with negligible
added error. This is a point-wise operation with the evaluation key being of
shape $dnum\times 2\times N\times(\ell+K)$. In practice, key sizes typically
range from $100$MB to $400$MB (see Table II).

$\mathbf{(P5)}\hskip 1.99997pt\textit{Reduce}$: The last stage in the ModUp
phase sums each digit’s $\mathbf{evk}$ multiplication into one final matrix of
size $2\times N\times(\ell+K)$.

###  III-C ModDown

We now have two polynomials, each of size $N\times(\ell+K)$ that must be
reduced to their original size of $N\times\ell$ for further computation. This
process begins by taking the last $K$ towers of each polynomial and performing
a similar series of $\textit{INTT}\rightarrow\textit{BConv}\rightarrow NTT$
operations. Here, each BConv operation converts the number of towers from $K$
to $\ell$. The runtime complexity of these three stages is $2K\times N\log N$,
$2N\times K\times\ell$, and $2\ell\times N\log N$, respectively. These
polynomials go through one final scalar-tower multiplication and summation to
finish out the key-switching process.

##  IV HKS Dataflows

We propose three distinct dataflows for the HKS algorithm: Max-Parallel (MP),
Digit-Centric (DC), and Output-Centric (OC). These dataflows differ in their
sequence of instructions, reusing the loaded and computed data, intermediate
data generation, and off-chip memory interaction. Assuming unlimited on-chip
memory, the performance of these dataflows would be identical, as all inputs
and intermediate data can be stored on-chip. Our goal is to show by changing
the sequence of operations we can have the same performance using a smaller
on-chip memory. In this section, we provide a detailed explanation of the
principles and strategies behind each dataflow. Later we evaluate their
performance by varying off-chip bandwidth and computational throughput. Our
analysis highlights how dataflow off-chip memory interaction will help to save
memory and bandwidth resources.

###  IV-A Max-Parallel Dataflow (MP)

This dataflow is designed to prioritize kernel parallelism at all costs. Each
tower is loaded onto the on-chip memory for a single operation, and each
operation is executed on all input towers sequentially before processing the
next step. However, this approach comes with a drawback. Specifically, in
ModUp_P2 and ModDown_P2, the generated intermediate data after BConv becomes
extremely large, even though only one of the BConv output towers is required
for calculating each output tower in the ModUp and ModDown stages. For BTS3,
at least 675MB on-chip memory is required to prevent excessive load and stores
to the off-chip memory.

###  IV-B Digit-Centric Dataflow (DC)

This dataflow adopts a “one-digit-at-a-time” approach, where each digit is
loaded onto the chip, and all possible calculations involving that digit are
performed before moving on to the next digit. As illustrated in Figure 2(b),
all P1 to P5 calculations for a single digit are done in sequence, maximizing
data reuse. However, BConv still expands the digit from $\alpha$ to $\beta$
towers, generating a partial product of the output that can either be stored
on-chip for later reduction to save bandwidth or sent off-chip to minimize on-
chip memory requirement. Once ModUp is completed, ModDown follows the same
approach. For BTS3, which is the largest benchmark, DC requires 255MB of on-
chip memory, which is 62% less compared to MP dataflow.

###  IV-C Output-Centric Dataflow (OC)

Finally, we propose Output-Centric (OC) dataflow, which is optimized for data
movement and on-chip storage, leveraging insights from the first two
solutions. OC focuses on computing one output tower at a time, efficiently
utilizing on-chip resources. In this dataflow, the ModUp stage has two
sections: Section1 computes output towers in modulo $Q$, with $dnum-1$ digits
going through ModUp_P2 & ModUp_P3 step and one tower from the last digit
bypassed through ModUp_P2 & ModUp_P3. Section2 computes output towers in mod
$P$, requiring all digits to pass through ModUp_P2 & ModUp_P3 for a single
output calculation.

In both sections, the computation is optimized to minimize the on-chip memory
requirement. Since only one output tower is calculated at a time, the entire
computation of ModUp_P2 & ModUp_P5 is unnecessary. Instead, a single ModUp_P2
output tower is calculated and multiplied with the $\mathbf{evk}$, reducing
memory requirements and off-chip data communication. Moreover, for each
partial sum in ModUp_P5, only one partial tower is calculated at a time,
allowing them to be aggregated before returning to off-chip memory. In
Section2, where all digits are required for calculating a single output tower,
we have used the following strategy to manage the on-chip memory limitation.
Since the INTT of the first $dnum-1$ digits is already on-chip, so we compute
the partial sum with those digits and then the final digit is loaded to
compute the last partial sum and the final output tower. This approach reduces
off-chip memory interaction and on-chip memory requirements.

ModDown has the same approach as ModUp. All towers related to
$[\mathtt{P}]_{\mathcal{C}}$ are loaded on-chip, but by calculating one output
tower at a time, the expansion of ModUp_P2 is eliminated, increasing the
efficiency of HKS implementation on a small on-chip memory.

##  V Methodology

This section provides an overview of our dataflow implementations. We will
start by describing the hardware architecture, and then explain the benchmarks
used for performance evaluation. Finally, we will introduce the software
framework employed for generating HKS instructions for different benchmarks
and dataflows.

###  V-A Hardware Simulation

We implement the dataflows introduced in Section V-A for the RPU [14],
alongside an extensive design space exploration in Section VI. The RPU is a
vector processor supporting Ring-Learning-With-Errors (RLWE)-based algorithms,
including HE, with 64, 64-bit vector registers, 64, 64-bit scalar registers, a
32MB vector data memory, and a 1MB scalar data memory, operating at 1.7GHz.
These exist alongside an additional modulus register file, which stores the
working set of RNS moduli. In our work, the RPU uses 128 lanes. This marks a
$2\times$ decrease in the size of RNS moduli from the original RPU paper[14],
which entailed doubling both the number of vector lanes and vector length to
maintain high throughput and keep compute units occupied. We also modified the
RPU’s associated instruction set architecture (ISA), $\mathtt{B512}$, to
support $1K$ vector length and will refer to it as $\mathtt{B1K}$.
$\mathtt{B1K}$ consists of $28$ instructions ranging from general purpose
point-wise arithmetic operations to HE-specific shuffle instructions for
(i)NTT kernels. Figure 3 presents the RPU microarchitecture, which consists of
a front-end to handle instruction fetching, decoding, and control logic, and a
backend that contains the high-performance large arithmetic word engines
(HPLEs) to efficiently perform our HE-tailored vector operations. To achieve
high performance and mask data movement by computation, the RPU includes three
distinct queues to fetch independent instructions in parallel. Additionally,
the RPU was implemented and verified on a Palladium system [25].

Figure. 3: Microarchitecture of the RPU.

###  V-B Benchmark Selection

We use the RNS variant of HKS, as presented in Han[17], which optimized the
key-switching implementation by leveraging RNS decomposition for enhanced
efficiency. The security of HE is defined by $\lambda$, which is a function of
$\frac{N}{logQP}$. As mentioned in Cheon[26], 128-bit security is required to
defend against dual attacks and to be able to extract the real data from the
encrypted output. BTS [15] simulates the multiplication time per slot by
sweeping $N$, $L$, and $\lambda$ to identify the optimal configurations for
128-bit security, and refers to these points as BTS1, BTS2, and BTS3. ARK [16]
uses a smaller polynomial degree, $2^{16}$, while increasing the number of
digits to 4 to satisfy the 128-bit security. Following recent studies [15, 16,
27, 20], we also target 128-bit security and use the latest work
parameterization [15, 16], and DPRIVE [28] to evaluate the performance of our
dataflows. Table II summarizes the parameters of the benchmarks used in our
research.

Table. II: Parameters satisfying 128-bit security. Benchmark | N | $k_{l}$ | $k_{p}$ | dnum | $\alpha$ | evk Size | Temp data
---|---|---|---|---|---|---|---
BTS1 |  217 | 28 | 28 | 1 | 28 | 112MB | 196MB
BTS2 |  217 | 40 | 20 | 2 | 20 | 240MB | 400MB
BTS3 |  217 | 45 | 15 | 3 | 15 | 360MB | 585MB
ARK |  216 | 24 | 6 | 4 | 6 | 120MB | 192MB
DPRIVE |  216 | 26 | 7 | 3 | 9 | 99MB | 163MB

###  V-C Software Framework

To generate HKS code for different benchmarks and dataflows, we break down the
HKS algorithm into steps highlighted in Figure 2, and generate instructions
for each step independently, based on the $\mathtt{B1K}$ ISA. Our simulation
framework includes two distinct tasks, namely memory tasks and compute tasks.
Memory tasks handle data transfer between off-chip and on-chip, while compute
tasks correspond to steps in the HKS algorithm, executed on the RPU [14]. The
challenge of our approach lies in effectively managing the task dependencies.
Each task may rely on one or more compute and memory tasks, which must
complete their execution before the dependent task can proceed. These
dependencies stem from a variety of reasons, such as the need to fetch data
from off-chip memory or to create space for subsequent operations using a
memory task. Moreover, some tasks depend on data generated by a compute task
as part of their input. These dependencies may vary based on the on-chip
memory, the specific dataflow, and the benchmarks used. Using the software
framework, we generate instructions for each configuration.

###  V-D Dataflow Simulation

We have implemented and analyzed all given benchmarks in Table II for each
dataflow described in Section IV. In Section IV, we noted that with unlimited
on-chip memory, the performance of the dataflows tends to be nearly identical.
However, with limited on-chip memory, this would no longer be true because the
inputs and intermediate data cannot all fit on the chip at once. This makes
the sequence of operations and the data movement between on and off-chip
memory crucial. When dealing with small on-chip memory and increased
intermediate data, the performance of DC may become close to MP due to more
interactions with off-chip memory.

Our goal is to keep as much data as we can on-chip to reduce interactions with
off-chip memory. In general, the INTT calculations will be in-place or out-of-
place, depending on the on-chip memory. In ModUp_P5, if on-chip space is
sufficient, we prioritize storing towers related to $[P_{0}]_{\mathcal{B}}$
and $[P_{1}]_{\mathcal{B}}$, for optimized on-chip memory use and reduced off-
chip memory access during subsequent computations. Additionally, _ModDown_P2_
and _ModDown_P3_ will begin computations from towers that are already on-chip.

Table. III: Intermediate off-chip loads and stores (MB).  Benchmark | MP (MB) | DC (MB) | OC (MB)
---|---|---|---
BTS1 | 404 | 404 | 224
BTS2 | 992 | 918 | 356
BTS3 | 1355 | 1286 | 675
ARK | 276 | 200 | 24
DPRIVE | 227 | 198 | 32

##  VI Evaluation

Figure. 4: Quantifying latency reduction for MP, DC, and OC by increasing DRAM
bandwidth for the five given benchmarks.

In this section, we evaluate HKS performance following the three dataflows
described above, using five benchmarks listed in Table I, from recent papers,
BTS [15] and ARK [16], and DPRIVE [28]. The evaluation is done using the RPU
[14] as the target hardware platform of our implementations, including the
modifications mentioned in Section V-A. While the performance results are
specific to the RPU, the general insights and takeaways from the optimizations
are broadly applicable. As mentioned earlier, one of the challenges in HKS is
properly handling the large amounts of input, intermediate, and key data. In
fact, prior work [15, 16, 29] has found that HE is memory bound. We re-examine
this performance limitation considering the different proposed dataflows.
First, we assume a large 512MB on-chip SRAM, with 32MB allocated for data and
the rest for $\mathbf{evks}$. We sweep bandwidth for all three dataflows,
showing the significant performance benefits of carefully arranging operations
using the OC dataflow given a fixed bandwidth. Next, we eliminate the on-chip
SRAM devoted to storing $\mathbf{evks}$, instead streaming them on-chip, as
they are used only once per HKS. This approach can save substantial on-chip
SRAM (up to $16\times$) with a maximum of $2.38\times$ slowdown due to the
increased off-chip data movement.

Finally, we increase the computational throughput of the RPU to understand how
the behavior of our proposed dataflow balances the compute-to-communication
ratio, and show how it compares to prior accelerators.

Table. IV: OC bandwidth (BW; in GB/s) required to achieve the same performance as MP using 64GB/s BW. Speedup reports the performance improvement OC achieves over MP at the listed bandwidth (BW). Benchmark | BW | OC(ms) | MP(ms) | Saved BW | Speedup
---|---|---|---|---|---
BTS1 | 25.60 | 30.08 | 39.13 | 2.50x | 1.30x
BTS2 | 12.80 | 43.24 | 104.85 | 5.00x | 2.42x
BTS3 | 32.00 | 51.87 | 71.50 | 2.00x | 1.37x
ARK | 8.00 | 9.01 | 37.54 | 8.00x | 4.16x
DPRIVE | 12.80 | 7.81 | 23.15 | 5.00x | 2.96x

###  VI-A Dataflow Comparison

Figure 4 compares different HKS implementation runtimes across different
dataflows for all benchmarks. Benchmarks are categorized into three groups:
ARK and DPRIVE (small, $2^{16}$ polynomial degree); BTS1 (single digit, lacks
ModUp_Reduce), and BTS2 and BTS3 (large, $2^{17}$ with three and four digits).
We sweep the off-chip bandwidth from 8GB/s to 64GB/s, extending to 1TB/s for
ARK and BTS3, representing the smallest and largest benchmarks, respectively.
This bandwidth range includes DDR4 (8GB/s to 25.6GB/s), DDR5 (32GB/s to
64GB/s), HBM2 (64GB/s to 410GB/s), and HBM3 (up to 1TB/s). In all benchmarks,
the performance benefit of OC is large at low bandwidth and decreases as
bandwidth increases. This is the result of RPU becoming compute bound,
reducing the impact of off-chip communication. With OC, we show that by
optimizing the dataflow we can achieve more performance with less bandwidth.
Below we will delve into a detailed comparison between OC, MP, and DC runtimes
when OC performance saturates, along with the corresponding bandwidth at which
OC matches MP performance with 64GB/s (DDR5), demonstrating the improved
bandwidth efficiency.

####  VI-A1 DPRIVE & ARK

Figure 4(a) and (d), demonstrate a significant improvement in HKS runtime by
implementing the OC dataflow. Table III presents data movement for off-chip
loading and storing, excluding constant $\mathbf{evks}$ and input data. For
DPRIVE, OC reduces data movement by up to 7$\times$, making it compute-bound
with lower off-chip bandwidth. In Figure 4(a), DPRIVE’s HKS runtime begins
saturating at 19.2GB/s and outperforms DC, and MP by 2.1$\times$ and
2.5$\times$, respectively. Before becoming compute bound, the RPU will be idle
for part of its execution time, waiting for dependent memory tasks to be
completed. With 19.2GB/s off-chip bandwidth, OC keeps the RPU idle for 4.8% of
its execution time, while DC and MP reach 54.1% and 62.3%, respectively. The
horizontal line in Figure 4(a) shows that OC can match MP and DC runtimes with
64GB/s bandwidth at 12.8GB/s off-chip bandwidth, resulting in a 5$\times$
bandwidth saving, emphasizing OC’s benefits when off-chip bandwidth is a
concern.

Similarly, for ARK, OC runtime saturates at 19.2GB/s, outperforming DC and MP
by 2.1$\times$ and 3.0$\times$ at this point. With 19.2GB/s, the RPU remains
idle for 5.5% of the runtime, which is 9.3$\times$ less than DC and
12.2$\times$ less than MP. Using OC with 8GB/s and 12.8GB/s off-chip bandwidth
achieves the same performance as MP and DC with 64GB/s off-chip bandwidth
(DDR5), resulting in 8$\times$ and 5$\times$ bandwidth savings, respectively.

####  VI-A2 BTS1

As mentioned above, for BTS1 with one digit, MP and DC have the same
implementation. In Figure 4(b), OC matches MP’s performance with 64GB/s, by
having 25.6GB/s off-chip bandwidth, saving 2.5$\times$ off-chip bandwidth. At
this bandwidth, OC is 1.3$\times$ faster than MP and 2.1$\times$ less idle.

####  VI-A3 BTS2 & BTS3

By analyzing BTS2 and BTS3, we observe that as the size of the benchmark
increases, DC and MP converge due to data expansion in the BConv operation and
an increased number of polynomial additions for reduction. This can also be
seen in Table III, which quantifies the (smaller) gap between off-chip data
movement in MP and DC for BTS2 and BTS3. Figure 4 shows that for BTS2, at
approximately 54.7GB/s, OC starts saturating and becomes compute bound. At
this point, OC is 1.3$\times$ and 1.4$\times$ faster than DC and MP,
respectively, with the RPU being 17.7$\times$ less idle, as DC and MP are both
bandwidth limited. Additionally, in Figure 4(c), OC’s runtime with less than
12.8GB/s off-chip bandwidth matches that of MP and DC with 64GB/s bandwidth,
saving 5$\times$ bandwidth.

For BTS3, the performance gap between OC and the other two dataflows decreases
as the RPU becomes more compute bound. As shown in Figure 4(d), for BTS3, the
runtime starts saturating at 128GB/s. Despite the decreasing gap between OC
and MP/DC, due to the increased input and intermediate data, OC still
outperforms them. With a 32GB/s bandwidth, OC is 1.3$\times$ faster and
1.7$\times$ less idle than MP and DC, while also matching MP’s runtime at
64GB/s, resulting in a 2$\times$ bandwidth saving.

####  VI-A4 Comparison Across Benchmarks

Table IV summarizes the previous discussion. The “ _BW_ ” column indicates the
bandwidth where OC matches MP’s performance at 64MB/s off-chip bandwidth,
while “ _Saved BW_ ” denotes the bandwidth savings achieved with OC

Most of the recent performance optimization solutions such as RNS-based HKS
[17] which is used in this paper, require a higher bandwidth; Therefore
focusing on reducing off-chip bandwidth is crucial. Implementing OC dataflow,
results in 1.37$\times$ to 4.16$\times$ speedup over a simple MP
implementation and saves 2$\times$ to 8$\times$ off-chip bandwidth. HKS
runtime for OC and MP dataflow has also been reported for reference. With OC,
we achieve up to 16$\times$ more compute-to-bandwidth compared to BTS [15]
which uses 2048 functional units and a 1TB/s off-chip bandwidth.

###  VI-B Streaming Evaluation Keys

Figure. 5: HKS runtime for OC with $\mathbf{evks}$ streamed from off-chip vs.
$\mathbf{evks}$ stored on-chip, and the equivalent bandwidth. Figure. 6:
Evaluating HKS runtimes for OC (a), DC (b), and MP (c) at different MODOPS for
the ARK benchmark.

Looking into the computations of HKS, the input data and intermediate data
(BConv output) are reused for calculating multiple output towers, making it
advantageous to keep them on-chip to reduce off-chip communication. On the
other hand, the evks for each HKS are large, ranging from 99MB for DPRIVE to
360MB for BTS3, and only used once per each HKS. Consequently, it can be more
practical and area efficient to store these large $\mathbf{evks}$ off-chip and
load them on-chip in a streaming fashion. To study the effects of streaming
$\mathbf{evks}$, we reserve a fraction of off-chip bandwidth and dedicate it
to loading the $\mathbf{evks}$ on-chip. To determine the required bandwidth
allocation for $\mathbf{evks}$, we calculate the ratio of the number of
$\mathbf{evks}$ to the number of loaded/stored data.

Figure 5 shows the slowdown for the OC dataflow of each benchmark when
streaming $\mathbf{evks}$ from off-chip instead of storing them on-chip. In
this case, we only have 32MB of on-chip memory to store data and capture
reuse. The results are shown for two bandwidths per benchmark, as indicated by
the clustered bars (e.g., 8 and 23.4 for ARK). The first bandwidth corresponds
to the bandwidth specified in Table IV, where the performance is equal to MP
64GB/s implementation, assuming $\mathbf{evks}$ to be on-chip. The second
bandwidth indicates the required bandwidth to attain equivalent performance
when streaming the $\mathbf{evks}$ from off-chip. The slowdown for DPRIVE is
less than ARK, because of the smaller ratio of $\mathbf{evks}$ to the
loaded/stored data (0.66 for ARK and 0.5 for DPRIVE). Among the large
benchmarks (BTS1, BTS2, and BTS3), BTS2 has the most slowdown, 1.33$\times$,
since that ratio is more than other benchmarks. As shown in Figure 5, using OC
dataflow, by 1.7$\times$ (for BTS3) to 2.9$\times$ (for ARK) more bandwidth we
can achieve the same performance as storing the keys on-chip while saving
16$\times$ on-chip memory. However, compared with the initial MP dataflow with
64GB/s and $\mathbf{evks}$ on-chip, by storing $\mathbf{evks}$ off-chip and
using OC dataflow, BTS3 still achieves the same performance and saves
1.1$\times$ bandwidth and 16$\times$ on-chip memory. In conclusion, storing
$\mathbf{evks}$ off-chip saves 16$\times$ on-chip memory and by implementing
OC dataflow, we can save up to 3.3$\times$ bandwidth to have the same
performance as MP 64GB/s with $\mathbf{evks}$ on-chip. Additionally, storing
keys off-chip and keeping 32MB on-chip memory for data, decreases the RPU area
from $521.85mm^{2}$ to $41.85mm^{2}$.

###  VI-C Sensitivity Studies

In the last section, we evaluated the three proposed dataflows and showed how
data reuse enabled the OC optimization to significantly improve the runtime of
HKS, saving considerable bandwidth even when streaming in $\mathbf{evks}$. In
this section we conduct a sensitivity study to investigate how the performance
of HKS with OC is affected as we increase both the bandwidth, ranging up to
1TB/s (HBM3), and the computational throughput up to 16$\times$ more. The goal
of this section is to explore the scalability of OC under various bandwidths
and computational throughputs. We refer to computational throughput as MODOPS,
for Modular Operations per Second.

####  VI-C1 Bandwidth Study

In Figure 4(d) and (e) we increase the off-chip bandwidth beyond 64GB/s up to
1TB/s to study how scaling bandwidth affects HKS runtime under the proposed
dataflows for the ARK and BTS3 benchmarks. For both ARK and BTS3, the benefit
from OC compared to the other two dataflows diminishes at bandwidths larger
than 256GB/s. This is because as we increase the bandwidth, the RPU becomes
compute bound and interactions with off-chip memory are no longer a challenge.
According to Figure 4(e), we observe that with 25.6GB/s off-chip bandwidth and
implementing BTS3 with OC dataflow, we can save 40$\times$ bandwidth by only
becoming 1.4$\times$ slower than 1TB/s bandwidth. In addition, at this
specific bandwidth, OC is also 1.4$\times$ faster than MP.

Based on Figure 4(d), for ARK with OC dataflow, HKS runtime remains the same
after reaching a 128GB/s bandwidth. At this point, the RPU becomes compute
bound, waiting for data to arrive from off-chip memory or to be stored back,
thereby limiting further performance gain from increasing bandwidth. By using
8GB/s off-chip bandwidth and utilizing OC implementation, we can save
128$\times$ bandwidth by being 1.6$\times$ slower compared to OC with 1TB/s.
As mentioned earlier, at this specific point OC is also 4.1$\times$ faster
than MP.

####  VI-C2 Computational Throughput Study

The RPU design includes 128 lanes, which is 16$\times$ less functional units
compared to BTS. To enhance the HKS runtime, which benefits from parallel
computation where the calculation of each output tower is entirely independent
of others, we adopt multiple RPUs in parallel. We simulate a multi-RPU design
by increasing RPU’s MODOPS (2$\times$, 4$\times$, 8$\times$, and 16$\times$)
and evaluate the HKS performance using OC, DC, and MP for both ARK and BTS3
benchmarks, representing the smallest and largest benchmarks, respectively.
Figure 6 shows how varying MODOPS will impact different dataflows at different
bandwidths for ARK. In these figures, we have assumed the $\mathbf{evks}$ to
be stored on-chip. Figure 7 and 8 compares OC performance for different MODOPS
while $\mathbf{evks}$ are stored off-chip.

Based on Figure 6, for low bandwidths, the HKS runtime for different MODOPS
are almost the same, as they are all bandwidth limited, and do not benefit
from increasing the computational throughput. However, as the bandwidth
increases, higher MODOPS start to become compute bound, resulting in an
increasing gap between the HKS runtime at different MODOPS. According to
Figure 6, this gap is much more in OC, compared to DC or MP, because of OC
being less bandwidth bound.

In addition, the difference between OC and DC or MP increases as the MODOPS
also increases, emphasizing the importance of OC implementation for higher
MODOPS. DC dataflow requires higher MODOPS compared to OC for equivalent
performance. For example, to match OC’s performance at 64GB/s and 4$\times$
MODOPS, DC requires 1TB/s bandwidth or 256GB/s bandwidth with 8$\times$ more
MODOPS, resulting in 16$\times$ or 8$\times$ higher bandwidth$\times$MODOPS
than OC, respectively. The trend for MP is the same as DC, with less gap
between different MODOPS.

Figure 7, represents the HKS runtime for ARK’s OC implementation with
1$\times$ to 8$\times$ more MODOPS. Unlike Figure 6, this plot assumes
$\mathbf{evks}$ to be stored off-chip. Compared to Figure 6(a), the gap
between different MODOPS is much less due to the implementation being more
bandwidth limited. Since ARK starts to become completely compute bound at
256GB/s, we chose that as the base bandwidth and found the equivalent
bandwidth for other MODOPS based on 256GB/s. With 2$\times$ more MODOPS and
45.62GB/s off-chip bandwidth, the execution time would be equal to 256GB/s and
1$\times$ MODOPS, saving 5.6$\times$ the bandwidth.

Figure. 7: Evaluating ARK’s OC implementation while streaming evks and varying
MODOPS.

Figure 8 shows the impact of MODOPS on BTS3 with the OC dataflow and
$\mathbf{evks}$ stored off-chip. To have the same runtime as 1$\times$ MODOPS
and 1TB/s bandwidth, the MODOPS can be increased up to2$\times$, 4$\times$,
8$\times$, where the bandwidth is equal to 45.62GB/s, 32GB/s, and 32GB/s,
respectively, saving 22.4$\times$, 32$\times$, 32$\times$ bandwidth.

Figure. 8: Evaluating BTS3’s OC implementation while streaminf evks and
varying MODOPS.

##  VII Related Work

High-Performance CPU Implementations: Many software libraries exist that
support HE [7, 6, 8, 5]. Notably, Lattigo [7], OpenFHE [6], and HEAAN [5],
support CKKS bootstrapping and FHE. However, due to limited computational
power, some applications like deep neural network inference, remain
impractical on pure CPU implementations. For instance, state-of-the-art ResNet
models [18, 30, 31] can take upwards of one hour per inference, limiting their
applicability to infrequent, low arrival rate applications [32, 33].

FHE Compilers: Many works have focused on FHE compiler development to simplify
FHE application development [34, 35, 36, 37, 38]. Eva [34] is a novel tool for
CKKS-based vector arithmetic using SEAL [8] library. It automates batch
processing, parameter selection and ciphertext management, and is an extension
of CHET [35], where both mainly focus on neural network inference. While FHE
compilers focus on mapping plaintext programs to FHE, our work optimizes
mapping FHE workloads onto hardware, emphasizing data reuse and minimizing
off-chip communication.
GPU/FPGA Acceleration: GPUs offer promising opportunities for performance gain
given their large number of parallel compute units and high off-chip
bandwidth. Previous studies explore GPU acceleration of HE operations [39, 12,
40, 41, 42]. Jung [41] was the first GPU implementation to support CKKS FHE,
which suggests optimizations like kernel fusing to reduce on-chip memory
requirements. Still, the lack of native modular arithmetic support and limited
on-chip memory yields subpar performance relative to modern ASIC solutions
[13, 15, 16, 22].

An alternative approach is to employ the use of FPGAs [43, 20, 44, 45]. While
FPGAs may not provide the same level of performance as ASIC solutions, their
reprogrammability offers a significant advantage given that FHE algorithms
continue to evolve at a rapid pace. Poseidon [43] was the first FPGA-based
accelerator targeting FHE CKKS. Most recently, FAB [20] proposes several
dataflow optimizations, alongside an FPGA implementation, geared towards
increasing on-chip data reuse and minimizing unnecessary DRAM accesses.
ASIC Acceleration: Cheetah [46] was the first to present a large-scale ASIC
with custom logic and show that the overheads of HE could be overcome with
hardware acceleration. $\mathtt{F1}$ [10] presented a programmable ASIC
accelerator for FHE. Notably, $\mathtt{F1}$ is tailored to small parameter
sets and has limited bootstrapping support, making it unable to efficiently
accelerate deep neural network computations. Since then, many works [13, 15,
16, 22] have proposed ASIC solutions targeting bootstrapping and FHE.
CraterLake [13] and BTS [15] were the first ASIC accelerators to support
bootstrapping, however they employ a large number of compute units that were
often underutilized despite allocating 1TB of off-chip bandwidth. Later, ARK
[16] proposed a minimal key-switching strategy to address this memory
bottleneck problem, yet still required a large 512MB on-chip scratchpad.
Recently, SHARP [22] characterized the effect of smaller moduli size on neural
network accuracy and found it was possible to utilize much smaller 36-bit RNS
moduli. This, in turn, reduced the size of compute units, on-chip memory
requirements, and off-chip bandwidth pressure.

##  VIII Conclusion

In this paper, we propose three distinct approaches for implementing the
hybrid key-switching algorithm that differ in the sequence of instructions and
data reuse strategies. Through our evaluations using the RPU accelerator with
various benchmarks, our novel dataflow, Output-Centric, achieves up to
4.16$\times$ speedup over a naive Max-Parallel implementation of HKS.
Additionally, we can save 16$\times$ of on-chip SRAM by storing the
$\mathbf{evks}$ off-chip. Here, OC achieves the same performance with
3.3$\times$ less bandwidth compared to MP using 64GB/s bandwidth and storing
$\mathbf{evks}$ on-chip.

## Acknowledgment

This work was supported in part by Graduate Assistance in Areas of National
Need (GAAN). 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 also express our gratitude to Duality, especially David Bruce
Cousins, Ahmad Al Badawi, and Yuriy Polyakov as well as Andrew G. Schmidt from
AMD for their valuable insights and support. The views, opinions, and/or
findings expressed are those of the authors and do not necessarily reflect the
views of sponsors.

## References

  * [1] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 169–178, 2009.
  * [2] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic encryption without bootstrapping,” ACM Transactions on Computation Theory (TOCT), vol. 6, no. 3, pp. 1–36, 2014.
  * [3] Z. Brakerski, “Fully homomorphic encryption without modulus switching from classical gapsvp,” in Annual Cryptology Conference, pp. 868–886, Springer, 2012.
  * [4] J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” Cryptology ePrint Archive, 2012.
  * [5] 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, pp. 409–437, Springer, 2017.
  * [6] 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.
  * [7] “Lattigo 1.3.0.” Online: http://github.com/ldsec/lattigo, Dec. 2019.  EPFL-LDS.
  * [8] “Microsoft SEAL (release 4.1).” https://github.com/Microsoft/SEAL, Jan. 2023.  Microsoft Research, Redmond, WA.
  * [9] 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), pp. 26–39, IEEE, 2021.
  * [10] N. Samardzic, A. Feldmann, A. Krastev, S. Devadas, R. Dreslinski, C. Peikert, and D. Sanchez, “F1: A fast and programmable accelerator for fully homomorphic encryption,” in MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, pp. 238–252, 2021.
  * [11] A. Aikata, A. C. Mert, S. Kwon, M. Deryabin, and S. S. Roy, “Reed: Chiplet-based scalable hardware accelerator for fully homomorphic encryption,” arXiv preprint arXiv:2308.02885, 2023.
  * [12] S. Fan, Z. Wang, W. Xu, R. Hou, D. Meng, and M. Zhang, “Tensorfhe: Achieving practical computation on encrypted data using gpgpu,” 2022.
  * [13] 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, pp. 173–187, 2022.
  * [14] D. Soni, N. Neda, N. Zhang, B. Reynwar, H. Gamil, B. Heyman, M. Nabeel, A. Al Badawi, Y. Polyakov, K. Canida, et al., “Rpu: The ring processing unit,” in 2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pp. 272–282, IEEE, 2023.
  * [15] S. Kim, J. Kim, M. J. Kim, W. Jung, J. Kim, M. Rhu, and J. H. Ahn, “Bts: An accelerator for bootstrappable fully homomorphic encryption,” in Proceedings of the 49th Annual International Symposium on Computer Architecture, pp. 711–725, 2022.
  * [16] J. Kim, G. Lee, S. Kim, G. Sohn, M. Rhu, J. Kim, and J. H. Ahn, “Ark: Fully homomorphic encryption accelerator with runtime data generation and inter-operation key reuse,” in 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO), pp. 1237–1254, IEEE, 2022.
  * [17] K. Han and D. Ki, “Better bootstrapping for approximate homomorphic encryption,” in Cryptographers’ Track at the RSA Conference, pp. 364–390, Springer, 2020.
  * [18] 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 (K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, eds.), vol. 162 of Proceedings of Machine Learning Research, pp. 12403–12422, PMLR, 17–23 Jul 2022.
  * [19] L. de Castro, R. Agrawal, R. Yazicigil, A. Chandrakasan, V. Vaikuntanathan, C. Juvekar, and A. Joshi, “Does fully homomorphic encryption need compute acceleration?,” 2021.
  * [20] R. Agrawal, L. de Castro, G. Yang, C. Juvekar, R. Yazicigil, A. Chandrakasan, V. Vaikuntanathan, and A. Joshi, “Fab: An fpga-based accelerator for bootstrappable fully homomorphic encryption,” in 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pp. 882–895, 2023.
  * [21] J. H. Cheon, K. Han, A. Kim, M. Kim, and Y. Song, “A full rns variant of approximate homomorphic encryption,” in Selected Areas in Cryptography–SAC 2018: 25th International Conference, Calgary, AB, Canada, August 15–17, 2018, Revised Selected Papers 25, pp. 347–368, Springer, 2019.
  * [22] 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, ISCA ’23, (New York, NY, USA), Association for Computing Machinery, 2023.
  * [23] C. V. Mouchet, J.-P. Bossuat, J. R. Troncoso-Pastoriza, and J.-P. Hubaux, “Lattigo: A multiparty homomorphic encryption library in go,” pp. 6. 64–70, 2020.
  * [24] 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.
  * [25] “Palladium Emulation.”  https://www.cadence.com/en_US/home/tools/system-design-and-verification/emulation-and-prototyping/palladium.html Accessed on Nov-01-2023.
  * [26] J. H. Cheon, M. Hhan, S. Hong, and Y. Son, “A hybrid of dual and meet-in-the-middle attack on sparse and ternary secret lwe,” IEEE Access, vol. 7, pp. 89497–89506, 2019.
  * [27] J.-P. Bossuat, C. Mouchet, J. Troncoso-Pastoriza, and J.-P. Hubaux, “Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 587–617, Springer, 2021.
  * [28] “DARPA DPRIVE Broad Agency Announcement (BAA), HR001120S0032.”  https://www.dla.mil/Strategic-Materials/Business/Broad-Agency-Announcement/ Accessed on Nov-01-2023.
  * [29] W. Jung, S. Kim, J. H. Ahn, J. H. Cheon, and Y. Lee, “Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with gpus,” IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 114–148, 2021.
  * [30] 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.
  * [31] 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.
  * [32] K. Garimella, Z. Ghodsi, N. K. Jha, S. Garg, and B. Reagen, “Characterizing and optimizing end-to-end systems for private inference,” in Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, ACM, mar 2023.
  * [33] J. Mo, K. Garimella, N. Neda, A. Ebel, and B. Reagen, “Towards Fast and Scalable Private Inference,” arXiv e-prints, p. arXiv:2307.04077, July 2023.
  * [34] 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, pp. 546–561, 2020.
  * [35] R. Dathathri, O. Saarikivi, H. Chen, K. Laine, K. Lauter, S. Maleki, M. Musuvathi, and T. Mytkowicz, “Chet: compiler and runtime for homomorphic evaluation of tensor programs,” arXiv preprint arXiv:1810.00845, 2018.
  * [36] Y. Lee, S. Heo, S. Cheon, S. Jeong, C. Kim, E. Kim, D. Lee, and H. Kim, “Hecate: Performance-aware scale optimization for homomorphic encryption compiler,” in 2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pp. 193–204, IEEE, 2022.
  * [37] 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, pp. 375–389, 2021.
  * [38] A. Viand, P. Jattke, M. Haller, and A. Hithnawi, “Heco: Automatic code optimizations for efficient fully homomorphic encryption,” arXiv preprint arXiv:2202.01649, 2022.
  * [39] A. Al Badawi, B. Veeravalli, C. F. Mun, and K. M. M. Aung, “High-performance fv somewhat homomorphic encryption on gpus: An implementation using cuda,” IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 70–95, 2018.
  * [40] S. Kim, W. Jung, J. Park, and J. H. Ahn, “Accelerating number theoretic transformations for bootstrappable homomorphic encryption on GPUs,” in 2020 IEEE International Symposium on Workload Characterization (IISWC), IEEE, oct 2020.
  * [41] W. Jung, S. Kim, J. H. Ahn, J. H. Cheon, and Y. Lee, “Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with gpus,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2021, p. 114–148, Aug. 2021.
  * [42] Y. B. Kaustubh Shivdikar, M. S. Rashmi Agrawal, E. M. Gilbert Jonatan, J. L. Abellán, A. Ingare, J. K. Neal Livesay, and D. K. Ajay Joshi, “Gme: Gpu-based microarchitectural extensions to accelerate homomorphic encryption,” MICRO’23, October 28-November 1, 2023, Toronto, ON, Canada, 2023.
  * [43] Y. Yang, H. Zhang, S. Fan, H. Lu, M. Zhang, and X. Li, “Poseidon: Practical homomorphic encryption accelerator,” in 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pp. 870–881, 2023.
  * [44] S. Gener, P. Newton, D. Tan, S. Richelson, G. Lemieux, and P. Brisk, “An fpga-based programmable vector engine for fast fully homomorphic encryption over the torus,” in SPSL: Secure and Private Systems for Machine Learning (ISCA Workshop), 2021.
  * [45] Y. Zhu, X. Wang, L. Ju, and S. Guo, “Fxhenn: Fpga-based acceleration framework for homomorphic encrypted cnn inference,” in 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pp. 896–907, IEEE, 2023.
  * [46] B. Reagen, W. Choi, Y. Ko, V. Lee, G.-Y. Wei, H.-H. S. Lee, and D. Brooks, “Cheetah: Optimizing and accelerating homomorphic encryption for private inference,” 2020.