IEEEexample:BSTcontrol

# Evaluating Homomorphic Operations
on a Real-World Processing-In-Memory System

Harshita Gupta∗ Mayank Kabra∗ Juan Gómez-Luna Konstantinos Kanellopoulos Onur
Mutlu
ETH Zürich

###### Abstract

Computing on encrypted data is a promising approach to reduce data security
and privacy risks, with homomorphic encryption serving as a facilitator in
achieving this goal. In this work, we accelerate homomorphic operations using
the Processing-in-Memory (PIM) paradigm to mitigate the large memory capacity
and frequent data movement requirements. Using a real-world PIM system, we
accelerate the Brakerski-Fan-Vercauteren (BFV) scheme for homomorphic addition
and multiplication. We evaluate the PIM implementations of these homomorphic
operations with statistical workloads (arithmetic mean, variance, linear
regression) and compare to CPU and GPU implementations. Our results
demonstrate $50-100\times$ speedup with a real PIM system (UPMEM) over the CPU
and $2-15\times$ over the GPU in vector addition. For vector multiplication,
the real PIM system outperforms the CPU by $40-50\times$. However, it lags
$10-15\times$ behind the GPU due to the lack of native sufficiently wide
multiplication support in the evaluated first-generation real PIM system. For
mean, variance, and linear regression, the real PIM system performance
improvements vary between $30\times$ and $300\times$ over the CPU and between
$10\times$ and $30\times$ over the GPU, uncovering real PIM system trade-offs
in terms of scalability of homomorphic operations for varying amounts of data.
We plan to make our implementation open-source in the future.

**footnotetext: Equal contribution.

##  1 Introduction

Traditional security measures that operate on plain (unencrypted) data often
expose the actual data during processing, creating security and privacy
vulnerabilities. Homomorphic Encryption (HE) [1, 2, 3, 4, 5, 6, 7, 8]
addresses this by enabling calculations on encrypted data without revealing
sensitive information.

A user can (1) encrypt data, and (2) send it to the server. Then, (3)
computing resources in the server operate on the data without decrypting it,
using HE, and (4) the encrypted results are returned to the user, preserving
data privacy [9, 10, 11, 5]. However, HE is very costly due to the use of
large ciphertexts and computation intensive operations [12, 13, 14, 15]. For
example, performing homomorphic multiplication on two fully homomorphic (FHE)
encrypted integers may require tens of millions of operations [16, 17, 18].
The complexity is further compounded by intricate mathematical operations, as
each of these operations is executed on data that can be up to $1000\times$
larger in size than the original plain data [16, 2, 19].

Recent research proposes the implementation of homomorphic operations on CPUs
[17, 20, 21, 22], GPUs [4, 23, 24, 22, 25], FPGAs [26, 27, 28, 29, 30, 31],
and ASICs [32, 13, 33, 34, 35, 36, 37], but these implementations do not
fundamentally solve the _data movement bottleneck_ associated with homomorphic
operations.

_Processing-in-Memory (PIM)_ , i.e., equipping memory with compute
capabilities [38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53,
54, 55, 56, 57, 58, 59, 16, 60, 61], can effectively alleviate the data
movement needs. Recent PIM-based HE solutions [16, 11, 62, 63] leverage high
parallelism and memory bandwidth inside the memory chips for acceleration.
However, there is no evaluation of homomorphic operations on real PIM systems,
which have recently been introduced [38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
50].

To our knowledge, this study is the first to implement and evaluate
homomorphic operations on a real PIM system. Using a real PIM system
(UPMEM)[38, 64, 44], we accelerate the Brakerski-Fan-Vercauteren (BFV) scheme
[65, 66] for homomorphic addition and multiplication. Our evaluation shows
that the real PIM system accelerates the homomorphic addition operation by
$50-100\times$ over a state-of-the-art CPU and by $2-15\times$ over a state-
of-the-art GPU. For the homomorphic multiplication operation, the real PIM
system provides a speedup of $30-50\times$ over the CPU, but lags
$10-15\times$ behind the GPU due to the lack of native sufficiently wide
multiplication support on the evaluated first-generation UPMEM PIM system. We
also evaluate our implementation of three statistical workloads (mean,
variance, linear regression) using homomorphic addition and homomorphic
multiplication. In our evaluation, the real PIM system achieves up to
$300\times$ speedup over the CPU for all workloads and up to $30\times$ over
the GPU for arithmetic mean. However, it lags by up to $50\times$ compared to
the GPU for variance and linear regression, due to the low performance of
multiplication on the first real-world PIM system.

Our work makes the following contributions:

  * •

We develop the first implementation of homomorphic addition and multiplication
on a real PIM system.

  * •

We evaluate the performance of homomorphic addition and multiplication on a
real PIM system for different bit-key security levels (27-109 bits). We use
three real-world statistical workloads (arithmetic mean, variance, linear
regression) for evaluation.

  * •

Our findings demonstrate the capabilities and tradeoffs of real PIM systems
for efficient cryptographic operations, providing a foundation for future
developments in this direction.

##  2 Background and Motivation

Homomorphic encryption (HE)[1, 2, 3, 4, 5, 6, 7, 8] enables processing (e.g.,
addition, multiplication, rotation) on encrypted data while preserving
privacy. We focus on the BFV (Brakerski-Fan-Vercauteren) scheme for HE [65,
66], but the implementation techniques that we propose are also applicable to
other HE schemes (e.g., BGV [67] and CKKS [68]). HE types include Fully
Homomorphic Encryption (FHE), Partially Homomorphic Encryption (PHE), and
Somewhat Homomorphic Encryption (SHE) [69]. FHE enables unrestricted
operations, PHE permits one type of operation, and SHE supports both addition
and multiplication with constraints on multiplicative depth. FHE, SHE, and PHE
offer different trade-offs between security and efficiency [70, 71, 8, 1, 72,
5, 7]. In this paper, we focus on SHE as it provides a balance between
security and efficiency, allowing some computations (e.g., addition,
multiplication) on encrypted data while still maintaining a high level of
security.

HE poses two main challenges that limit its use in real-world applications.

1) Large memory footprint: HE schemes require very long vectors with wide
elements to encode information [13]. Prior work [32] shows that multiplying
2MB ciphertexts requires 32MB of auxiliary data, and 25MB ciphertexts would
require over 1.4GB of auxiliary data. This amount of auxiliary data is too
large to fit on a processor-centric chip which limits the scalability and
performance of HE.

2) Frequent data movement: The large amount of data that homomorphic
algorithms need to operate on is moved back-and-forth between off-chip
memory/storage units and compute units. Prior work [73] shows that homomorphic
operations exhibit low arithmetic intensity (<1 operations/byte). As a result,
in processor-centric systems, such as CPUs and GPUs, it is challenging to
efficiently offset the performance and energy expenses incurred when
transferring large amounts of data.

Several recent works [4, 23, 24, 22, 25, 26, 27, 28, 29, 30, 31, 32, 13, 33,
34, 35, 36, 37] explore domain-specific architectures, such as GPUs, FPGAs,
and ASICs, to accelerate homomorphic operations. These efforts have achieved
significant speedups compared to CPUs. However, challenges remain in resource
limitations, data movement, and practical implementation of especially ASIC-
based accelerators [35].

In this work, our goal is to evaluate the suitability of real-world general-
purpose processing-in-memory architectures to compute homomorphic operations.
To this end, we implement homomorphic addition and multiplication on the UPMEM
PIM system [44, 39, 38], and evaluate them on real-world statistical and
machine learning workloads.

Processing-in-memory (PIM) [38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 16, 60, 61] systems can accelerate
memory-intensive applications [46, 74, 75, 64, 76] by equipping memory arrays
with compute capabilities. These systems can potentially address the challenge
of large ciphertexts in HE algorithms by reducing the overhead of data
transfers between the memory and the CPU [77, 45]. In addition to reducing
data movement, PIM also offers high levels of parallelism [38, 39], which are
useful for performing costly homomorphic operations. Thus, by computing
directly in memory, PIM can significantly improve the performance of HE.
Various real-world PIM systems have recently been introduced  [38, 39, 40, 41,
42, 43, 44, 45, 46, 47, 50]. These real-world PIM systems have some common
characteristics [64]: there is a central host processor connected to
conventional main memory, alongside PIM-enabled memory chips with processing
elements that access memory with high bandwidth and low latency. In this work,
we use the UPMEM PIM system [44, 39, 38, 78], which consists of fine-grained
multithreaded PIM cores near DRAM banks. For more details on the UPMEM PIM
system, we refer the reader to [48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58,
59, 16, 60, 44, 39, 38].

##  3 Implementation

We consider an environment where users offload computations on encrypted data
to a PIM system. Users handle key generation, encryption, and decryption to
guarantee their data privacy. Computation of homomorphic operations takes
place in a PIM system. In this work, we implement addition and multiplication
operations.

The security level of HE relies on the polynomial modulus degree [79],
affecting ciphertext length, vulnerability to attacks, and noise tolerance.
For instance, for 27-bit security, we need a polynomial that has 1024 27-bit
coefficients, which indicates a relatively lower security level in HE.
Increasing the bit length enhances security. In this work, we also evaluate
54-bit (2048-coefficient polynomial) and 109-bit (4096-coefficient polynomial)
security levels. To represent 27-, 54-, and 109-bit coefficients, we use
integers of 32, 64, and 128 bits, respectively. The reason is that the UPMEM
PIM system that we use in our evaluation has native support for 32-bit
integers.

Homomorphic Addition. We implement homomorphic addition using polynomial
addition[80, 81] on the UPMEM PIM system. Each PIM thread running on a PIM
core performs the element-wise addition of the coefficients of two
polynomials. UPMEM PIM cores [44] support native 32-bit integer addition (add)
and 32-bit integer addition with carry-in (addc), which we use to implement
64- and 128-bit addition (and can be extended to any multiple of 32 bits).

Homomorphic Multiplication. We implement homomorphic multiplication using
polynomial multiplication and polynomial addition [82, 83, 84, 85]. Each PIM
thread running on a PIM core performs the polynomial multiplication and
polynomial addition of the coefficients of two polynomials to generate the
desired result. For 32-bit coefficients, we rely on the compiler-generated
32-bit shift-and-add based multiplication.111The UPMEM PIM system performs
8-bit and 16-bit multiplications using the native 8-bit hardware multipliers,
but employs a software-based shift-and-add algorithm for higher bit widths
[44, 64, 38]. For 64- and 128-bit multiplications, we divide the bits into
chunks of 32-bits and apply the Karatsuba algorithm [86], which requires less
operations than the traditional multiplication algorithm. We do not
incorporate Number Theoretic Transform (NTT)[87, 88] techniques to optimize
multiplication. We leave them for future work.

Statistical Workloads. We implement three statistical workloads (arithmetic
mean, variance, linear regression) using homomorphic addition and homomorphic
multiplication techniques. The arithmetic mean [89, 90] workload employs
polynomial addition performed on the UPMEM PIM cores and scalar division
performed on the host processor. The variance [91, 92] workload uses
polynomial multiplication which is performed on the UPMEM PIM cores and a
final scalar division performed on the host processor. Similarly, linear
regression [93, 94] workload uses both polynomial addition and multiplication
to perform the vector-matrix multiplication, which is employed on the UPMEM
PIM cores.

##  4 Evaluation

###  4.1 Methodology

We evaluate homomorphic addition and multiplication on a first-generation
UPMEM PIM system [44, 39, 38, 78], a 4-core Intel i5-8250U CPU [95], and an
NVIDIA A100 GPU[96]. The UPMEM system contains 2,524 PIM cores (running at 425
MHz) and 158GB of PIM-enabled memory with a total bandwidth of 2,145 GB/s. We
compare our PIM implementations to our own custom CPU and GPU implementations.
We also compare to an optimized CPU implementation, the SEAL CPU library [79],
which leverages the Residue Number System (RNS) [97] and the Number Theoretic
Transform (NTT) [98] implementations for faster operations.

We first evaluate microbenchmarks for vector addition and vector
multiplication (Section 4.2). We experiment with different numbers of
ciphertexts between 20,480 to 327,680 for addition, and between 5,120 and
81,920 for multiplication. We run experiments for integers of 32 bits (27-bit
coefficients), 64 bits (54-bit coefficients), and 128 bits (109-bit
coefficients). We then evaluate SHE implementations of three statistical
workloads (arithmetic mean, variance, linear regression) that employ our PIM-
based homomorphic encryption operations (Section 4.3). We plan to open-source
all workloads.

###  4.2 Vector Addition and Multiplication

Figure 1 shows the execution time of vector addition (1(a)) and multiplication
(1(b)) on homomorphically encrypted ciphertexts for our real-world UPMEM PIM-
based implementation (PIM), our custom CPU and GPU implementations, and the
SEAL library (CPU-SEAL). The figure also shows the speedup of PIM over the
custom CPU implementations.

(a) 128-bit ciphertext vector addition

(b) 128-bit ciphertext vector multiplication

Figure 1: Execution time (ms) of ciphertext vector addition (a) and vector
multiplication (b) for 128-bit (109-bit) wide polynomial coefficients on CPU,
PIM, CPU-SEAL and GPU.

We make several observations about these experimental results. First, the
performance of PIM implementations saturates at 11 or more PIM threads (not
shown in Figure 2). This is in line with the observations in prior works [38,
45, 64]. Second, the large number of PIM cores and the native support for
32-bit integer addition in PIM cores result in fast execution of vector
addition on the PIM system. Figure 1(a) shows the results for 128-bit
addition. The trends are the same for 32-bit and 64-bit addition. For 32-,
64-, and 128-bit addition, the PIM implementation outperforms CPU, CPU-SEAL,
and GPU by $20-150\times$, $35-80\times$, and $15-50\times$, respectively.

Key Takeaway 1. _With native hardware support for 32-bit integer addition and
large number of PIM cores, the UPMEM PIM system outperforms CPU and GPU for
homomorphic addition._

Third, vector multiplication on the UPMEM PIM system suffers from the lack of
native 32-bit multiplication hardware, as multiplication wider than 16 bits is
based on compiler generated shift-and-add algorithm. Figure 1(b) shows the
results for 128-bit multiplication. We observe similar trends for 32-bit and
64-bit multiplication. For 32-, 64-, and 128-bit multiplication, the PIM
implementation outperforms CPU by $40-50\times$, and CPU-SEAL for 32 bits by
$2\times$. However, the PIM implementation is $12-15\times$ slower than GPU,
and $2-4\times$ slower than CPU-SEAL for 64 and 128 bits.

Key Takeaway 2. _The lack of native support for 32-bit integer multiplication
hampers the performance of PIM for homomorphic multiplication. Future PIM
systems with native 32-bit multiplication hardware could potentially
outperform CPUs and GPUs._

###  4.3 Statistical Workloads

We implement and evaluate the performance of three real-world statistical
workloads (arithmetic mean, variance, linear regression) that utilize
homomorphic addition and multiplication for the CPU, real-world PIM, CPU-SEAL
and GPU implementations. Figure 2 shows the execution times of the three
workloads on CPU, PIM, CPU-SEAL, and GPU. For arithmetic mean and variance, we
evaluate scenarios with 640, 1280, and 2560 users. For linear regression, we
evaluate 640 users, and 32 and 64 ciphertexts per user (data samples with 3
features).

(a) Arithmetic Mean

(b) Variance

(c) Linear Regression

Figure 2: Execution time (ms) of aritmetic mean (a), variance (b), and linear
regression (c) for 128-bit (109-bit) wide polynomial coefficients on CPU, PIM,
CPU-SEAL and GPU.

We make several observations from Figure 2. First, arithmetic mean uses only
homomorphic addition. As a result, PIM is significantly faster than CPU, CPU-
SEAL, and GPU. Figure 2(a) shows PIM speedups of $25-100\times$ over CPU,
$11-50\times$ over CPU-SEAL, and $9-34\times$ over GPU for different numbers
of users. Second, as variance uses the square operation (i.e., homomorphic
multiplication of two equal numbers), the PIM implementation is heavily
burdened by the slow multiplication. In Figure 2(b), we observe that PIM
outperforms only the custom CPU implementation (by $6-25\times$) for different
numbers of users. CPU-SEAL and GPU are, respectively, $2-10\times$ and
$13-50\times$ faster than PIM. Third, for linear regression the trends are the
same as for variance, given that linear regression also uses multiplication
heavily. Figure 2(c) shows that PIM is only faster than the custom CPU
implementation (by $7.5\times$) for 32 ciphertexts. CPU-SEAL and GPU are,
respectively, $11.4\times$ and $54.9\times$ faster than PIM for 64
ciphertexts. Fourth, we observe that PIM execution time remains constant for
different numbers of users. This is achieved by dynamically adjusting the
utilization of PIM cores, which is particularly beneficial in our experiments
as they involve a large number of users. This approach differs from CPUs and
GPUs, which have a limited number of cores and must use them regardless of the
number of users in our experiment.

Key Takeaway 3. _The computational power of PIM scales with memory
capacity[99, 100] via the addition of more memory banks and corresponding PIM
cores. This memory-capacity-proportional performance scalability provided by
PIM holds promise for accommodating expanding numbers of users and more
parallel computations as memory capacity grows._

##  5 Related Work

Several recent works explore the suitability of real-world processing-in-
memory (PIM) architectures [38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 16, 60, 61] to accelerate a variety of
memory-intensive tasks [46, 74, 75, 64, 76]. To our knowledge, this is the
first work to explore the use of a real PIM system to accelerate homomorphic
operations.

Acceleration of homomorphic operations on GPUs, FPGAs, or ASICs is the subject
of various recent works. All these processor-centric techniques suffer from
data movement bottlenecks between memory and compute units. GPUs can
accelerate HE schemes [4, 23, 24, 22, 25]. However, GPUs suffer from high
power consumption for homomorphic operations [101, 102]. FPGAs can also
accelerate homomorphic operations [26, 27, 28, 29, 30, 31], but they are
limited in hardware resources and suffer from data movement bottlenecks [103,
104]. Several recent works propose ASIC designs [32, 13, 33, 34, 35, 36, 37]
for CKKS algorithms, but they are only evaluated in simulation. Similarly,
PIM-based solutions [11, 16, 105] for accelerating homomorphic operations are
also limited to simulation.

##  6 Conclusion

We presented initial results on the use of a real-world general-purpose PIM
architecture (i.e., the UPMEM PIM system [50, 38]) to accelerate homomorphic
operations. Our PIM implementations of homomorphic addition, multiplication
and statistical workloads (mean, variance, linear regression) show great
promise when compared to CPU and GPU implementations, as long as the necessary
integer operations are natively supported by the PIM hardware. We aim to
implement more homomorphic operations and optimizations as future work.

## Acknowledgments

We acknowledge support from the SAFARI Research Group’s industrial partners,
especially Google, Huawei, Intel, Microsoft, VMware, and the Semiconductor
Research Corporation. This research was partially supported by the ETH Future
Computing Laboratory and the European Union’s Horizon programme for research
and innovation under grant agreement No. 101047160, project BioPIM
(Processing-in-memory architectures and programming libraries for
bioinformatics algorithms). This research was also partially supported by
ACCESS – AI Chip Center for Emerging Smart Systems, sponsored by InnoHK
funding, Hong Kong SAR.

## References

  * [1] M. Ogburn _et al._ , “Homomorphic Encryption,” _Procedia Computer Science_ , 2013.
  * [2] D. Tourky _et al._ , “Homomorphic Encryption The “Holy Grail” of Cryptography,” in _ICCC 2016_.
  * [3] C. Gentry and S. Halevi, “Implementing Gentry’s Fully Homomorphic Encryption Scheme,” in _EUROCRYPT 2011_.
  * [4] A. Al Badawi _et al._ , “Towards The Alexnet Moment For Homomorphic Encryption: HCNN, The First Homomorphic CNN on Encrypted Data With GPUs,” _TETC 2020_.
  * [5] C. Gentry, “Fully Homomorphic Encryption using Ideal Lattices,” in _STOC 2009_.
  * [6] M. Van Dijk _et al._ , “Fully Homomorphic Encryption over the Integers,” in _EUROCRYPT 2010_.
  * [7] D. Boneh _et al._ , “Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE, and Compact Garbled Circuits,” IACR 2014.
  * [8] D. Boneh _et al._ , “Private Database Queries using Somewhat Homomorphic Encryption,” in _ACNS_ , 2013.
  * [9] C. Moore _et al._ , “Practical Homomorphic Encryption: A Survey,” in _ISCAS 2014_.
  * [10] P. Chaudhary _et al._ , “Analysis and Comparison of Various Fully Homomorphic Encryption Techniques,” in _GUCON 2019_.
  * [11] S. Gupta and T. Š. Rosing, “Accelerating Fully Homomorphic Encryption with Processing-in-memory,” in _DAC 2021_.
  * [12] N. Samardzic _et al._ , “F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption,” in _MICRO 2021_.
  * [13] N. Samardzic _et al._ , “Craterlake: A Hardware Accelerator for Efficient Unbounded Computation on Encrypted Data,” in _ISCA 2022_.
  * [14] B. Alaya _et al._ , “Homomorphic Encryption Systems Statement: Trends and Challenges,” _CSR 2020_.
  * [15] K. El Makkaoui _et al._ , “Challenges of Using Homomorphic Encryption to Secure Cloud Computing,” in _CloudTech 2015_.
  * [16] S. Gupta _et al._ , “MemFHE: End-to-end Computing with Fully Homomorphic Encryption in Memory,” _TECS 2022_.
  * [17] X. Cao _et al._ , “Optimised Multiplication Architectures For Accelerating Fully Homomorphic Encryption,” _TC 2015_.
  * [18] Y. Su _et al._ , “A Highly Unified Reconfigurable Multicore Architecture to Speed-up NTT/INTT for Homomorphic Polynomial Multiplication,” _TVLSI 2022_.
  * [19] Y. Doröz _et al._ , “Homomorphic AES Evaluation using the Modified LTV Scheme,” _DCC 2016_.
  * [20] A. C. Mert _et al._ , “Design and Implementation of Encryption/Decryption Architectures for BFV Homomorphic Encryption Scheme,” _TVLSI 2019_.
  * [21] S. Meftah _et al._ , “Towards High Performance Homomorphic Encryption for Inference Tasks on CPU: An MPI Approach,” _FGCS 2022_.
  * [22] T. Morshed _et al._ , “CPU and GPU Accelerated Fully Homomorphic Encryption,” in _HOST 2020_.
  * [23] W. Dai and B. Sunar, “cuHE: A Homomorphic Encryption Accelerator Library,” in _BalkanCryptSec 2016_.
  * [24] A. Al Badawi _et al._ , “Multi-GPU Design and Performance Evaluation of Homomorphic Encryption on GPU Clusters,” _TPDS 2020_.
  * [25] W. Dai _et al._ , “Accelerating NTRU based Homomorphic Encryption using GPUs,” in _HPEC 2014_.
  * [26] W. Wang and H. Xinming, “FPGA Implementation Of a Large-number Multiplier for Fully Homomorphic Encryption,” in _ISCAS 2013_.
  * [27] R. Agrawal _et al._ , “FAB: An FPGA-based Accelerator for Bootstrappable Fully Homomorphic Encryption,” in _HPCA 2023_.
  * [28] D. B. Cousins _et al._ , “Designing an FPGA-accelerated Homomorphic Encryption Co-processor,” _TETC 2016_.
  * [29] D. B. Cousins _et al._ , “An FPGA Co-processor Implementation of Homomorphic Encryption,” in _HPEC 2014_.
  * [30] I. Syafalni _et al._ , “Efficient Homomorphic Encryption Accelerator with Integrated PRNG using Low-cost FPGA,” _IEEE Access 2022_.
  * [31] C. Jayet-Griffon _et al._ , “Polynomial Multipliers for Fully Homomorphic Encryption on FPGA,” in _ReConFig 2015_.
  * [32] A. Feldmann _et al._ , “F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption,” _MICRO 2021_.
  * [33] Y. Yang _et al._ , “Poseidon: Practical Homomorphic Encryption Accelerator,” in _HPCA 2023_.
  * [34] E. Öztürk _et al._ , “A Custom Accelerator for Homomorphic Encryption Applications,” _TC 2016_.
  * [35] S. Kim _et al._ , “BTS: An Accelerator for Bootstrappable Fully Homomorphic Encryption,” in _ISCA 2022_.
  * [36] M. Nabeel _et al._ , “CoFHEE: A Co-processor for Fully Homomorphic Encryption Execution,” in _DATE 2023_.
  * [37] X. Cao _et al._ , “High-speed Fully Homomorphic Encryption over the Integers,” in _FC 2014_.
  * [38] J. Gómez-Luna _et al._ , “Benchmarking Memory-centric Computing Systems: Analysis of Real Processing-in-Memory Hardware,” in _IGSC 2021_.
  * [39] J. Gómez-Luna _et al._ , “Benchmarking a New Paradigm: Experimental Analysis and Characterization of a Real Processing-in-memory System,” _IEEE Access 2022_.
  * [40] J. H. Kim _et al._ , “Aquabolt-XL: Samsung HBM2-PIM with In-memory Processing for ML Accelerators and Beyond,” in _HCS 2021_.
  * [41] J. H. Kim _et al._ , “Aquabolt-XL HBM2-PIM, LPDDR5-PIM with In-memory Processing, and AXDIMM with Acceleration Buffer,” _IEEE MICRO 2022_.
  * [42] D. Lee _et al._ , “Improving In-Memory Database Operations with Acceleration DIMM (AxDIMM),” in _DaMoN_ , 2022.
  * [43] L. Ke _et al._ , “Near-Memory Processing in Action: Accelerating Personalized Recommendation with AxDIMM,” _IEEE Micro_ , 2021.
  * [44] “UPMEM SDK,” https://sdk.upmem.com/2023.1.0/.
  * [45] J. Gómez-Luna _et al._ , “Machine Learning Training on a Real Processing-in-Memory System,” in _ISVLSI 2022_.
  * [46] M. Item _et al._ , “TransPimLib: Efficient Transcendental Functions for Processing-in-Memory Systems,” in _ISPASS_ , 2023.
  * [47] J. Kim and Y. Kim, “HBM: Memory Solution for Bandwidth-hungry Processors,” in _HCS_ , 2014.
  * [48] S. Ghose _et al._ , “The Processing-in-Memory Paradigm: Mechanisms to Enable Adoption,” in _Beyond-CMOS Technologies for Next Generation Computer Design 2019_.
  * [49] G. F. Oliveira _et al._ , “DAMOV: A New Methodology And Benchmark Suite For Evaluating Data Movement Bottlenecks,” _IEEE Access 2021_.
  * [50] F. Devaux, “The True Processing in Memory Accelerator,” in _HCS_ , 2019.
  * [51] S. Ghose _et al._ , “Processing-in-memory: A Workload-driven Perspective,” _IBM JRD 2019_.
  * [52] O. Mutlu _et al._ , “A Modern Primer on Processing-in-memory,” in _Emerging Computing: From Devices to Systems: Looking Beyond Moore and Von Neumann 2022_.
  * [53] V. Seshadri _et al._ , “Ambit: In-memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology,” in _MICRO 2017_.
  * [54] H. S. Stone, “A Logic-in-Memory Computer,” _IEEE TC_ , 1970.
  * [55] W. H. Kautz, “Cellular Logic-in-Memory Arrays,” _IEEE TC_ , 1969.
  * [56] A. Farmahini-Farahani _et al._ , “DRAMA: An Architecture for Accelerated Processing-near-memory,” _IEEE Computer Architecture Letters_ , 2014.
  * [57] G. Singh _et al._ , “A Review of Near-memory Computing Architectures: Opportunities and Challenges,” in _Euromicro DSD 2018_.
  * [58] Y. Kwon _et al._ , “TensorDIMM: A Practical Near-memory Processing Architecture for Embeddings and Tensor Operations in Deep Learning,” in _MICRO 2019_.
  * [59] S. F. Yitbarek _et al._ , “Exploring Specialized Near-memory Processing for Data-intensive Operations,” in _DATE 2016_.
  * [60] N. Hajinazar _et al._ , “SIMDRAM: A Framework for Bit-serial SIMD Processing-using-DRAM,” in _ASPLOS 2021_.
  * [61] C. Lim _et al._ , “Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs,” _ACM SIGMOD_ , 2023.
  * [62] W. Li _et al._ , “Leveraging Memory PUFs and PIM-based Encryption to Secure Edge Deep Learning Systems,” in _VTS 2019_.
  * [63] D. Reis _et al._ , “Computing-in-memory for Performance and Energy-efficient Homomorphic Encryption,” _TVLSI 2020_.
  * [64] J. Gómez-Luna _et al._ , “An Experimental Evaluation of Machine Learning Training on a Real Processing-in-Memory System,” _arXiv preprint arXiv:2207.07886_ , 2022.
  * [65] S. Halevi _et al._ , “An Improved RNS Variant of the BFV Homomorphic Encryption Scheme,” in _CT-RSA 2019_.
  * [66] F. Wibawa _et al._ , “BFV-Based Homomorphic Encryption for Privacy-Preserving CNN Models,” _Cryptography 2022_.
  * [67] J. Mono _et al._ , “Finding and Evaluating Parameters for BGV,” _Cryptology ePrint Archive_ , 2022.
  * [68] J. H. Cheon _et al._ , “Remark on the Security of CKKS Scheme in Practice,” _Cryptology ePrint Archive_ , 2020.
  * [69] A. Acar _et al._ , “A Survey on Homomorphic Encryption Schemes: Theory and Implementation,” _ACM CSUR 2018_.
  * [70] A. B. Alexandru _et al._ , “Cloud-based Quadratic Optimization with Partially Homomorphic Encryption,” _IEEE TAC_ , 2020.
  * [71] I. Damgård _et al._ , “Multiparty Computation From Somewhat Homomorphic Encryption,” in _CRYPTO 2012_.
  * [72] M. Yasuda _et al._ , “Practical Packing Method in Somewhat Homomorphic Encryption,” in _DPM 2013 and SETOP 2013_.
  * [73] L. de Castro _et al._ , “Does Fully Homomorphic Encryption Need Compute Acceleration?” _IACR 2021_.
  * [74] S. Diab _et al._ , “A Framework for High-throughput Sequence Alignment using Real Processing-in-Memory Systems,” _Bioinformatics_ , 2023.
  * [75] C. Giannoula _et al._ , “Towards Efficient Sparse Matrix Vector Multiplication on Real Processing-in-Memory Architectures,” in _SIGMETRICS_ , 2022.
  * [76] G. F. Oliveira _et al._ , “Accelerating Neural Network Inference with Processing-in-DRAM: From the Edge to the Cloud,” _IEEE Micro 2022_.
  * [77] O. Mutlu _et al._ , “Processing Data Where It Makes Sense: Enabling In-memory Computation,” _MICPRO_ , 2019.
  * [78] J. Gómez-Luna _et al._ , “Evaluating Machine Learning Workloads on Memory-Centric Computing Systems,” in _ISPASS 2023_.
  * [79] “Microsoft SEAL,” https://www.microsoft.com/en-us/research/project/microsoft-seal/.
  * [80] E. D. Sontag, “Real Addition and the Polynomial Hierarchy,” _IPL 1985_.
  * [81] R. Zippel, _"Effective Polynomial Computation"_. SSBM 1993.
  * [82] R. T. Moenck, “Practical Fast Polynomial Multiplication,” in _SYMSAC 1976_.
  * [83] D. Harvey _et al._ , “Faster Polynomial Multiplication over Finite Fields,” _JACM 2017_.
  * [84] D. Harvey _et al._ , “Polynomial multiplication over finite fields in time,” _JACM 2022_.
  * [85] D. D. Chen _et al._ , “High-speed Polynomial Multiplication Architecture for Ring-LWE and SHE Cryptosystems,” _TCAS-I 2014_.
  * [86] C. Eyupoglu, “Performance Analysis of Karatsuba Multiplication Algorithm for Different Bit Lengths,” _Procedia: SBS 2015_.
  * [87] M. Bisheh-Niasar _et al._ , “High-Speed NTT-based Polynomial Multiplication Accelerator For CRYSTALS-Kyber Post-Quantum Cryptography,” _ICAR 2021_.
  * [88] T. Fritzmann and J. Sepúlveda, “Efficient and Flexible Low-Power NTT for Lattice-Based Cryptography,” in _HOST 2019_.
  * [89] E. Jacquier _et al._ , “Geometric or Arithmetic Mean: A Reconsideration,” _FAJ_ , 2003.
  * [90] T.-H. Zhao _et al._ , “On Approximating the Quasi-arithmetic Mean,” _JIA_ , 2019.
  * [91] M. G. Larson, “Analysis of Variance,” _Circulation_ , 2008.
  * [92] M. Davidian _et al._ , “Variance Function Estimation,” _JASA_ , 1987.
  * [93] X. Su _et al._ , “Linear Regression,” _WIREs Comp Stats_ , 2012.
  * [94] D. Maulud _et al._ , “A Review on Linear Regression Comprehensive in Machine Learning,” _JASTT_ , 2020.
  * [95] Intel, “Intel® Core™ i5-8250U Processor,” https://ark.intel.com/content/www/us/en/ark/products/124967/intel-core-i58250u-processor-6m-cache-up-to-3-40-ghz.html, 2017.
  * [96] NVIDIA, “NVIDIA A100 Tensor Core GPU Architecture. White Paper,” https://images.nvidia.com/aem-dam/en-zz/Solutions/data-center/nvidia-ampere-architecture-whitepaper.pdf, 2020.
  * [97] M. Gomathisankaran _et al._ , “HORNS: A Homomorphic Encryption Scheme for Cloud Computing using Residue Number System,” in _IEEE CISS 2011_.
  * [98] A. W. Mohsen _et al._ , “Performance Analysis of Number Theoretic Transform for Lattice-based Cryptography,” in _ICCES 2018_.
  * [99] J. Ahn _et al._ , “A Scalable Processing-in-memory Accelerator for Parallel Graph Processing,” in _ISCA_ , 2015.
  * [100] J. Ahn _et al._ , “Retrospective: A Scalable Processing-in-memory Accelerator for Parallel Graph Processing,” _arXiv preprint arXiv:2306.15577_ , 2023.
  * [101] S. Tan _et al._ , “CryptGPU: Fast Privacy-preserving Machine Learning on the GPU,” in _SP 2021_.
  * [102] W. Wang _et al._ , “Exploring the Feasibility of Fully Homomorphic Encryption,” _IEEE TC 2013_.
  * [103] S. S. Roy _et al._ , “HEPCloud: An FPGA-based Multicore Processor for FV Somewhat Homomorphic Function Evaluation,” _TC 2018_.
  * [104] S. S. Roy _et al._ , “FPGA-based High-performance Parallel Architecture For Homomorphic Computing on Encrypted Data,” in _HPCA 2019_.
  * [105] H. Nejatollahi _et al._ , “CryptoPIM: In-memory Acceleration for Lattice-based Cryptographic Hardware,” in _DAC 2020_.