Bootstrapping in approximate fully homomorphic encryption: a research survey

Abstract

Fully homomorphic encryption (FHE) has emerged as a prominent area of cryptographic research in recent years, offering the capability to perform computations on ciphertext without compromising data privacy. Among various FHE schemes, the Cheon–Kim–Kim–Song (CKKS) algorithm for approximate homomorphic encryption has gained prominence due to its efficient handling of floating-point operations. Bootstrapping, a critical technique that enables unlimited homomorphic operations by refreshing noisy ciphertexts, represents both the most complex and essential component of practical FHE implementations. This survey provides a comprehensive analysis of bootstrapping techniques in CKKS, examining their evolution from the original proposal to current state-of-the-art methods. Recent literature has witnessed a proliferation of novel bootstrapping schemes for CKKS, these diverse approaches often emphasize different performance aspects, leading to a lack of a unified quantitative framework for comparative analysis. To address this gap, we systematically categorize existing approaches into three main directions: optimization of homomorphic modular reduction, optimization of encoding/decoding operations, and development of alternative constructions using blind rotation techniques. Through detailed comparative analysis, we identify that current schemes can achieve either high throughput (processing over 1000 ciphertexts per second) or high precision (up to 400 bits), but exhibit limitations in concurrent optimization of both parameters. Furthermore, potential directions for future optimizations are explored and discussed, contributing to the ongoing development of efficient and practical FHE systems.

Introduction

In recent years, Fully Homomorphic Encryption (FHE) has garnered significant attention due to its ability to perform computations on encrypted data without compromising privacy. FHE presents broad application prospects, such as protecting user data privacy in cloud computing and enabling data sharing and computation in untrusted environments. Since (Rivest et al. 1978) introduced the concept of FHE in 1978, it has been regarded as the Holy Grail of cryptography. For an extended period, homomorphic encryption schemes could only achieve partial homomorphic encryption (PHE) (Rivest et al. 1983; Paillier 1999; ElGamal 2000) or somewhat homomorphic encryption (SWHE) (Boneh et al. 2005). The key limitation preventing full homomorphic capabilities was the accumulation of noise during computations, until Gentry (Gentry 2009) proposed the revolutionary bootstrapping technique in 2009.

The significance of bootstrapping in FHE cannot be overstated. In all FHE schemes, each homomorphic operation introduces noise into the ciphertext, which accumulates with subsequent operations. Without intervention, this noise eventually overwhelms the encrypted data, making correct decryption impossible. This fundamental limitation would restrict FHE to a finite number of operations, severely limiting its practical utility. Bootstrapping serves as the crucial mechanism that “refreshes” noisy ciphertexts by homomorphically evaluating the decryption circuit, effectively resetting the noise level and enabling unlimited consecutive operations. This capability transforms FHE from a theoretical curiosity into a practical tool for real-world applications. However, bootstrapping remains the most computationally intensive operation in FHE schemes, often determining the practical feasibility of FHE applications. The efficiency of bootstrapping thus represents a critical bottleneck in the widespread adoption of FHE technology, making it a central focus of ongoing research and optimization efforts.

This breakthrough in bootstrapping technology catalyzed rapid development in the field of fully homomorphic encryption, leading to substantial advances in both efficiency and practical applicability. Notable developments include the BGV (Brakerski et al. 2014, 2011) and BFV (Brakerski 2012; Fan and Vercauteren 2012) schemes operating over finite fields, as well as bit-oriented approaches such as FHEW/AP (Ducas and Micciancio 2015; Alperin-Sheriff and Peikert 2014a; Pereira 2021a) and TFHE/GINX (Chillotti et al. 2016, 2017, 2019; Gama et al. 2016a). While these schemes demonstrate ingenious designs and excel at precise integer and bit-level computations, they encounter significant challenges in efficiently handling floating-point operations.

This limitation is particularly crucial given that many contemporary applications, especially in the domain of privacy-preserving machine learning (Al-Rubaie and Chang 2019), fundamentally rely on floating-point arithmetic. The growing demand for privacy-preserving techniques in data-intensive applications has thus highlighted the critical need for efficient homomorphic floating-point computation. This requirement has emerged as a key determinant in bridging the gap between theoretical FHE capabilities and practical deployment requirements, establishing efficient floating-point arithmetic as a central focus in modern FHE research.

Within the FHE ecosystem, different schemes have evolved to serve distinct computational needs. The BGV and BFV schemes excel at exact integer arithmetic and are particularly well-suited for applications requiring precise calculations. These schemes have demonstrated significant utility when combined with specific protocols such as secure Multi-Party Computation (MPC) (Chen et al. 2021a; Huang et al. 2022; Lu et al. 2023), private set intersection (PSI) (Chen et al. 2017; Cong et al. 2021; Kales et al. 2019; Resende and Aranha 2018; Chen et al. 2021a), and private information retrieval (PIR) (Angel et al. 2018; Mughees et al. 2021; Mahdavi and Kerschbaum 2022). Complementing these, FHEW/TFHE schemes specialize in boolean circuit evaluation and bit-level operations, enabling efficient implementation of comparison operations (Liu et al. 2022), lookup tables (Chillotti et al. 2021), and even homomorphic AES operation (Wang et al. 2024).

The emerging need for efficient floating-point arithmetic in privacy-preserving applications has led to the development of the approximate homomorphic encryption approach (Cheon et al. 2017), which would later be formalized as the CKKS scheme. This approach has rapidly gained prominence as the mainstream solution for applications involving real-number computations, particularly in machine learning and statistical analysis. Recent research has further demonstrated the potential for cross-scheme interoperability, where approximate floating-point operations can be effectively combined with the bit-wise precision of FHEW/TFHE or the exact arithmetic of BGV/BFV to create hybrid solutions (Boura et al. 2020; Chen et al. 2021b). This complementary ecosystem enables developers to select the most appropriate scheme based on their specific computational requirements while maintaining the flexibility for scheme interoperation when needed.

At ASIACRYPT 2017, the CKKS scheme was formally presented (Cheon et al. 2017) as a groundbreaking solution for homomorphic floating-point computation through its innovative treatment of noise in Ring Learning With Error (RLWE). Rather than attempting to eliminate noise entirely, CKKS incorporates it as part of the plaintext, resulting in approximate computations that yield results with controlled noise during decryption. This paradigm shift proved particularly valuable for applications like machine learning and statistical analysis, where approximate results are often sufficient for practical purposes.

A year later, Cheon et al. (2018) proposed a bootstrapping method for approximate homomorphic encryption. Unlike previous bootstrapping schemes for BGV and BFV (Halevi and Shoup 2021), CKKS’s approximate nature prevents direct noise elimination through homomorphic decryption circuits. Instead, Cheon et al. (2018) employed a method that increases computational iterations to achieve bootstrapping. Specifically, they first expanded the ciphertext modulus to increase CKKS multiplication depth, while simultaneously performing homomorphic modular operations on ciphertexts to eliminate the previous small modulus. Leveraging CKKS’s inherent approximate encryption property, they approximated this modular operation using error-prone fitting methods.

The initial CKKS bootstrapping scheme (Cheon et al. 2018) suffered from low efficiency and precision. Subsequent research has focused on optimizing this approach (Chen et al. 2019; Han and Ki 2020; Lee et al. 2020, 2022d; Jutla and Manohar 2020; Bossuat et al. 2021; Lee et al. 2021b; Jutla and Manohar 2022; Lee et al. 2022e; Bae et al. 2022). Additionally, Kim et al. (2024a) and Yang et al. (2021) proposed alternative bootstrapping techniques utilizing the FHEW blind-rotate (Gentry et al. 2013; Ducas and Micciancio 2015; Chillotti et al. 2019) method to refresh noise in individual ciphertexts. This technique achieves high-precision bootstrapping with small parameters but exhibits lower throughput for packed ciphertexts compared to homomorphic modular reduction schemes.

From a security perspective, recent work by Li and Micciancio (2021) revealed that the CKKS scheme (Cheon et al. 2018) fails to satisfy IND-CPA security. This vulnerability arises from CKKS outputting noise as part of the plaintext, allowing attackers to deduce the private key using plaintext noise and ciphertext information. To mitigate this attack, Li and Micciancio (2021) proposed a noise flooding technique (Ducas and Stehlé 2016) that adds $2^{30}$ bits of noise during decryption. This approach requires CKKS bootstrapping schemes to maintain at least 30-bit precision to ensure both correct decryption and IND-CPA security. Consequently, precision has become a crucial metric for evaluating CKKS bootstrapping alongside efficiency (throughput).

The field of Fully Homomorphic Encryption has garnered substantial academic attention, resulting in numerous comprehensive surveys. These surveys can be broadly categorized into several domains: theoretical foundations of FHE (Moore et al. 2014; Marcolla et al. 2022), hardware acceleration techniques (Zhang et al. 2024; Gong et al. 2024), implementation aspects including opensource libraries and homomorphic compilers (Acar et al. 2018; Dhiman et al. 2023; Viand et al. 2021), practical applications (Wood et al. 2020a; Yang et al. 2023; Alharbi et al. 2020; Pulido-Gaytan et al. 2020), and comparative analyses of various FHE schemes (Alaya et al. 2020). Despite this extensive coverage, a dedicated survey focusing on the bootstrapping operation in the CKKS scheme remains notably absent from the literature.

This paper fills this gap by analyzing recent advances in CKKS bootstrapping algorithms. We focus on optimization techniques and their practical implications, examining theoretical foundations, implementation strategies, and real-world applications. The paper is organized as follows:

“Preliminaries” section establishes the mathematical foundations, presenting key properties and theorems of homomorphic encryption alongside a detailed examination of the CKKS scheme. “General approach and optimization of CKKS bootstrapping” section investigates the fundamental principles of CKKS bootstrapping and discusses various optimization strategies that have emerged in recent literature. “Preliminaries” section Alternative approaches to CKKS bootstrapping explores alternative approaches to CKKS bootstrapping construction, with particular emphasis on blind rotation techniques. “Performance comparison of different schemes” section provides a detailed comparative analysis of these schemes, evaluating their performance through the dual lenses of utility and precision. “Implementation resources and tools” section examines real-world applications where CKKS bootstrapping has demonstrated practical impact. The paper concludes with a synthesis of findings and identifies promising directions for future optimization efforts.

Preliminaries

Basic notation

In this paper, boldface lowercase letters represent vectors, such as $\mathit{v}$. Boldface uppercase letters denote matrices, such as $\mathit{M}$. The inner product of two vectors is denoted by $⟨·,·⟩$. The functions $\lceil ·\rfloor$, $\lceil ·\rceil$, and $\lfloor ·\rfloor$ represent rounding to the nearest integer, ceiling, and floor operations, respectively. For an integer m, ${[m]}_q$ denotes the modulo q operation. The notation $x\leftarrow \mathcal{D}$ indicates that x is sampled from the distribution $\mathcal{D}$. The discrete Gaussian distribution is denoted as $\mathcal{D}\mathcal{G}({\sigma }^2)$, where $\sigma$ is the standard deviation.

The infinity norm of a vector $\mathit{v}$ is represented by ${\Vert \mathit{v}\Vert }_{\infty }$. ${\Phi }_M(X)=X^N+1$ denotes the M-th cyclotomic polynomial, where the degree $N=M/2$ when M is a power of 2. Let $\mathcal{R}=\mathbb{Z}/({\Phi }_M(X))$ be the ring of integer polynomials, and ${\mathcal{R}}_q=\mathcal{R}/q\mathcal{R}$ be the finite field of polynomials over $Z_q$.

For $m(X)\in \mathcal{R}$, we define the canonical embedding $\mathsf{emd}$ as a mapping from the polynomial m(X) to a vector in ${\mathbb{C}}^N$, obtained by evaluating m(X) at the M-th roots of unity $m({\zeta }_M^j)$. ${\mathsf{emd}}^{-1}$ denotes the inverse of $\mathsf{emd}$. We define ${|m|}^{\mathsf{can}}\infty ={\Vert \mathsf{emd}(m)\Vert }_{\infty }$. For a polynomial $m(X)=m_0+m_{1}X+\cdots +m_{N-1}{X}^{N-1}$, we denote its coefficient representation as $\mathit{m}=(m_0,m_1,...,m_{N-1})$. For simplicity, we sometimes write m(X) as m throughout the paper. The multiplication of two polynomials $m_1$ and $m_2$ is denoted as $m_1·m_2$, sometimes $m_1{m}_2$ for simplicity. $\odot$ marks the Hadamard product of two vectors.

Table 1. Essential notations and definitions

Notation	Definition
Mathematical sets and spaces
$\mathbb{Z},\mathbb{C}$	Ring of integers, complex numbers
$\mathcal{R}=\mathbb{Z}/({\Phi }_M(X))$	Ring of integer polynomials modulo ${\Phi }_M(X)$
${\mathcal{R}}_q=\mathcal{R}/q\mathcal{R}$	Ring of polynomials modulo both ${\Phi }_M(X)$ and q
Operators and functions
$⟨·,·⟩$	Inner product of vectors
${\Vert ·\Vert }_{\infty }$	Infinity norm
$\lceil ·\rfloor ,\lfloor ·\rfloor ,\lceil ·\rceil$	Rounding, floor, and ceiling operations
$\mathsf{emd},{\mathsf{emd}}^{-1}$	Canonical embedding and its inverse
Ciphertext types
${\mathsf{LWE}}_Q(m)$	LWE ciphertext $(b,\mathit{a})\in {\mathbb{Z}}^{N+1}$ encrypting m with modulus Q
${\mathsf{RLWE}}_Q(m)$	RLWE ciphertext $(b,a)\in {\mathcal{R}}_Q^2$ encrypting polynomial m with modulus Q
${\mathsf{RLWE}}_Q^{\prime }(m)$	Decomposed RLWE ciphertext vector of length d
${\mathsf{RGSW}}_Q(m)$	RGSW ciphertext matrix in ${\mathcal{R}}_Q^{2\times 2d}$ encrypting m
CKKS parameters
N	Ring dimension (degree of ${\Phi }_M(X)$)
q, Q	Ciphertext moduli
h	Hamming weight of secret key
$\sigma$	Standard deviation for error distribution
CKKS operations
$\mathsf{Add},\mathsf{Mult}$	Homomorphic addition and multiplication between two ciphertexts
$\mathsf{cAdd},\mathsf{cMult}$	Homomorphic addition and multiplication between a ciphertext and a plaintext
$\mathsf{Rot},\mathsf{Conj}$	Rotation and conjugation operations
$\mathsf{KS},\mathsf{Relin}$	Key switching and relinearization
$\mathsf{ModRaise},\mathsf{CoeffToSlot},\mathsf{EvalMod},\mathsf{SlotToCoeff}$	Bootstrapping components

Table 1 summarizes the essential notations and definitions used throughout this paper, including mathematical spaces, operators, ciphertext types, parameters, and homomorphic operations.

CKKS scheme

The CKKS scheme (Cheon et al. 2017) enables approximate homomorphic operations on complex and real numbers. Its security is based on the Ring Learning With Error (RLWE) problem. The plaintext space of CKKS is the polynomial ring $m(X)\in R$. Using canonical embedding and approximate scaling, N/2 complex numbers can be mapped to $\mathcal{R}$. Operations on $\mathcal{R}$ are equivalent to element-wise operations on vectors in ${\mathbb{C}}^{N/2}$. Thus, the CKKS scheme can pack N/2 complex numbers into a single polynomial and perform Single Instruction Multiple Data (SIMD) operations on this polynomial. We refer to $m(X)\in \mathcal{R}$ as the plaintext and its corresponding ${\mathbb{C}}^{N/2}$ vector as plaintext slots.

CKKS defines an encoding function $\mathsf{Ecd}(\mathit{z})$ that encodes a vector $\mathit{z}\in {\mathbb{C}}^{N/2}$ of length N/2 into a polynomial $m(X)\in R$, and a decoding function $\mathsf{Dcd}(m)$ that decodes the polynomial m(X) back to the vector $\mathit{z}$.

The Residual Number System (RNS)-based CKKS scheme sets the modulus as $Q_l=q_0·{\prod }_{i=1}^l{q}_i$. To support Number Theoretic Transform (NTT) operations, each $q_i$ must satisfy $q_i=1(mod2N)$, ensuring that modulo $q_i$ contains a 2N-th root of unity. We refer to $0\le l\le L$ as the level of the ciphertext. After each multiplication, the ciphertext modulus changes from $Q_l$ to $Q_{l-1}$, with level l indicating support for l layers of multiplication. The RNS-CKKS scheme achieves higher performance than the original CKKS by avoiding the use of large moduli. The CKKS algorithms are as follows (described in symmetric encryption form):

• $\mathsf{KeyGen}(1^{\lambda }):$ Key generation. Given security parameter $\lambda$, select a ring $\mathcal{R}$, key sparsity coefficient h, integer P, and Gaussian distribution parameter $\sigma$. Choose the key s as a polynomial with Hamming weight h, with coefficients selected from $\{\pm 1,0\}$. Output the private key $\mathsf{sk}=(1,s)$.

• $\mathsf{KSGen}(s^{\prime }):$ Key switching key generation. For $s^{\prime }\in \mathcal{R}$, sample $a^{\prime }\leftarrow {\mathcal{R}}_{P·Q_L}$, $e^{\prime }\leftarrow \mathcal{D}\mathcal{G}({\sigma }^2)$, and output the key switching key $\mathsf{swk}\leftarrow ({\mathsf{swk}}_0,{\mathsf{swk}}_1)\in {\mathcal{R}}_{P·Q_L}^2$, where ${\mathsf{swk}}_1=a^{\prime },{\mathsf{swk}}_0=-a^{\prime }s+e^{\prime }+P·s^{\prime }(modP·Q_L)$.

• ${\mathsf{Enc}}_{\mathsf{sk}}(m):$ Encryption. Sample $a\in {\mathcal{R}}_{Q_L}$, $e\in \mathcal{D}\mathcal{G}({\sigma }^2)$, and output the ciphertext $\mathsf{ct}=(b,a)(mod{Q}_L)$, where $b=-as+e+m$.

• ${\mathsf{Dec}}_{\mathsf{sk}}(ct):$ Decryption. Given $\mathsf{ct}=(b,a)(mod{Q}_L)$, output plaintext $m+e=b+as(mod{Q}_L)$.

• $\mathsf{Add}({\mathsf{ct}}_1,{\mathsf{ct}}_2):$ Homomorphic addition. Compute ${\mathsf{ct}}_{\mathsf{add}}={\mathsf{ct}}_1+{\mathsf{ct}}_2(mod{Q}_l)$.

• $\mathsf{Mult}({\mathsf{ct}}_1,{\mathsf{ct}}_2):$ Homomorphic multiplication. For ${\mathsf{ct}}_1=(b_1,a_1)$, ${\mathsf{ct}}_2=(b_2,a_2)\in {\mathcal{R}}_{Q_l}^2$, compute $${\mathsf{ct}}_{\mathsf{mult}}=(b_1{b}_2,a_1{b}_2+a_2{b}_1,a_1{a}_2)(mod{Q}_l),$$ The resulting ciphertext has three terms, which can be converted back to two terms through relinearization $\mathsf{Relin}$.

• ${\mathsf{KS}}_{\mathsf{swk}}({\mathsf{ct}}^{\prime }):$ Key switching. For a ciphertext ${\mathsf{ct}}^{\prime }=(b,a)\in {\mathcal{R}}_{Q_l}^2$ encrypted under $s^{\prime }$, and key switching key $\mathsf{swk}=({\mathsf{swk}}_0,{\mathsf{swk}}_1)\leftarrow \mathsf{KSGen}(s^{\prime })$, compute and output $$\begin{array}{c}\hfill {\mathsf{ct}}_{\mathsf{KS}}=\left(b,+,\lceil ,\frac{a·{\mathsf{swk}}_0}{P},\rfloor ,,,\lceil ,\frac{a·{\mathsf{swk}}_1}{P},\rfloor \right)(mod{Q}_l),\end{array}$$ where ${\mathsf{ct}}_{\mathsf{KS}}$ is a ciphertext encrypted under s.

• ${\mathsf{Relin}}_{\mathsf{rlk}}({\mathsf{ct}}_{\mathsf{mult}}):$ Relinearization. For a ciphertext ${\mathsf{ct}}_{\mathsf{mult}}=(d_0,d_1,d_2)$ resulting from multiplication, and relinearization key $\mathsf{rlk}=\mathsf{KSGen}(s^2)$, compute and output ${\mathsf{ct}}_{\mathsf{relin}}=(d_0,d_1)+{\mathsf{KS}}_{\mathsf{rlk}}((0,d_2))$.

• $\mathsf{cAdd}({\mathsf{ct}}_1,\mathit{a}):$ Ciphertext-plaintext addition. For a ciphertext ${\mathsf{ct}}_1=(b_1,a_1)$ and a plaintext vector $\mathit{a}$, output ${\mathsf{ct}}_{\mathsf{cadd}}=(b_1+\mathsf{Ecd}(\mathit{a}),a_1)$.

• $\mathsf{cMult}({\mathsf{ct}}_1,\mathit{a}):$ Ciphertext-plaintext multiplication. For a ciphertext ${\mathsf{ct}}_1=(b_1,a_1)$ and a plaintext vector $\mathit{a}$, compute $m=\mathsf{Ecd}(\mathit{a})$, and output ${\mathsf{ct}}_{\mathsf{cmult}}=(b_1·m,a_1·m)$.

• ${\mathsf{Rot}}_k(\mathsf{ct}):$ Homomorphic rotation. For ciphertext $\mathsf{ct}=(b,a)$, the rotation operation shifts elements in its plaintext slots left by k positions. Define an automorphism ${\phi }_k:X\to X^{5^k}$, with rotation key ${\mathsf{rk}}_k=\mathsf{KSGen}({\phi }_k(s))$, compute and output ${\mathsf{ct}}_{\mathsf{rk}}={\mathsf{KS}}_{{\mathsf{rk}}_k}({\phi }_k(b),{\phi }_k(a))$.

• $\mathsf{Conj}(\mathsf{ct}):$ Homomorphic conjugation. For ciphertext $\mathsf{ct}=(b,a)$, the conjugation operation takes the complex conjugate of elements in its plaintext slots. Define an automorphism ${\phi }^{\prime }:X\to X^{-1}$, with conjugation key $\mathsf{cjk}=\mathsf{KSGen}({\phi }^{\prime }(s))$, compute and output ${\mathsf{ct}}_{\mathsf{conj}}={\mathsf{KS}}_{\mathsf{cjk}}({\phi }^{\prime }(b),{\phi }^{\prime }(a))$.

• $\mathsf{RS}(\mathsf{ct}):$ Rescaling. For a ciphertext $\mathsf{ct}\in {\mathcal{R}}_{Q_l}^2$ at level l, output ${\mathsf{ct}}_{\mathsf{RS}}=\lceil p_l^{-1}\mathsf{ct}\rfloor (mod{Q}_{l-1})$.

To implement the bootstrapping operation for CKKS, the algorithm additionally defines a rotation operation ${\mathsf{Rot}}_k(\mathsf{ct})$ and a conjugation operation $\mathsf{Conj}(\mathsf{ct})$. For a ciphertext $\mathsf{ct}$ with plaintext slots $\mathit{z}=(z_0,...,z_{N/2-1})$, executing ${\mathsf{Rot}}_k(\mathsf{ct})$ results in a ciphertext with corresponding plaintext slots ${\rho }_k(\mathit{z})=(z_k,z_{k+1},...,z_{N/2-1},z_0,...,z_{k-1})$. Executing $\mathsf{Conj}(\mathsf{ct})$ results in a ciphertext with corresponding plaintext slots $\overline{\mathit{z}}=(\overline{z_0},..,\overline{z_{N/2-1}})$.

The rotation algorithm can be used to define a multiplication between a plaintext matrix and a ciphertext vector. For a matrix $\mathit{A}$ of size $N/2\times N/2$, to perform matrix–vector multiplication with a ciphertext $\mathsf{ct}$,$$\begin{array}{c}\hfill \mathit{A}=\left[\begin{array}{cccc}{A}_{0,0}& A_{0,1}& \cdots & A_{0,N/2-1}\\ A_{1,0}& A_{1,1}& \cdots & A_{1,N/2-1}\\ ⋮& ⋮& \ddots & ⋮\\ A_{N/2-1,0}& A_{N/2-1,1}& \cdots & A_{N/2-1,N/2-1}\end{array}\right],\end{array}$$Let the diagonal elements of $\mathit{A}$ be ${\mathit{a}}_i={\{A_{0,i},A_{1,i+1},...,A_{N/2-1,i-1}\}}_{0\le i\le N/2-1}$. For a vector $\mathit{z}$, we have $\mathit{A}·\mathit{z}={\sum }_{0\le i<N/2}({\mathit{a}}_i\odot {\rho }_i(\mathit{z}))$.

Based on the plaintext algorithm, we can derive the matrix–vector multiplication for ciphertext $\mathsf{ct}$, as shown in Algorithm 1:

[See PDF for image]

Algorithm 1

Matrix-Vector Ciphertext Multiplication $\mathsf{Matmul}(\mathit{A},\mathsf{ct})$

The $\mathsf{Matmul}$ algorithm facilitates the computation of a matrix–vector product between a plaintext matrix and a ciphertext $\mathsf{ct}$ (containing a plaintext vector). This algorithm proves particularly useful in bootstrapping, as it enables the linear transformation of ciphertext coefficients into slots.

General approach and optimization of CKKS bootstrapping

General bootstrapping framework for CKKS

[See PDF for image]

Fig. 1

CKKS bootstrapping roadmap

A year after the introduction of the CKKS scheme, Cheon et al. (2018) proposed a general framework for CKKS bootstrapping. This structure remains the mainstream approach for CKKS bootstrapping, with most subsequent work based on this framework (Han and Ki 2020; Chen et al. 2019; Bossuat et al. 2021; Lee et al. 2021b, 2020, 2022d; Jutla and Manohar 2022). The overall development roadmap is illustrated in Fig. 1.

The CKKS bootstrapping process primarily consists of four steps: Modulus Raising ($\mathsf{ModRaise}$), Homomorphic Encoding ($\mathsf{CoeffToSlot}$), Homomorphic Modular Reduction ($\mathsf{EvalMod}$), and Homomorphic Decoding ($\mathsf{SlotToCoeff}$). The relationship between these four steps is shown in the following equation:

1

$$\begin{array}{c}\hfill \begin{array}{cccc}\hfill m(modq)& \stackrel{\mathsf{ModRaise}}{\to }m+qI(modQ)\hfill & \hfill \stackrel{\mathsf{CoeffToSlot}}{\to }& {(m+qI)}^{\ast }\hfill \\ \hfill & & \hfill \downarrow \\ \hfill m(mod{Q}^{\prime })& \stackrel{\mathsf{SlotToCoeff}}{\leftarrow }{(m)}^{\ast }\hfill & \hfill \stackrel{\mathsf{EvalMod}}{\leftarrow }& {(m+qI)}^{\ast }\hfill \end{array}\end{array}$$Since the decryption operation in CKKS cannot eliminate noise, CKKS bootstrapping expands the modulus to provide the ciphertext with more layers, thereby increasing the number of computations. The Modulus Raising operation ($\mathsf{ModRaise}$) can directly expand the modulus of $m(X)={[⟨\mathsf{sk},\mathsf{ct}⟩]}_q$ to Q, yielding $t(X)={[⟨\mathsf{sk},\mathsf{ct}⟩]}_Q=m(X)+I(X)·q$. Then, a homomorphic modular reduction ($\mathsf{EvalMod}$) operation is applied to eliminate the $I(X)·q$ term. As the modular reduction operation is performed on coefficients, while homomorphic addition and multiplication operations target plaintext slots, it is necessary to first place the coefficients into plaintext slots before computation, i.e., execute a homomorphic encoding process ($\mathsf{CoeffToSlot}$). After the homomorphic modular reduction process, a homomorphic decoding ($\mathsf{SlotToCoeff}$) is performed to restore the plaintext slots. The following sections will elaborate on these four algorithms.

Modulus Raising ($\mathsf{ModRaise}$): For a ciphertext $\mathsf{ct}$ containing plaintext $m(X)={[⟨\mathsf{ct},\mathsf{sk}⟩]}_q$, we have $t(X)=⟨\mathsf{ct},\mathsf{sk}⟩=qI(X)+m(X)\equiv m(X)modq$, where ${\Vert I(X)\Vert }_{\infty }<K=O(\sqrt{h})$. Here, h is the Hamming weight of $\mathsf{s}k$ (the number of 1 s in $\mathsf{sk}$). Choosing a sufficiently large modulus Q, we obtain ${[t(X)]}_Q=t(X)=t_0+t_{1}X+\cdots +t_{N-1}{X}^{N-1}$.

Remark 1

Sparse Key. Generally, in homomorphic encryption, the coefficients of the private key $\mathsf{sk}$ are selected from $(-1,0,1)$ with equal probability. For an N-bit key, the Hamming weight h is likely to be 2/3N; such keys are called dense keys. However, in schemes requiring bootstrapping, to minimize $K=O(\sqrt{h})$, h is set to [64, 192]. This sparse key selection strategy leads to reduced security (Son and Cheon 2019), necessitating a larger N to ensure security. Keys selected using this strategy are termed sparse keys.

Homomorphic Encoding ($\mathsf{CoeffToSlot}$): In the CKKS bootstrapping process, a modular reduction operation on polynomial coefficients is required. The approach is to approximate the modular function using homomorphic addition and multiplication, which operate on numbers in plaintext slots. Therefore, it is necessary to place the coefficients into plaintext slots, effectively performing a homomorphic ciphertext encoding operation. However, a challenge arises: there are N polynomial coefficients, but only N/2 plaintext slots. A straightforward solution is to distribute the coefficients of $t(X)=t_0+t_{1}X+\cdots +t_{N-1}{X}^{N-1}$ into two ciphertexts with plaintext slots ${\mathit{t}}_0=(t_0,...,t_{\frac{N}{2}-1})$ and ${\mathit{t}}_1=(t_{\frac{N}{2}},...,t_{N-1})$.

Directly executing an encoding function on the ciphertext would be complex. However, observing that encoding and decoding are essentially vector linear transformations, we can represent this linear transformation as a multiplication between a plaintext matrix and a ciphertext vector. Specifically:

Let $\zeta$ be a primitive N-th root of unity for the M-th cyclotomic polynomial ${\Phi }_M(X)=X^N+1$, and define ${\zeta }_j={\zeta }^{5^j},0\le j<N/2$. Then $\left\{{\zeta }_j,,,\overline{{\zeta }_j},:,0,\le ,j,<,N,/,2\right\}$ forms the set of N roots of unity. The transformation relationship between a vector $\mathit{z}\in {\mathbb{C}}^{N/2}$ and a polynomial $m(X)\in \mathcal{R}$ can be expressed as: $m({\zeta }_j)=z_j,\overline{m({\zeta }_j)}=m(\overline{{\zeta }_j})=\overline{z_j}$. Therefore, we can construct a matrix $\mathit{U}\in {\mathbb{C}}^{N/2\times N}$:

2

$$\begin{array}{c}\hfill \mathit{U}=\left[\begin{array}{ccccc}1& {\zeta }_0& {\zeta }_0^2& \cdots & {\zeta }_0^{N-1}\\ 1& {\zeta }_1& {\zeta }_1^2& \cdots & {\zeta }_1^{N-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\zeta }_{\frac{N}{2}-1}& {\zeta }_{\frac{N}{2}-1}^2& \cdots & {\zeta }_{\frac{N}{2}-1}^{N-1}\end{array}\right]\in {\mathbb{C}}^{\frac{N}{2}\times N},\end{array}$$Thus, the transformation from $\mathit{m}$ to $\mathit{z}$ can be written as $\mathit{z}=\mathit{U}·\mathit{m}\in {\mathbb{C}}^{N/2}$. From this equation, we can derive $\mathit{m}={\mathit{U}}^{-1}·\mathit{z}$. However, ${\mathit{U}}^{-1}$ is generally not computed directly. Utilizing the Vandermonde determinant form, we extend $\mathit{U}$ by defining $\mathsf{CRT}=\left[\begin{array}{cc}& \mathit{U}\hfill \\ \hfill & \overline{\mathit{U}}\hfill \end{array},\right]$. Consequently, $(\mathit{z},\overline{\mathit{z}})=\mathsf{CRT}·\mathit{m}$, and thus $\mathit{m}={\mathsf{CRT}}^{-1}·(\mathit{z},\overline{\mathit{z}})$. Here, ${\mathsf{CRT}}^{-1}=\frac{1}{N}{\overline{\mathsf{CRT}}}^T=\frac{1}{N}({\overline{\mathit{U}}}^T,{\mathit{U}}^T)$. Therefore, this inverse transformation can be expressed as: $\mathit{m}=\frac{1}{N}({\overline{\mathit{U}}}^T·\mathit{z}+{\mathit{U}}^T·\overline{\mathit{z}})$.

In homomorphic encoding, the polynomial coefficients are $\mathit{t}=(t_0,...,t_{N-1})$, where $\mathit{t}$ is an N-dimensional vector. Since the encoding can only encode $\frac{N}{2}$ numbers into an N-degree polynomial, it is necessary to encode $\mathit{t}$ into two ciphertexts with plaintext slots ${\mathit{t}}_0=(t_0,...,t_{\frac{N}{2}-1})$ and ${\mathit{t}}_1=(t_{\frac{N}{2}},...,t_{N-1})$ respectively. Specifically, we can split $\mathit{U}$ into two matrices $\mathit{U}=[{\mathit{U}}_0|{\mathit{U}}_1]$:

3

$$\begin{array}{c}\hfill {\mathit{U}}_0=\left[\begin{array}{cccc}1& {\zeta }_0& \dots & {\zeta }_0^{\frac{N}{2}-1}\\ 1& {\zeta }_1& \dots & {\zeta }_1^{\frac{N}{2}-1}\\ ⋮& ⋮& \ddots & ⋮\\ 1& {\zeta }_{\frac{N}{2}-1}& \dots & {\zeta }_{\frac{N}{2}-1}^{\frac{N}{2}-1}\end{array}\right],{\mathit{U}}_1=\left[\begin{array}{cccc}{\zeta }_0^{\frac{N}{2}}& {\zeta }_0^{\frac{N}{2}+1}& \dots & {\zeta }_0^{N-1}\\ {\zeta }_1^{\frac{N}{2}}& {\zeta }_1^{\frac{N}{2}+1}& \dots & {\zeta }_1^{N-1}\\ ⋮& ⋮& \ddots & ⋮\\ {\zeta }_{\frac{N}{2}-1}^{\frac{N}{2}}& {\zeta }_{\frac{N}{2}-1}^{\frac{N}{2}+1}& \dots & {\zeta }_{\frac{N}{2}-1}^{N-1}\end{array}\right]\in {\mathbb{C}}^{\frac{N}{2}\times \frac{N}{2}}\end{array}$$We can compute ${\mathit{t}}_k=\frac{1}{N}\left({\overline{U_k}}^T,·,\mathit{z},+,U_k^T,·,\overline{\mathit{z}}\right),k=0,1$, where $\mathit{z}\in {\mathbb{C}}^{N/2}$ represents the plaintext slots corresponding to the polynomial t(x). This step can be constructed using the aforementioned homomorphic matrix multiplication and conjugate operations. By transforming the above algorithm into a ciphertext algorithm, we obtain the specific algorithm for homomorphic encoding: compute ${\mathsf{ct}}_{\mathsf{conj}}=\mathsf{Conj}(\mathsf{ct})$, ${\mathsf{ct}}_0=1/N(\mathsf{Matmul}({\overline{{\mathit{U}}_0}}^T,\mathsf{ct})+\mathsf{Matmul}({\mathit{U}}_0^T,{\mathsf{ct}}_{\mathsf{conj}}))$. We can obtain that ${\mathsf{ct}}_0$ is an encryption of ${\mathit{t}}_0$, and similarly, ${\mathsf{ct}}_1$ is an encryption of ${\mathit{t}}_1$.

Homomorphic Modular Reduction ($\mathsf{EvalMod}$): In the modulus raising $\mathsf{ModRaise}$, we obtained $t(X)=m(X)+I(X)q$, where ${\Vert I(X)\Vert }_{\infty }<K$. The modular reduction to be performed on the coefficients of $t(X)=t_0+t_{1}X+\cdots +t_{N-1}{X}^{N-1}$ is $F(t_i)={[t_i]}_q=m_i$, with the modular operation interval being $[-Kq,Kq]$. Cheon et al. (2018) observed that this modular function, like trigonometric functions, is periodic with period q, and the approximation between trigonometric functions and the modular function is very high near the zero point. Therefore, F(t) can be approximated by constructing a trigonometric function $S(t)=\frac{q}{2\pi }sin\left(\frac{2\pi t}{q}\right)$ with period q. The error between F(t) and S(t) is $O(q{ϵ}^3)$, where $ϵ=\frac{|m|}{q}$.

Since homomorphic operations are addition and multiplication, it is necessary to expand S(t) into a polynomial using Taylor series. The higher the degree of this polynomial, the smaller the error with S(t). Directly approximating the sine function $\frac{q}{2\pi }sin\left(\frac{2\pi t}{q}\right)$using Taylor expansion requires computing a Taylor polynomial of order Kq to achieve a good approximation effect. This is because after a d-th order Taylor expansion of $S(t)=\frac{q}{2\pi }sin\left(\frac{2\pi t}{q}\right)$, we obtain an O(d) order polynomial:

4

$$\begin{array}{c}\hfill S^{\prime }(t)=\frac{q}{2\pi }\sum _{j=0}^{d-1}\frac{{(-1)}^j}{(2j+1)!}{\left(\frac{2\pi t}{q}\right)}^{2j+1},\end{array}$$Since $|t|<Kq$, we have $|S(t)-S^{\prime }(t)|<\frac{q}{2\pi }·\frac{1}{(2d+1)!}{(2\pi K)}^{2d+1}$. Using Stirling’s formula ($n!\approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$), we can derive for $|S(t)-S^{\prime }(t)|$:

5

$$\begin{array}{c}\hfill \frac{q}{2\pi }·\frac{1}{(2d+1)!}{(2\pi K)}^{2d+1}\approx \frac{q}{2\pi }·\frac{{(2\pi eK)}^{2d+1}}{\sqrt{2\pi (2d+1)}·{(2d+1)}^{2d+1}},\end{array}$$Therefore, when the order reaches $d=O(Kq)$, the error $|S(t)-S^{\prime }(t)|$ becomes small enough to be negligible. Running this O(Kq)-order polynomial $S^{\prime }(t)$ on the two ciphertexts ${\mathsf{ct}}_0,{\mathsf{ct}}_1$ respectively, we obtain ${\mathsf{ct}}_0,{\mathsf{ct}}_1$ encrypting ${\mathit{z}}_0=(m_0,...,m_{N/2-1})$ and ${\mathit{z}}_1=(m_{N/2},...,m_{N-1})$ respectively.

Homomorphic Decoding ($\mathsf{SlotToCoeff}$): Homomorphic decoding is the inverse operation of homomorphic encoding. It is necessary to transform two ciphertexts ${\mathsf{ct}}_0,{\mathsf{ct}}_1$ with plaintext slots ${\mathit{z}}_0=(m_0,...,m_{N/2-1})$ and ${\mathit{z}}_1=(m_{N/2},...,m_{N-1})$ back into an encryption of the polynomial $m(X)=m_0+m_{1}X+\cdots +m_{N-1}{X}^{N-1}$. This means placing the numbers from the two plaintext slots back into the coefficients of one polynomial. This step is also done through matrix multiplication, specifically: $\mathit{z}={\mathit{U}}_0·{\mathit{z}}_0+{\mathit{U}}_1·{\mathit{z}}_1$.

It can be observed that the bootstrapping in CKKS (Cheon et al. 2018) operates directly on ciphertexts, such as performing linear transformations on ciphertexts and polynomial operations on ciphertexts. It does not require the computation of a decryption circuit on the ciphertext, thus eliminating the need for a bootstrapping key. Compared to the bootstrapping proposed by Gentry (2009), its main advantages are: firstly, it does not require a bootstrapping key, its security is not based on the circular security assumption, and it reduces communication overhead; secondly, its computational complexity depends on the order of the approximating polynomial for the modular function, which offers significant room for optimization.

The optimization improvement routes for CKKS bootstrapping operations are illustrated in Fig. 1, and can be mainly categorized into three types:

• Optimizations for the modular operation primarily target the $\mathsf{EvalMod}$ operation. Since the precision of CKKS bootstrapping is mainly related to the precision of homomorphic modular reduction, optimizations in this direction have achieved the highest bootstrapping precision.

• Optimizations for homomorphic encoding and decoding. The encoding and decoding operations are the most time-consuming parts of the entire CKKS bootstrapping process. Therefore, optimizations in this area can enable the bootstrapping scheme to achieve higher throughput.

• Employing alternative methods for CKKS bootstrapping, such as using FHEW blind rotation for noise refreshing, or replacing homomorphic modular reduction with homomorphic computation of modular terms.

It is important to note that while the above two categories of optimizations operate within this four-step framework, the third category represents fundamentally different approaches to CKKS bootstrapping. These alternative methods, such as FHEW blind rotation and meta-bootstrapping, achieve the bootstrapping objective through entirely different mathematical and algorithmic paradigms that do not align with the traditional four-step process. We discuss these alternative approaches separately in Sect. 4 to highlight their distinct characteristics and trade-offs.

Optimizations for homomorphic modular reduction

Cheon et al. (2018) observed that the approximating function is a trigonometric function, allowing for effective utilization of double-angle formulas and Euler’s formula properties. Leveraging CKKS’s ability to compute complex numbers, they calculated $\frac{q}{2\pi }sin\left(\frac{2\pi t}{q}\right)$ using the double-angle formula. Specifically, $\frac{q}{2\pi }sin\left(\frac{2\pi t}{q}\right)=\frac{q}{4\pi }\left(exp,\left(\frac{2\pi it}{q}\right),-,exp,\left(\frac{-2\pi it}{q}\right)\right),exp\left(\frac{2\pi it}{q}\right)=exp{\left(\frac{2\pi it}{2q}\right)}^2$. Therefore, by computing $P_0(t)={\sum }_{k=0}^{d_0}\frac{1}{k!}{\left(\frac{2\pi it}{2^r·q}\right)}^k\approx exp\left(\frac{2\pi it}{2^r·q}\right)$, and then $P_i(t)=P_{i-1}{(t)}^2$, one obtains $P_r(t)\approx exp\left(\frac{2\pi it}{q}\right)$. Since $P_0(t)$ has a small range, it can be approximated using a Taylor series expansion of order $d_0=O(1)$, followed by $r=O(log\mathit{Kq})$ squaring operations, resulting in a total of $O(log\mathit{Kq})$ multiplication layers. Cheon et al. (2018) achieved a remaining precision of 20 bits after bootstrapping.

Chen et al. (2019) recognized that the double-angle formula introduces larger errors with each iteration. They proposed using Chebyshev interpolation to directly approximate $\frac{q}{2\pi }sin\left(\frac{2\pi t}{q}\right)$ in the $[-Kq,Kq]$ interval, reducing both the number of multiplications and the error in the approximation. Their work focused on decreasing the number of multiplication layers in polynomial approximation, resulting in an overall efficiency improvement of about 50 times compared to Cheon’s original approach (Cheon et al. 2018), while maintaining a post-bootstrapping precision of 20 bits.

Han and Ki (2020) noted that approximating ${[t]}_q$ over the entire $[-Kq,Kq]$ interval is unnecessary since $m\ll q$. They proposed Chebyshev interpolation of $\frac{q}{2\pi }sin\left(\frac{2\pi t}{q}\right)$ only near multiples of q, requiring fewer multiplications. This method achieved a twofold efficiency improvement over Chen’s work Chen et al. (2019). Moreover, Han and Ki (2020) was the first to implement an RNS-based CKKS bootstrapping circuit. However, their precision remained relatively low, not exceeding 20 bits.

The aforementioned works focused on optimizing the approximation of the $\frac{q}{2\pi }sin\left(\frac{2\pi t}{q}\right)$ function, which inherently has an $O(q{ϵ}^3)$ error compared to ${[t]}_q$. Subsequent works (Jutla and Manohar 2020; Lee et al. 2022e, 2020; Jutla and Manohar 2022; Lee et al. 2021b) aimed to circumvent this error by directly approximating ${[t]}_q$.

Recent works by Lee et al. (2020, 2021b) and Jutla and Manohar (2020) employed algorithmic search methods to directly approximate the modular function. Lee et al. (2020) used a least squares algorithm for approximation, while Jutla and Manohar (2020) utilized Lagrange Interpolation to approximate the Mod function. However, these methods resulted in large coefficients for the approximating polynomials, which reduced the precision of multiplication operations, limiting the achievable bootstrapping precision.

Lee et al. (2021b) employed inverse trigonometric functions to approximate the modular function, using the Remez method to effectively reduce polynomial coefficient sizes. This approach achieved a precision of 32.6 bits. Their subsequent work Lee et al. (2022e) further optimized efficiency by using Baby-Step Giant-Step ($\mathsf{BSGS}$) operations for polynomial computation optimization, achieving fewer multiplications. They also delayed relinearization ($\mathsf{Relin}$) and rescaling ($\mathsf{Rescale}$) to reduce their frequency during polynomial operations, resulting in higher efficiency. By approximating a 1625-degree modular function, they successfully increased precision to 100 bits.

Jutla and Manohar (2022) designed a sine function sequence to better approximate ${[t]}_q$. Specifically, while the Taylor expansion shows an $O(q{ϵ}^3)$ error between $\frac{q}{2\pi }sin\left(\frac{2\pi t}{q}\right)$ and ${[t]}_q$, they discovered that approximating ${[t]}_q$ with the sine function sequence $4/3sint-1/6sin2t$ results in only $O({ϵ}^5)$ error. This improvement allowed their bootstrapping scheme to also achieve 100-bit precision.

In a recent work, Kim et al. (2022) proposed a new CKKS bootstrapping algorithm using $\mathsf{EvalRound}$ instead of the original $\mathsf{EvalMod}$ method. While the original CKKS bootstrapping process used the $\mathsf{EvalMod}$ function to perform homomorphic modular reduction on $(m+qI)$ (by approximating the modular function with a polynomial) to obtain (m), $\mathsf{EvalRound}$ obtains (qI) from $(m+qI)$, effectively rounding to multiples of I. This approach requires smaller polynomial coefficients and allows for smaller scaling factors. The result is a reduction in the number of levels consumed by the bootstrapping step while maintaining a certain precision, thereby increasing the computational capacity of the ciphertext after bootstrapping.

Optimizations for homomorphic encoding and decoding (linear transformations)

In homomorphic encoding ($\mathsf{CoeffToSlot}$) and decoding ($\mathsf{SlotToCoeff}$), directly using matrix multiplication as shown in Algorithm 1 requires O(N) rotation keys ${({\mathsf{rk}}_i)}_{0\le i\le N/2-1}$ and O(N) rotation operations. To address this, Cheon et al. (2018) employed the $\mathsf{BSGS}$ method proposed by Halevi and Shoup (2014, 2021) to perform multiplication between a plaintext matrix and a ciphertext vector. $\mathsf{BSGS}$ reduces both the number of rotation keys and rotation operations to $O(\sqrt{N})$, as shown in Algorithm 2:

[See PDF for image]

Algorithm 2

Baby-Step Giant-Step Matrix-Vector Multiplication ${\mathsf{Matmul}}_{\mathsf{BSGS}}(\mathit{A},\mathsf{ct})$

The matrix multiplication constructed using $\mathsf{BSGS}$ reduces the number of rotations in homomorphic encoding and decoding to $O(\sqrt{N})$, requiring only one multiplication layer.

One disadvantage of using matrix multiplication is that homomorphic encoding requires two ciphertexts to store $N/2\times 2$ plaintext slots for N coefficients, with all subsequent operations performed on these two ciphertexts. An optimization in this regard is to use sparsely packed ciphertexts, utilizing only n out of N/2 plaintext slots, where n|N/2. Sparse packing allows all coefficients to be placed in a single ciphertext during homomorphic encoding ($\mathsf{CoeffToSlot}$), avoiding the generation of two ciphertext terms and reducing the total number of rotations from $O(\sqrt{N})$ to $O(\sqrt{n})$, thereby increasing the overall scheme’s performance.

Chen et al. (2019) proposed using FFT butterfly operations for homomorphic encoding, requiring $O(log(N))$ rotations and $O(log(N))$ multiplication layers. This approach effectively reduces the number of rotations at the cost of consuming more multiplication layers, representing a trade-off between multiplication layers and rotation operations.

Currently, in CKKS bootstrapping schemes, the matrix multiplication method proposed by Cheon et al. (2018) is widely used for constructing homomorphic encoding and decoding, as it consumes only one multiplication layer. The number of remaining multiplication layers after bootstrapping is an important indicator of bootstrapping performance.

Bossuat et al. (2021) observed that when using $\mathsf{BSGS}$ for matrix multiplication in linear transformations, the most time-consuming steps are the $O(\sqrt{N})$ rotation operations $(\mathsf{Rot})$ and conjugation operations $(\mathsf{Conj})$, both constructed using the key switching method $(\mathsf{KS})$. Building upon the Hoisting algorithm proposed by Halevi and Shoup (2014, 2021) to accelerate $\mathsf{KS}$, Bossuat et al. (2021) improved it to a Double Hoisting method, reducing the complexity of the $\mathsf{KS}$ algorithm itself and achieving a twofold efficiency improvement in overall linear transformations.

Alternative approaches to CKKS bootstrapping

Kim et al. (2024a) and Yang et al. (2021) utilized the blind rotation operation (Chillotti et al. 2016, 2017, 2019) from FHEW-type fully homomorphic encryption (Ducas and Micciancio 2015; Chillotti et al. 2016) to perform bootstrapping for CKKS. Bae et al. (2022) optimized bootstrapping precision by recursively employing bootstrapping.

RGSW-type ciphertexts and FHEW blind rotation

FHEW blind rotation primarily targets Boolean circuits, with security based on the Learning With Error (LWE) problem. It focuses on LWE-type ciphertexts $\mathsf{ct}=(b,\mathit{a})\in {\mathbb{Z}}^{N+1}$, where $b=⟨\mathbf{a},\mathbf{s}⟩+m+e(modQ),m\in \mathbb{Z}$. For convenience, we denote this ciphertext as ${\mathsf{LWE}}_Q(m)$. In contrast, BGV/BFV/CKKS security is based on the Ring Learning With Error (RLWE) problem, employing an encoding function to transform vectors into polynomials, then encrypting them as RLWE-type ciphertexts $\mathsf{ct}=(b,a)\in {\mathcal{R}}_Q^2$, where $b=as+m+e,m\in \mathcal{R}$. We denote this ciphertext as ${\mathsf{RLWE}}_Q(m)$.

A key feature of FHEW blind rotation is its use of RGSW ciphertexts (Gentry et al. 2013) to encrypt the private key s as a bootstrapping key, enabling blind rotation operations on ciphertexts. Blind rotation can transform an LWE-type ciphertext ${\mathsf{LWE}}_{2N}(u)$ into ${\mathsf{RLWE}}_Q(f(X)·X^u)$, where $f(X)=f_0+f_{1}X+\cdots +f_{N-1}{X}^{N-1}$. We now elaborate on RGSW and blind rotation.

RGSW Ciphertexts: First, define a decomposition base $\mathit{g}=(g_0,...,g_{d-1})$. For a polynomial $t\in {\mathcal{R}}_q$, decompose it using $\mathit{g}$ into $(t_0,...,t_{d-1})$, satisfying $t={\sum }_{i=0}^{d-1}{g}_i·t_i$. Based on this decomposition property, we can define ${\mathsf{RLWE}}^{\prime }$ and $\mathsf{RGSW}$ ciphertexts:

6

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill {\mathsf{RLWE}}_Q^{\prime }(m)& =\left({\mathsf{RLWE}}_Q,(g_0·m),,,{\mathsf{RLWE}}_Q,(g_1·m),,,.,.,.,,,{\mathsf{RLWE}}_Q,(g_{d-1}·m)\right)\in {\mathcal{R}}_Q^{2d},\hfill \\ \hfill {\mathsf{RGSW}}_Q(m)& =\left({\mathsf{RLWE}}^{\prime },(m),,,{\mathsf{RLWE}}^{\prime },(s·m)\right)\in {\mathcal{R}}_Q^{2\times 2d},\hfill \end{array}\end{array}$$External Product Operation of RGSW: Define the external product operator $\times$ between a polynomial and ${\mathsf{RLWE}}^{\prime }$ as ${\mathcal{R}}_q\times {\mathsf{RLWE}}^{\prime }\to \mathsf{RLWE}$, specifically:

7

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill t\times {\mathsf{RLWE}}_Q^{\prime }(m)& =⟨(t_0,...,t_{d-1},({\mathsf{RLWE}}_Q(g_0·m),{\mathsf{RLWE}}_Q(g_1·m),...,{\mathsf{RLWE}}_Q(g_{d-1}·m)⟩,\hfill \\ \hfill & =\sum _{i=0}^{d-1}{t}_i·{\mathsf{RLWE}}_Q(g_i·m)={\mathsf{RLWE}}_Q\left(\sum _{i=0}^{d-1},g_i,·,t_i,·,m\right)={\mathsf{RLWE}}_Q(t·m);\hfill \\ \hfill \end{array}\end{array}$$Similarly, we can define the external product operation between $\mathsf{RLWE}$ and $\mathsf{RGSW}$ as $\mathsf{RLWE}\times \mathsf{RGSW}\to \mathsf{RLWE}$:

8

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill {\mathsf{RLWE}}_Q(m_1)\times {\mathsf{RGSW}}_Q(m_2)& =(b_1,a_1)\times ({\mathsf{RLWE}}_Q^{\prime }(m_2),{\mathsf{RLWE}}_Q^{\prime }(s·m_2)\hfill \\ \hfill & =b_1\times {\mathsf{RLWE}}_Q^{\prime }(m_2)+a_1\times {\mathsf{RLWE}}_Q^{\prime }(s·m_2)\hfill \\ \hfill & ={\mathsf{RLWE}}_Q(b_1·m_2+a_1·s·m_2)\hfill \\ \hfill & ={\mathsf{RLWE}}_Q(m_1·m_2+e_1·m_2);\hfill \end{array}\end{array}$$By ensuring $m_2$ is sufficiently small, we can approximate ${\mathsf{RLWE}}_Q(m_1)\times {\mathsf{RGSW}}_Q(m_2)\approx \mathsf{RLWE}(m_1·m_2)$.

Blind Rotation Algorithm: Leveraging the property of the external product $\mathsf{RLWE}\times \mathsf{RGSW}=\mathsf{RLWE}$, we can apply it to perform blind rotation on $\mathsf{RLWE}$ ciphertexts. Specifically, we first define the blind rotation key $\mathsf{brk}={\left\{{\mathsf{RGSW}}_Q,\left(s_i^{+}\right),,,{\mathsf{RGSW}}_Q,\left(s_i^{-}\right)\right\}}_{i\in [0,N-1]}$, where

9

$$\begin{array}{c}\hfill \left\{\begin{array}{cc}{s}_i^{+}=1,\hfill & \text{if}{s}_i=1\hfill \\ s_i^{+}=0,\hfill & \text{otherwise}\hfill \end{array},,,,\left\{\begin{array}{cc}{s}_i^{-}=1,\hfill & \text{if}{s}_i=-1\hfill \\ s_i^{-}=0,\hfill & \text{otherwise}\hfill \end{array}\right)\right)\end{array}$$Let ${\mathsf{LWE}}_Q(u)=(b,\mathit{a})$, $f=f_0+f_{1}X+\cdots +f_{N-1}{X}^{N-1}$, and define an initial value $\mathsf{ACC}={\mathsf{RLWE}}_Q(f·X^b)$. By employing the external product for accumulation operations, we can obtain ${\mathsf{RLWE}}_Q(f·X^{b+\sum a_i{s}_i})={\mathsf{RLWE}}_Q(f·X^u)$. Specifically, each accumulation operation yields $\mathsf{RGSW}(X^{a_i·s_i})=\mathsf{RGSW}(1)+(X^{a_i}-1)·\mathsf{RGSW}(s_i^{+})+(x^{-a_i}-1)\mathsf{RGSW}(s_i^{-})$. By computing $\mathsf{ACC}=\mathsf{ACC}\times \mathsf{RGSW}(X^{a_i·s_i})$, we obtain $\mathsf{ACC}=\mathsf{RLWE}(f·X^{b+\sum a_i·s_i})=\mathsf{RLWE}(f·X^u)$. The specific algorithm for blind rotation is as follows:

[See PDF for image]

Algorithm 3

Blind Rotation $\mathsf{BlindRotate}({\mathsf{LWE}}_{2N}(u),\mathsf{brk},f)$

Upon completion of the algorithm, we obtain $\mathsf{ACC}={\mathsf{RLWE}}_Q(f·X^u)={\mathsf{RLWE}}_Q(f_0{X}^u+f_1{X}^{u+1}+\cdots +f_{N-u}{X}^N+\cdots +f_{N-1}{X}^{N-1+u})$. Given that in $\mathcal{R}=Z[X]/X^N+1$, $X^N=-1$, the constant term of the ciphertext in $\mathsf{ACC}$ is $-f_{N-u}$. The $\mathsf{Extract}$ method proposed by Chen et al. (2021b) can be employed to extract the coefficient of the constant term, yielding ${\mathsf{LWE}}_Q(-f_{N-u})$. This demonstrates that a function can be computed during the blind rotation process.

Negacyclicity in Blind Rotation: The arbitrary specification of coefficients in f(X) allows for the computation of a function with negacyclic properties during blind rotation. Specifically:

Let $g:2N\to Q$ be a function, and define $f=g(0)-g(N-1)X-g(N-2)X^2-\cdots -g(1)X^{N-1}$. Upon executing $\mathsf{BlindRotate}({\mathsf{LWE}}_{2N}(u),\mathsf{brk},f)$, we obtain ${\mathsf{RLWE}}_Q(f·X^u)$. Subsequent application of the $\mathsf{Extract}$ operation yields ${\mathsf{LWE}}_Q(g^{\prime })$, where $g^{\prime }$ represents the constant term of $f·X^u$. For $0\le u<N$, $g^{\prime }=g(u)$; conversely, for $N\le u<2N-1$, $g^{\prime }=-g(u-N)$.

This negacyclic behavior arises from the constraint $X^N=-1$, necessitating that $g(X+N)=-g(X)$ for all X.

The negacyclicity constraint potentially limits the range of functions computable during blind rotation. However, if this constraint can be mitigated, for instance by restricting the domain of u to [0, N), it may become feasible to execute arbitrary functions within the blind rotation process.

Bootstrapping CKKS using blind rotation

Kim et al. (2024a) observed that directly extending the modulus of a ciphertext ${\mathsf{RLWE}}_q(m(X))$ results in ${\mathsf{ct}}^{\prime }={\mathsf{RLWE}}_Q(t(x))$, where $t(x)=m(X)+u(X)·q(modQ)$. Consequently, they proposed first employing an extraction method to obtain ${\mathsf{ct}}_{\mathit{prep}}={\mathsf{RLWE}}_{2N}(u(X))$, then applying blind rotation and scaling to yield ${\mathsf{ct}}_{\mathit{sm}}={\mathsf{RLWE}}_Q(-q·u(X))$. Finally, they compute ${\mathsf{ct}}^{\prime \prime }={\mathsf{ct}}^{\prime }+{\mathsf{ct}}_{\mathit{sm}}$ on the modulus-extended ciphertext to obtain ${\mathsf{ct}}^{\prime \prime }={\mathsf{RLWE}}_Q(m(X))$. The process is as follows:

Extraction: For a ciphertext $\mathsf{ct}=(b,a)$, where $as+b=m(X)+e+q·v(X)\in R$, compute ${\mathsf{ct}}^{\prime }=2N·2t(modq)=({[2N·b]}_q,{[2N·a]}_q)$. This yields ${[2N·b]}_q+{[2N·a]}_q·s=2N·m+2N·e+q·u(X)\in R$. Calculate ${\mathsf{ct}}_{\mathit{prep}}=\left(\frac{2N·\mathsf{ct}-{\mathsf{ct}}^{\prime }}{q}\right)$ to obtain ${\mathsf{ct}}_{\mathit{prep}}={\mathsf{RLWE}}_{2N}(-u(X))$.

Blind Rotation and Scaling: Noise analysis shows that ${\Vert u(X)\Vert }_{\infty }<\frac{N}{2}$. Therefore, when performing blind rotation on the coefficients of $u(X)=u_0+u_{1}X+\cdots +u_{N-1}{X}^{N-1}$, the negacyclic property of blind rotation becomes negligible. Use $\mathsf{Extract}$ to convert ${\mathsf{ct}}_{\mathit{prep}}$ into N$\mathsf{LWE}$ ciphertexts ${\{{\mathsf{LWE}}_{2N}(-u_i)\}}_{i\in [0,N-1]}$, then apply blind rotation to compute ${\{{\mathsf{LWE}}_Q(-u_i·q)\}}_{i\in [0,N-1]}$. Finally, employ the $\mathsf{Repack}$ method from Chen et al. (2021b) to consolidate these into a single ${\mathsf{ct}}_{\mathit{sm}}={\mathsf{RLWE}}_Q(-q·u(X))$.

Result Computation: Calculate ${\mathsf{ct}}^{\prime \prime }={\mathsf{ct}}_{\mathit{sm}}+{\mathsf{ct}}^{\prime }={\mathsf{RLWE}}_{\mathit{Qp}}(2N·m)$. Multiply by $\frac{p}{2N}$ to obtain ${\mathsf{RLWE}}_{\mathit{Qp}}(p·m)$, then apply $\mathsf{rescale}$ on p to yield ${\mathsf{ct}}_{\mathit{boot}}={\mathsf{RLWE}}_Q(m)$.

Through these extraction, blind rotation scaling, and computation steps, ${\mathsf{RLWE}}_q(m(X))$ is transformed into ${\mathsf{RLWE}}_Q(m(X))$. This method eliminates the need for polynomial approximation of the modulus function and homomorphic linear transformations. Moreover, the scheme designed by Kim et al. (2024a) can bootstrap all $\mathsf{RLWE}$-type ciphertexts, including BGV (Brakerski et al. 2014), BFV (Brakerski 2012; Fan and Vercauteren 2012), and CKKS (Cheon et al. 2017).

Yang et al. (2021) focused on the structure of CKKS ciphertexts, which take the form ${\mathsf{RLWE}}_Q(\Delta m+e)$. From a bit-level perspective, the effective bits of the plaintext occupy high positions (at bit $log\Delta$), while the noise’s effective bits are in low positions (at bit 0). They proposed a novel bootstrapping scheme that extracts low-bit noise through blind rotation and subtracts it from the high-bit plaintext. The key advantage of their approach lies in its ability to reduce the original ciphertext’s noise, a feat unachievable by other CKKS bootstrapping methods. Consequently, while noise eventually overwhelms the plaintext’s effective bits in other methods as computations progress, Yang et al. (2021)’s scheme allows for unlimited computations without compromising plaintext integrity due to noise accumulation.

Yang et al. (2021) designed a $\mathsf{BitExtract}$ method by addressing the negacyclic property of blind rotation, enabling the extraction of specific bits from the ciphertext into a new ciphertext. This bit extraction technique extracts low-bit noise into a new ciphertext and subtracts it from the original ciphertext, thereby reducing noise in CKKS ciphertexts while simultaneously expanding the modulus from q to Q, achieving both modulus extension and noise reduction.

Specifically, certain bits can be extracted from the ciphertext through scaling and modulus operations. However, the negacyclic property of the blind rotation function poses challenges in directly applying blind rotation to construct $\mathsf{BitExtract}$. To address this, Yang et al. (2021) designed a scheme that circumvents the negacyclic constraint of blind rotation. They observed that for ${\mathsf{LWE}}_{2N}(u)$ where $0\le u<2N$, the highest bit of u is its sign bit, and obtaining the sign bit through bootstrapping is feasible as it adheres to the negacyclic property. By using blind rotation once to obtain u’s sign bit, Yang et al. (2021) multiply the sign bit by $-N$ and add it to the original ciphertext, thus constraining the plaintext size in $\mathsf{LWE}$ to $0\le u+kN<N,k\in \{0,-1\}$. In essence, they limit u’s size by invoking blind rotation once, then invoke it again to extract any bit from the ciphertext.

Utilizing this innovative blind rotation approach, they successfully designed the $\mathsf{BitExtract}$ algorithm. By invoking $\mathsf{BitExtract}$ at different positions in the ciphertext to extract specific bits, they performed CKKS bootstrapping by accumulating high-bit plaintext information and subtracting low-bit noise information.

Both aforementioned schemes (Kim et al. 2024a; Yang et al. 2021) can bootstrap CKKS under standard parameters. In contrast, general CKKS bootstrapping frameworks (Cheon et al. 2018), which use polynomial approximation, require a larger number of remaining levels to support high-degree polynomial computations. This necessitates a larger q, and to ensure 128-bit security, N must also be larger, resulting in non-standard security parameters. Although (Kim et al. 2024a; Yang et al. 2021) may be less efficient than general bootstrapping frameworks, they can use smaller, standard homomorphic encryption parameters.

The optimization of CKKS bootstrapping through blind rotation techniques has become increasingly interconnected with advances in FHEW/TFHE bootstrapping methods. Recent research has yielded significant improvements over traditional AP/FHEW bootstrapping (Ducas and Micciancio 2015; Alperin-Sheriff and Peikert 2014b; Pereira 2021b) and GINX/TFHE blind rotation (Gama et al. 2016b; Chillotti et al. 2019). These advances include reduced bootstrapping key sizes, lower computational costs (Liu and Wang 2023a; Lee et al. 2023b), and the capacity for simultaneous bootstrapping of multiple ciphertexts (Liu and Wang 2023a, b, c). Notably, researchers have also demonstrated the viability of constructing blind rotation using NTRU assumptions (Xiang et al. 2023). The ongoing refinements in FHEW/TFHE blind rotation techniques, particularly in key size optimization and amortized computational efficiency, can be directly applied to enhance CKKS bootstrapping performance. This symbiotic relationship between FHEW/TFHE and CKKS bootstrapping suggests that continued advancements in FHEW/TFHE methods will likely drive further improvements in CKKS bootstrapping implementations.

Enhancing precision through multiple bootstrapping invocations

Bae et al. (2022) utilized a method involving multiple bootstrapping invocations to perform CKKS bootstrapping. Specifically, for an initial ciphertext $\mathsf{ct}={\mathsf{RLWE}}_q(m(X))$, bootstrapping yields ${\mathsf{ct}}_{\mathit{boot}}={\mathsf{RLWE}}_Q(m(X)+e_{\mathit{boot}})$, where ${\mathsf{ct}}_{\mathit{boot}}$ contains additional noise $e_{\mathit{boot}}$ introduced by the bootstrapping process compared to the original $\mathsf{ct}$. Subtracting these two ciphertexts results in a new ciphertext ${\mathsf{ct}}_{\mathit{err}}={\mathsf{RLWE}}_q(e_{\mathit{boot}})$, whose plaintext represents the bootstrapping noise. By applying the bootstrapping circuit to this encrypted noise ciphertext, we obtain a modulus-extended noise ciphertext ${\mathsf{ct}}_{\mathit{err}}^{\prime }={\mathsf{RLWE}}_Q(e_{\mathit{boot}})$. Subsequently, subtracting this additional ciphertext from the bootstrapped ciphertext yields ${\mathsf{ct}}_{\mathit{boot}}={\mathsf{ct}}_{\mathit{boot}}-{\mathsf{ct}}_{\mathit{err}}^{\prime }={\mathsf{RLWE}}_Q(m(X))$.

It is important to note that if a k-bit bootstrapping scheme is employed, the precision of ${\mathsf{ct}}_{\mathit{boot}}$ obtained after the first bootstrapping operation is k bits. By executing a second bootstrapping operation to subtract the noise from ${\mathsf{ct}}_{\mathit{boot}}$, an additional k bits of precision are gained, resulting in a total precision of 2k bits. Consequently, by invoking any bootstrapping scheme l times, a bootstrapping precision of kl bits can be achieved.

Performance comparison of different schemes

Among the various bootstrapping schemes for CKKS, only the schemes by Cheon et al. (2018) and Bossuat et al. (2021) have open-source implementations available in Inc (2024) and Mouchet et al. (2020), respectively.

We conducted experiments using Intel(R) Core(TM) i7-13700H 2.40 GHz CPU with 32 GB RAM running Ubuntu 22.04 LTS. For implemented schemes, we used HEAAN v1.1 and Lattigo v3.0 with default compiler optimizations. Each timing result represents the average of 10 independent runs. The experiments for Cheon et al. (2018) and Bossuat et al. (2021) were directly measured. For schemes without implementations, we have conducted quantitative analyses based on the data provided in their respective papers. Due to the variation in parameter indicators across papers, we have adopted a unified metric for comparison.

Specifically, we employ the Utility metric (Chen et al. 2019; Bossuat et al. 2021) to evaluate the performance of different CKKS bootstrapping schemes. The Utility is defined as:

10

$$\begin{array}{c}\hfill \text{Utility}=log\left(\frac{\text{Remaining modulus bits}\times \text{Plaintext slots}\times \text{Precision}}{\text{Refresh time in seconds}}\right)\end{array}$$The significance of this metric lies in its incorporation of the number of multiplication levels that can be further computed with the remaining modulus, the precision of plaintext representation, and the number of plaintext messages that can be encoded in a single ciphertext. The Utility metric provides a unified quantitative measure of a ciphertext’s computational capability and efficiency. In addition to Utility, the precision of CKKS bootstrapping is another crucial indicator. Enhancing precision not only improves computational accuracy but also enables the application of noise-flooding techniques during decryption to enhance $\mathsf{IND}-{\mathsf{CPA}}^{\mathsf{D}}$ security when precision exceeds 30 bits (Li and Micciancio 2021).

Given that various schemes have different optimization focuses, including performance optimizations (Cheon et al. 2018; Chen et al. 2019; Han and Ki 2020; Bossuat et al. 2021; Lee et al. 2022e) and precision optimizations (Jutla and Manohar 2020; Lee et al. 2021b, 2022e; Jutla and Manohar 2022; Kim et al. 2024a; Yang et al. 2021; Bae et al. 2022), we categorize and compare these schemes along two dimensions. The first comparison, as shown in Table 2, evaluates the highest achievable Utility for each scheme. The second comparison, presented in Table 3, examines the maximum precision attainable by different schemes.

Table 2. Utility comparison of CKKS bootstrapping schemes

Scheme	N	n	$logQP$	$log{Q}^{\prime }$	h	t	u	p	$\lambda$
Cheon et al. (2018)	$2^{16}$	$2^7$	2480	631	64	591.0	11.09	16.0	80
Chen et al. (2019)	$2^{16}$	$2^{14}$	2480	172	64	158.3	18.33	18.6	80
Chen et al. (2019)	$2^{16}$	$2^{12}$	2480	301	64	167.8	17.22	20.9	80
Han and Ki (2020)	$2^{16}$	$2^{14}$	1452	370	64	52.8	20.24	10.8	90
Bossuat et al. (2021)	$2^{16}$	$2^{15}$	1553	505	192	18.1	24.06$_{}^a$	19.1	128
Bossuat et al. (2021)	$2^{16}$	$2^{14}$	1547	240	192	16.0	22.88	31.6	128
Lee et al. (2021b)	$2^{16}$	$2^{14}$	1553	653	192	461.5	19.26	27.2	128
Lee et al. (2021b)	$2^{16}$	$2^5$	1553	473	192	94.7	12.66	40.5$_{}^b$	128
Lee et al. (2022e)	$2^{16}$	$2^{14}$	1487	240	192	28.3	22.05	31.4	>128
Lee et al. (2022e)	$2^{17}$	$2^3$	3069	–	192	–	–	100.1$_{}^c$	128

N: Ring Size, n: Slot Count, $logQP$: Pre-bootstrap Modulus, $log{Q}^{\prime }$: Post-bootstrap Modulus,

h: Key Sparsity, t: Time (s), u: Utility, p: Precision, $\lambda$: Security Level

$_{}^a$Highest Utility, $_{}^b$Highest Precision for $N=2^{16}$, $_{}^c$Highest overall Precision, Values in bold represent the best performance in their respective category

A comparison of the utility (efficiency) of different schemes is shown in Table 2. Here, N represents the order of the cyclotomic polynomial ${\Phi }_M(X)=X^N+1$, n denotes the number of plaintext slots. During bootstrapping, the modulus q is expanded to Q, but after $\mathsf{CoeffToSlot}$, $\mathsf{EvalMod}$, and $\mathsf{SlotToCoeff}$ operations, it is reduced to $Q^{\prime }$ due to modulus consumption. To perform $\mathsf{KS}$, an additional modulus P is introduced. The overall security of the scheme is related to $logQP$, where $log{Q}^{\prime }$ represents the bit size of the remaining modulus. h denotes the Hamming weight of the key, and the time column indicates the total execution time for one bootstrapping operation. The utility is calculated as previously described, and precision is the ratio of plaintext size to final noise magnitude. $\lambda$ represents the security level achievable by the scheme’s parameters.

In the initial two schemes (Cheon et al. 2018; Chen et al. 2019), due to the absence of RNS-CKKS, the additional modulus P is equal to Q, resulting in a relatively large $logQP$. Moreover, the use of sparse keys with $h=64$ limits the security to 80 bits, falling short of the 128-bit security standard. HK20 (Han and Ki 2020) employed the RNS-CKKS scheme to construct the bootstrapping circuit, allowing P to be similar in size to q. Leveraging the high performance of RNS-CKKS, they significantly improved utility. However, with the sparse key still at $h=64$, security only reached 90 bits.

Bossuat et al. (2021) optimized the key switching $\mathsf{KS}$ in the most time-consuming linear transformation of bootstrapping and utilized the $\mathsf{BSGS}$ approach to enhance homomorphic polynomial operations. This substantially reduced the overall CKKS bootstrapping time, achieving the highest utility to date.

Lee et al. (2021b) optimized the modular function approximation. However, as their scheme was not designed for RNS, its overall efficiency was relatively poor, although it could achieve a precision of up to 40.5 bits. In a subsequent work, Lee et al. (2022e) extended their previous research (Lee et al. 2021b) to support RNS schemes and optimized the homomorphic polynomial operations from (Bossuat et al. 2021). This allowed them to attain good efficiency while maintaining precision. They also presented results achieving up to 100 bits of precision, albeit without providing specific efficiency metrics or parameters.

Table 3. Precision comparison of CKKS bootstrapping schemes

Scheme	N	n	$logQP$	$log{Q}^{\prime }$	t	p
Cheon et al. (2018)	$2^{16}$	1	2480	344	126	24
Lee et al. (2021b)	$2^{16}$	$2^5$	1553	473	94.7	40.5
Jutla and Manohar (2020)	$2^{18}$	$2^3$	3600	1351	1893	63
Yang et al. (2021)	${\mathbf{2}}^{\mathbf{13}}$	1	$\mathbf{208}$	108	68.3	39
Kim et al. (2024a)	${\mathbf{2}}^{\mathbf{13}}$	2	219	170	–	79.04
Jutla and Manohar (2022)	$2^{17}$	$2^3$	3000	843	167	100
Lee et al. (2022e)	$2^{17}$	$2^3$	3069	–	–	100
Bae et al. (2022)	$2^{17}$	$2^{16}$	2881	450	903	420

N: Ring Size, n: Slot Count, $logQP$: Pre-bootstrap Modulus, $log{Q}^{\prime }$: Post-bootstrap Modulus, t: Time (s), p: Precision. Bold values indicate significant parameters: the small ring sizes (N) by Yang et al., and Kim et al., the notably small pre-bootstrap modulus (208) by Yang et al., and the highest precision (420) achieved by Bae et al.

Table 3 presents the highest precision levels achieved by several schemes (Jutla and Manohar 2020; Lee et al. 2021b; Yang et al. 2021; Kim et al. 2024a; Jutla and Manohar 2022; Lee et al. 2022e; Bae et al. 2022) optimized for bootstrapping precision. This includes schemes (Yang et al. 2021) and (Kim et al. 2024a), which construct blind rotations using $\mathsf{RGSW}$ ciphertexts. These two schemes achieve reasonable plaintext precision under relatively small polynomial moduli. However, due to the lack of SIMD operations support for blind rotations, both schemes are inefficient. Yang et al. (2021) requires 68.3 s to refresh a single CKKS ciphertext, while (Kim et al. 2024a) has not disclosed its runtime data.

In comparison, schemes utilizing SIMD technology to approximate the modular function tend to exhibit higher performance. For the modular function, Cheon et al. (2018) employed sine functions for approximation, followed by polynomial approximation of the sine functions. However, due to inherent errors between sine functions and the modular function, high precision could not be achieved. Subsequent optimizations avoided this intrinsic error. Lee et al. (2021b) utilized sine and arccosine functions, employing the multi-interval Remez algorithm for approximation. However, their requirement for large polynomial coefficients limited precision to a maximum of 40 bits. Jutla and Manohar (2020) used Lagrange interpolation to directly approximate the modular function with polynomials, but the high order and large coefficients of the polynomials necessitated large parameters. They achieved 63-bit precision with $N=2^{18}$.

Jutla and Manohar (2022) approximated the modular function using sine sequences, reducing error by two orders of magnitude compared to single sine functions. The use of sine functions allowed for rapid computation using double angle formulas, enabling their scheme to achieve 100-bit precision in 167 s. Lee et al. (2022e) conducted optimal analysis using signal-to-noise ratio, identifying a polynomial with smaller coefficients for direct approximation of the modular function. Through this method, they also achieved 100-bit precision, though runtime was not disclosed in their paper.

Bae et al. (2022) constructed a method for high-precision bootstrapping by invoking bootstrapping schemes multiple times. By calling a k-bit precision bootstrapping scheme l times, lk-bit precision can be achieved. They termed this method “meta-bootstrapping”. However, as it involves l invocations of other bootstrapping schemes, the required time is approximately l times longer.

Analysis of the aforementioned table reveals that currently, for CKKS bootstrapping, Bossuat et al. (2021)’s scheme achieves optimal performance (throughput), while (Lee et al. 2022e) and (Jutla and Manohar 2022)’s schemes attain high bootstrapping precision. Higher precision can be achieved through multiple invocations using BCC+22 (Bae et al. 2022)’s method. Meanwhile, Yang et al. (2021)’s method can reduce noise in the original ciphertext, enabling arbitrary numbers of homomorphic operations.

Implementation resources and tools

Table 4. Recommended FHE libraries

Library	Schemes	Boot.	Lang.	Last update
OpenFHE Al Badawi et al. (2022)	BGV, BFV, CKKS	$●$	C++	2025/01
tfhe-rs Zama (2022b)	TFHE	$◐$	Rust	2025/01
lattigo Mouchet et al. (2020)	BGV, BFV, CKKS	$●$	Go	2024/12
SEAL Microsoft (2024)	BGV, BFV, CKKS	$○$	C++	2024/07
HEAAN Inc (2024)	CKKS	$●$	C++	2023/08
HElib Halevi and Shoup (2024)	BGV, CKKS	$◐$	C++	2023/07

$●$: support CKKS Bootstrapping, $◐$: support other Bootstrapping method, $○$: No Bootstrapping Supported

The landscape of FHE libraries has evolved significantly, with several mature implementations now available for practical applications. Table 4 provides a comparative overview of major open-source FHE libraries, highlighting their supported schemes, bootstrapping capabilities, implementation languages, and development activity. When selecting a library for CKKS implementation, key considerations include scheme support, performance optimization, documentation quality, and community activity. Below, we detail the characteristics and strengths of prominent libraries to guide implementation choices.

OpenFHE (Al Badawi et al. 2022), the successor to PALISADE (Project 2024), stands out as a comprehensive solution supporting multiple schemes including BGV, BFV, CKKS (with bootstrapping), and FHEW/TFHE. Its distinctive features include threshold versions of major schemes, proxy re-encryption capabilities, and extensive optimization options. The library’s active development and comprehensive documentation make it particularly suitable for projects requiring multiple FHE schemes or advanced features like bootstrapping.

Microsoft’s SEAL (Microsoft 2024) has established itself as a foundational library in the FHE ecosystem, supporting BGV, BFV, and CKKS schemes. While it doesn’t implement CKKS bootstrapping, its robust implementation, extensive documentation, and wide adoption in production systems make it an excellent choice for building FHE applications. Notable projects built on SEAL include private set intersection (APSI Microsoft 2021a), private information retrieval (SEALPIR Microsoft 2018), homomorphic compiler (EVA Microsoft 2021b), and privacy-preserving computation frameworks (SecretFlow Group 2024, mpc4j Alibaba 2024).

Lattigo Mouchet et al. (2020), implemented in Go, offers unique advantages for cross-platform deployment, including WASM compilation for browser-based applications. It supports BFV/BGV and CKKS schemes with their multiparty versions, and implements state-of-the-art bootstrapping optimizations (Bossuat et al. 2021). Its pure Go implementation delivers performance comparable to C++ alternatives while enabling broader deployment options.

TFHE-rs (Zama 2022b), developed by Zama AI, represents the cutting edge in TFHE implementation. Its Rust-based implementation supports advanced TFHE features, including circuit bootstrapping, making it particularly suitable for implementing CKKS bootstrapping through TFHE blind rotation techniques (Kim et al. 2024b; Yang et al. 2021). The library powers several practical applications, including privacy-preserving machine learning (ConcreteML Zama 2022a) and FHE-enabled ethereum virtual machines (fhEVM Zama 2024).

HElib Halevi and Shoup (2024), developed by IBM, pioneered many optimization techniques in RLWE-based schemes, particularly for BGV. While its CKKS implementation is more recent, its mature BGV implementation and historical contributions to FHE optimization make it valuable for understanding advanced implementation techniques.

HEAAN Inc (2024), developed by the original CKKS authors, implements the foundational CKKS scheme and its initial bootstrapping approach (Cheon et al. 2018). While now closed-source, it remains historically significant and useful for understanding the basic CKKS construction.

Beyond open-source implementations, several critical resources and tools support the secure implementation of FHE schemes. The Homomorphic Encryption Security Standard (Albrecht et al. 2018) provides comprehensive guidelines for parameter selection across different security levels, serving as an essential reference for both researchers and practitioners implementing FHE schemes. This standard ensures implementations meet accepted security requirements while maintaining practical efficiency. Complementing these guidelines, the Lattice Estimator (Albrecht 2022) offers a practical tool for assessing the concrete security level of lattice-based cryptosystems. This tool is particularly valuable when selecting parameters for FHE implementations and other lattice-based cryptographic systems, helping developers balance security requirements with performance constraints. Together, these resources form a robust toolkit for implementing secure and efficient FHE systems, whether using CKKS or other homomorphic encryption schemes.

Applications of CKKS bootstrapping

The CKKS scheme, as an approximate fully homomorphic encryption system, has enabled numerous privacy-preserving applications through its bootstrapping capability. While several implementations have successfully utilized Leveled Homomorphic Encryption for specific tasks such as face identification (Ibarrondo et al. 2023), inference (Chen et al. 2021c), and secure multi-party computation protocols (Huang et al. 2022), this approach exhibits inherent limitations when confronted with computationally intensive applications requiring substantial multiplicative depth. Such applications include deep neural networks (He et al. 2016; Vaswani 2017), encrypted database operations (Bois et al. 2021), and outsourced computation (Morrison et al. 2021). In this section, we explore major application domains where CKKS bootstrapping has demonstrated significant impact, with particular emphasis on privacy-preserving machine learning, secure outsourced computation, and recent developments in cross-scheme bootstrapping.

Privacy-preserving machine learning

Privacy-Preserving Machine Learning (PPML) represents one of the most significant applications of the CKKS scheme, where bootstrapping enables the evaluation of deep neural networks and complex training procedures in the encrypted domain. The bootstrapping operation serves as a crucial component for managing noise growth during iterative computations, allowing for the implementation of sophisticated machine learning algorithms while maintaining data privacy throughout the entire process. Numerous PPML systems have been implemented with secure multi-party computation (MPC) protocols (Mohassel and Rindal 2018; Mohassel and Zhang 2017; Riazi et al. 2018; Rouhani et al. 2018; Lu et al. 2023; Lin et al. 2024; Bhardwaj et al. 2024). While MPC approaches necessitate active multi-party participation, FHE’s distinctive capability for single-party computation offers unique advantages in specific application contexts.

The evolution of privacy-preserving training methodologies has been significantly influenced by practical challenges in healthcare and genomics, particularly through the iDASH Privacy & Security Workshop competition. A notable milestone emerged from the 2017 competition (Wang et al. 2018), where participants tackled the implementation of privacy-preserving logistic regression on genomic data. The winning solution (Chen et al. 2018) demonstrated a groundbreaking application of CKKS with bootstrapping, enabling multiple gradient descent iterations and establishing a foundational framework for managing noise accumulation in iterative computations on encrypted biomedical data.

Further advancing this domain, subsequent research in logistic regression training (Kim et al. 2018) has leveraged bootstrapping to overcome the constraints of noise accumulation in gradient descent iterations. This approach achieves linear computational complexity with respect to iteration count, though ultimately bounded by homomorphic encryption parameter selections.

The landscape of encrypted neural network inference has witnessed substantial evolution, particularly in Machine Learning as a Service (MLaaS) systems. Contemporary MLaaS platforms predominantly employ the CKKS scheme (Cheon et al. 2024; Wood et al. 2020b; Jiang et al. 2018a; Lee et al. 2022b; Zhang et al. 2024b), where efficient bootstrapping mechanisms prove instrumental for practical encrypted inference (Lee et al. 2023a). The field has progressed significantly from early approaches that focused on HE-friendly network architectures (Gilad-Bachrach et al. 2016; Chou et al. 2018), which, while innovative, required substantial model modifications that conflicted with the MLaaS paradigm’s requirement for standard architecture support.

Recent research has marked a paradigm shift towards precise approximation of pre-trained standard CNNs (SCNNs). Significant advances include (Lee et al. 2022b)’s implementation of multiplexed parallel convolutions and optimized bootstrapping techniques in RNS-CKKS, enabling efficient evaluation of standard ResNet architectures while maintaining robust security guarantees. The Channel-By-Channel methodology (Cheon et al. 2024) further refined these capabilities through sophisticated data packing and convolution optimizations.

Contemporary optimization techniques have achieved remarkable efficiency improvements, with recent work (Kim and Guyot 2023) maintaining constant computational complexity independent of kernel dimensions. The NeuJeans framework (Ju et al. 2023) represents a significant advancement through its innovative Coefficients-in-Slot (CinS) encoding, enabling multiple convolution operations within single homomorphic multiplications while eliminating costly permutation operations.

Secure outsourced computation

While CKKS has found widespread adoption in privacy-preserving machine learning due to its natural fit for approximate arithmetic, its role in secure outsourced computation (SOC) has been historically limited by both bootstrapping performance and its approximate nature. However, recent improvements in bootstrapping efficiency are changing this landscape, potentially enabling more general-purpose secure computation services in cloud environments.

In the era of cloud computing, SOC has emerged as a crucial paradigm enabling organizations to delegate computational tasks while protecting sensitive data. The field has evolved from basic encryption schemes to sophisticated protocols, including identity-based encryption (Boneh and Franklin 2001; Unal et al. 2021), attribute-based encryption (Bethencourt et al. 2007), and integrity verification methods (Backes et al. 2013). While these traditional methods primarily focus on protecting data privacy during storage and transmission, homomorphic encryption enables direct computation on encrypted data, addressing the broader challenge of secure data processing in untrusted environments.

Historically, the substantial computational overhead of bootstrapping in FHE schemes led researchers to pursue alternative approaches (Zhao et al. 2022). These alternatives included partially homomorphic encryption (PHE) schemes (Paillier 1999; Rivest et al. 1983), somewhat homomorphic encryption (SWHE) (Brakerski et al. 2014), and multi-server architectures with interactive protocols (Goldreich et al. 2019). While more efficient for specific tasks, these approaches were inherently limited in functionality, typically focusing on singular aspects of SOC such as k-means clustering (Zhang et al. 2022), data aggregation (Marandi et al. 2024), linear algebra (Atallah and Frikken 2010), matrix computation (Jiang et al. 2018b), or face recognition (Wang et al. 2022). None could handle general computation tasks due to the bootstrapping bottleneck. As bootstrapping efficiency improves, SOC applications can potentially transition from these specialized protocols to more general FHE-based solutions.

Some computational tasks inherently require bootstrapping due to their complexity. For instance, comparison operations, despite sophisticated optimization protocols (Cheon et al. 2020; Lee et al. 2021a; Tan et al. 2020; Lee et al. 2022a) minimizing multiplicative depth, still require bootstrapping for extended computational chains. Notable advances in this area include (Hong et al. 2021)’s optimized k-way sorting network, which achieves an improved complexity of $O(k{log}_{k}n)$. Similarly, in search applications, HERS (Engelsma et al. 2022) demonstrates the practical viability of similarity search over encrypted vectors, where bootstrapping proves essential for result aggregation and iterative search procedures.

Encrypted databases represent another significant domain for secure data outsourcing, where both data and queries are processed in encrypted form. However, due to the requirement for exact arithmetic in database operations, these systems typically employ PHE schemes like Paillier (Popa et al. 2012) or SWHE schemes like BFV (Henzinger et al. 2023; Bian et al. 2023; Ren et al. 2022) rather than CKKS. Recent work such as ArcEDB (Zhang et al. 2024c) achieves state-of-the-art performance in encrypted database queries by utilizing exponent encoding of RLWE(BFV) ciphertext and external product of RGSW for homomorphic filtering.

As cloud computing continues to evolve, the improved efficiency of CKKS bootstrapping opens new possibilities for general-purpose secure computation services. Unlike traditional application-specific protocols, CKKS-based solutions could enable cloud providers to offer flexible secure computation services that support arbitrary functions while maintaining data privacy, though careful consideration of performance trade-offs remains necessary.

Bootstrapping other FHE scheme with CKKS

The evolution of FHE schemes has demonstrated significant interconnectivity across different generations and types. Foundational work by Boura et al. (2020) established the interoperability between FHEW-type and BGV/BFV/CKKS-type schemes, while (Chen et al. 2021b) demonstrated the convertibility between RLWE and LWE ciphertexts. This interconnectedness extends to bootstrapping mechanisms, where recent research reveals substantial mutual benefits between different schemes’ bootstrapping approaches.

A significant theoretical advancement has emerged in the form of a novel bootstrapping methodology for BFV (Kim et al. 2024b), which ingeniously leverages CKKS bootstrapping as a fundamental component. This approach, applicable when the BFV plaintext modulus t divides the ciphertext modulus q, enables noise extraction and transformation into the CKKS domain through modulus switching. The methodology achieves remarkable efficiency improvements, reducing both key size and computational overhead by approximately 30-fold compared to traditional approaches, while establishing a valuable bridge where advancements in CKKS bootstrapping directly enhance BFV bootstrapping capabilities.

Particularly noteworthy is the application of CKKS bootstrapping for functional bootstrapping tasks traditionally associated with FHEW/TFHE schemes (Ducas and Micciancio 2015; Chillotti et al. 2019). Alexandru et al. (2024) demonstrated that CKKS-style bootstrapping, combined with trigonometric Hermite interpolation techniques, can achieve functional bootstrapping with efficiency improvements of three orders of magnitude compared to traditional FHEW/TFHE approaches. Building upon this foundation, Bae et al. (2024a, 2024b) further expanded the capabilities of CKKS bootstrapping to evaluate arbitrary functions on bit-level and small integer inputs during the bootstrapping process, marking a significant advancement in the versatility of CKKS-based approaches.

Future research directions

The comparative analysis in the previous section demonstrates that CKKS bootstrapping schemes have made significant advancements since their initial proposal, which could only refresh one 8-bit precision ciphertext per second (Cheon et al. 2018). Currently, the fastest CKKS bootstrapping scheme can refresh 1024 ciphertexts with 31.6-bit precision per second (Bossuat et al. 2021). The highest precision for a single bootstrapping operation has reached 100 bits (Jutla and Manohar 2022; Lee et al. 2022e), and through multiple bootstrapping invocations, a precision of up to 400 bits can be achieved (Bae et al. 2022).

However, for applications requiring high real-time performance (such as real-time model prediction Brutzkus et al. 2019) or programs with extremely high computational complexity (such as machine learning training Lee et al. 2022c), current CKKS bootstrapping schemes still cannot simultaneously meet both precision and efficiency requirements. There remains considerable room for optimization in computational efficiency. Future research directions may include:

Increasing Residual Modulus: For CKKS schemes, each multiplication operation consumes a certain modulus, thus the size of the residual modulus is closely related to the remaining available multiplication layers. Increasing the residual modulus can effectively enhance the overall usability of bootstrapping schemes.

Small Parameter Bootstrapping: In schemes based on polynomial approximation for modular reduction, parameters often need to be set to $N=2^{17}$ to construct a viable scheme. However, in CKKS applications, common parameter ranges are $N\in \left\{2^{13},,,2^{14},,,2^{15}\right\}$. Large parameters lead to slower basic operations (such as addition, multiplication, and relinearization). Therefore, implementing bootstrapping under smaller parameters is an important optimization direction.

Constructing Applications: Developing applications using the most efficient current bootstrapping schemes. Compared to initial proposals, current bootstrapping performance has improved considerably. Thus, it is worth considering the use of new bootstrapping schemes to construct efficient privacy-preserving algorithms in scenarios requiring high-degree polynomial computations.

Software and Hardware Optimization: In addition to algorithmic improvements for usability, optimization of overall algorithmic efficiency can be considered at both software and hardware levels. For instance, leveraging GPU parallelization capabilities for parallel processing of $\mathsf{CoeffToSlot}$ and $\mathsf{SlotToCoeff}$ algorithms in bootstrapping, or implementing hardware-level optimizations for bootstrapping algorithms using FPGA or other chips.

Eliminating Computational Noise: Current CKKS bootstrapping can increase the number of computational layers while introducing only a small amount of noise. However, noise generated by the computation itself is not effectively removed, ultimately affecting the accuracy of the final computational results. Designing other efficient methods similar to Yang et al. (2021) to address the noise introduced by CKKS computations would represent a significant breakthrough.

Conclusion

As bootstrapping is the most computationally intensive component of fully homomorphic encryption, constructing efficient bootstrapping algorithms is crucial for the lightweight implementation of fully homomorphic encryption. It directly impacts the integration of fully homomorphic technology with blockchain and its application in decentralized privacy-preserving computing scenarios. This paper focuses on the widely applied CKKS algorithm in the privacy-preserving computing domain, systematically and comprehensively analyzing the current research status of bootstrapping technology and comparing the advantages and disadvantages of different schemes. It summarizes the research progress of CKKS bootstrapping schemes to date, aiming to provide a reference for the implementation of lightweight fully homomorphic technology. Simultaneously, this paper offers directions and specific suggestions for future research optimization, with the goal of promoting rapid development and practical application of CKKS bootstrapping schemes.

Regarding improving algorithmic usability (including efficiency and precision), we propose several potentially feasible suggestions:

1. To enhance the precision of a single bootstrapping operation, the primary approach is to find a (preferably low-degree) polynomial with small coefficients to approximate the modular function. Considering the use of inverse trigonometric functions combined with trigonometric function sequences may further improve the approximation of the modular function.

2. In Kim et al. (2024a), a single blind rotation is used for modular reduction, but this can only refresh 6–7 bits of plaintext. Therefore, considering segmented blind rotation operations to optimize modular reduction noise could be beneficial.

3. In CKKS bootstrapping schemes using blind rotation (Kim et al. 2024a; Yang et al. 2021), consider leveraging the capabilities of the latest amortized blind rotation (De Micheli et al. 2024; Guimarães et al. 2023) to perform FHEW-type bootstrapping on multiple ciphertexts simultaneously, thereby increasing the throughput of CKKS bootstrapping under small parameters.

4. The Jutla and Manohar (2022) scheme did not consider the RNS form of CKKS schemes. Exploring how to optimize bootstrapping efficiency using RNS schemes is a direction worth considering.

5. In bootstrapping schemes using polynomial approximation, consider using polynomial fitting methods to extract the noise component introduced by computations as a new ciphertext, and subtract it from the original ciphertext through subtraction. This approach could reduce errors from approximate calculations, potentially enabling arbitrary computational depth.

Acknowledgements

We would like to extend our sincere appreciation to the editor and reviewers for their valuable feedback and constructive suggestions that helped improve the quality of this manuscript.

Author Contributions

HS: writing, editing, review. QX: editing, review. BY: editing, review. YY: editing, review. WH: editing, review. All authors read and approved the final manuscript.

Funding

This work was supported by the National Key Research and Development Program of China under Grant 2023YFB3106501.

Availability of data and materials

All data generated or analyzed during this study are included in this published article.

Declarations

Competing interests

The authors declare that they have no conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

Acar, A; Aksu, H; Uluagac, AS et al. A survey on homomorphic encryption schemes: theory and implementation. ACM Comput Surv (CSur); 2018; 51, 4 pp. 1-35. [DOI: https://dx.doi.org/10.1145/3214303] 1410.54043

Al Badawi A, Bates J, Bergamaschi F, et al (2022) Openfhe: open-source fully homomorphic encryption library. In: Proceedings of the 10th workshop on encrypted computing & applied homomorphic cryptography. Association for Computing Machinery, New York, NY, USA, WAHC’22, pp 53–63. https://doi.org/10.1145/3560827.3563379

Al-Rubaie, M; Chang, JM. Privacy-preserving machine learning: threats and solutions. IEEE Secur Privacy; 2019; 17, 2 pp. 49-58. [DOI: https://dx.doi.org/10.1109/MSEC.2018.2888775] 1289.92063

Alaya, B; Laouamer, L; Msilini, N. Homomorphic encryption systems statement: trends and challenges. Comput Sci Rev; 2020; 36, 4091226 [DOI: https://dx.doi.org/10.1016/j.cosrev.2020.100235] 1478.68079 100235.

Albrecht M, Chase M, Chen H, et al (2018) Homomorphic encryption security standard. Tech. rep., HomomorphicEncryption.org, Toronto, Canada

Albrecht MR (2022) Security estimates for lattice problems. https://github.com/malb/lattice-estimator

Alexandru A, Kim A, Polyakov Y (2024) General functional bootstrapping using ckks. Cryptology ePrint Archive

Alharbi A, Zamzami H, Samkri E (2020) Survey on homomorphic encryption and address of new trend. Int J Adv Comput Sci Appl 11(7)

Alibaba (2024) mpc4j: a java library for secure multi-party computation. https://github.com/alibaba-edu/mpc4j. Accessed 06 Jan 2025

Alperin-Sheriff J, Peikert C (2014a) Faster bootstrapping with polynomial error. In: Advances in cryptology–CRYPTO 2014: 34th annual cryptology conference, Santa Barbara, CA, USA, 17–21 Aug 2014, Proceedings, Part I 34. Springer, pp 297–314

Alperin-Sheriff, J; Peikert, C. Faster bootstrapping with polynomial error; 2014; Berlin, Springer: pp. 297-314. [DOI: https://dx.doi.org/10.1007/978-3-662-44371-2_17] 1336.94034

Angel S, Chen H, Laine K, et al (2018) Pir with compressed queries and amortized query processing. In: 2018 IEEE symposium on security and privacy (SP). IEEE, pp 962–979

Atallah MJ, Frikken KB (2010) Securely outsourcing linear algebra computations. In: Proceedings of the 5th ACM symposium on information, computer and communications security, pp 48–59

Backes M, Fiore D, Reischuk RM (2013) Verifiable delegation of computation on outsourced data. In: Proceedings of the 2013 ACM SIGSAC conference on computer & communications security, pp 863–874

Bae Y, Cheon JH, Cho W, et al (2022) Meta-bts: bootstrapping precision beyond the limit. In: Proceedings of the 2022 ACM SIGSAC conference on computer and communications security, CCS’22. ACM. https://doi.org/10.1145/3548606.3560696,

Bae, Y; Cheon, JH; Kim, J et al. Bootstrapping bits with CKKS; 2024; Cham, Springer: pp. 94-123. [DOI: https://dx.doi.org/10.1007/978-3-031-58723-8_4] 1551.94076

Bae, Y; Cheon, JH; Kim, J et al. Bootstrapping bits with CKKS; 2024; Cham, Springer: pp. 94-123. [DOI: https://dx.doi.org/10.1007/978-3-031-58723-8_4] 1551.94076

Bethencourt J, Sahai A, Waters B (2007) Ciphertext-policy attribute-based encryption. In: 2007 IEEE symposium on security and privacy (SP’07). IEEE, pp 321–334

Bhardwaj D, Saravanan S, Chandran N, et al (2024) Securely training decision trees efficiently. Cryptology ePrint Archive

Bian S, Zhang Z, Pan H, et al (2023) He3db: an efficient and elastic encrypted database via arithmetic-and-logic fully homomorphic encryption. In: Proceedings of the 2023 ACM SIGSAC conference on computer and communications security, pp 2930–2944

Bois A, Cascudo I, Fiore D, et al (2021) Flexible and efficient verifiable computation on encrypted data. In: IACR international conference on public-key cryptography. Springer, pp 528–558

Boneh D, Franklin M (2001) Identity-based encryption from the Weil pairing. In: Annual international cryptology conference. Springer, pp 213–229

Boneh, D; Goh, EJ; Nissim, K. Evaluating 2-DNF formulas on ciphertexts; 2005; Berlin, Springer: pp. 325-341. [DOI: https://dx.doi.org/10.1007/978-3-540-30576-7_18] 1079.94534

Bossuat, JP; Mouchet, C; Troncoso-Pastoriza, J et al. Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys; 2021; Berlin, Springer: pp. 587-617. [DOI: https://dx.doi.org/10.1007/978-3-030-77870-5_21] 1479.94132

Boura, C; Gama, N; Georgieva, M et al. Chimera: combining ring-LWE-based fully homomorphic encryption schemes. J Math Cryptol; 2020; 14, 1 pp. 316-338.4134762 [DOI: https://dx.doi.org/10.1515/jmc-2019-0026] 1462.94030

Brakerski, Z. Fully homomorphic encryption without modulus switching from classical GapSVP; 2012; Berlin, Springer: pp. 868-886. [DOI: https://dx.doi.org/10.1007/978-3-642-32009-5_50] 1296.94091

Brakerski Z, Vaikuntanathan V (2011) Efficient fully homomorphic encryption from (standard) LWE. In: 2011 IEEE 52nd annual symposium on foundations of computer science. IEEE. https://doi.org/10.1109/focs.2011.12

Brakerski, Z; Gentry, C; Vaikuntanathan, V. (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans Comput Theory; 2014; 6, 3 pp. 1-36.3255281 [DOI: https://dx.doi.org/10.1145/2633600] 1347.68121

Brutzkus A, Gilad-Bachrach R, Elisha O (2019) Low latency privacy preserving inference. In: International conference on machine learning, PMLR, pp 812–821

Chen C, Zhou J, Wang L, et al (2021a) When homomorphic encryption marries secret sharing: secure large-scale sparse logistic regression and applications in risk control. In: Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pp 2652–2662

Chen H, Laine K, Rindal P (2017) Fast private set intersection from homomorphic encryption. In: Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pp 1243–1255

Chen, H; Gilad-Bachrach, R; Han, K et al. Logistic regression over encrypted data from fully homomorphic encryption. BMC Med Genomics; 2018; 11, pp. 3-12. [DOI: https://dx.doi.org/10.1186/s12920-018-0397-z]

Chen, H; Chillotti, I; Song, Y. Improved bootstrapping for approximate homomorphic encryption; 2019; Berlin, Springer: pp. 34-54. [DOI: https://dx.doi.org/10.1007/978-3-030-17656-3_2] 1428.94064

Chen, H; Dai, W; Kim, M et al. Efficient homomorphic conversion between (ring) LWE ciphertexts; 2021; Berlin, Springer: pp. 460-479. [DOI: https://dx.doi.org/10.1007/978-3-030-78372-3_18] 1491.94042

Chen J, Feng Y, Liu Y, et al (2021c) Non-interactive privacy-preserving Naíve Bayes classifier using homomorphic encryption. In: International conference on security and privacy in new computing environments. Springer, pp 192–203

Cheon, JH; Kim, A; Kim, M et al. Homomorphic encryption for arithmetic of approximate numbers; 2017; Berlin, Springer: pp. 409-437. [DOI: https://dx.doi.org/10.1007/978-3-319-70694-8_15] 1420.94051

Cheon, JH; Han, K; Kim, A et al. Bootstrapping for approximate homomorphic encryption; 2018; Berlin, Springer: pp. 360-384. [DOI: https://dx.doi.org/10.1007/978-3-319-78381-9_14] 1420.94050

Cheon JH, Kim D, Kim D (2020) Efficient homomorphic comparison methods with optimal complexity. In: Advances in cryptology–ASIACRYPT 2020: 26th international conference on the theory and application of cryptology and information security, Daejeon, South Korea, 7–11 Dec 2020, Proceedings, Part II 26. Springer, pp 221–256

Cheon, JH; Kang, M; Kim, T et al. Batch inference on deep convolutional neural networks with fully homomorphic encryption using channel-by-channel convolutions. IEEE Trans Depend Secure Comput; 2024; [DOI: https://dx.doi.org/10.1109/tdsc.2024.3448406] 1361.32003

Chillotti, I; Gama, N; Georgieva, M et al. Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds; 2016; Berlin, Springer: pp. 3-33. [DOI: https://dx.doi.org/10.1007/978-3-662-53887-6_1] 1384.94044

Chillotti, I; Gama, N; Georgieva, M et al. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE; 2017; Berlin, Springer: pp. 377-408. [DOI: https://dx.doi.org/10.1007/978-3-319-70694-8_14] 1420.94052

Chillotti, I; Gama, N; Georgieva, M et al. Tfhe: fast fully homomorphic encryption over the torus. J Cryptol; 2019; 33, 1 pp. 34-91.4051995 [DOI: https://dx.doi.org/10.1007/s00145-019-09319-x] 1455.94141

Chillotti I, Ligier D, Orfila JB, et al (2021) Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE. In: Advances in cryptology—ASIACRYPT 2021: 27th international conference on the theory and application of cryptology and information security, Singapore, 6–10 Dec 2021, Proceedings, Part III 27. Springer, pp 670–699

Chou E, Beal J, Levy D, et al (2018) Faster cryptonets: leveraging sparsity for real-world encrypted inference. arXiv preprint arXiv:1811.09953

Cong K, Moreno RC, da Gama MB, et al (2021) Labeled psi from homomorphic encryption with reduced computation and communication. In: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 1135–1150

De Micheli, G; Kim, D; Micciancio, D et al. Faster amortized FHEW bootstrapping using ring automorphisms; 2024; Berlin, Springer: pp. 322-353. [DOI: https://dx.doi.org/10.1007/978-3-031-57728-4_11] 1551.94107

Dhiman, S; Mahato, GK; Chakraborty, SK. Homomorphic encryption library, framework, toolkit and accelerator: a review. SN Comput Sci; 2023; 5, 1 24. [DOI: https://dx.doi.org/10.1007/s42979-023-02316-9] 1515.90019

Ducas, L; Micciancio, D. FHEW: bootstrapping homomorphic encryption in less than a second; 2015; Berlin, Springer: pp. 617-640. [DOI: https://dx.doi.org/10.1007/978-3-662-46800-5_24] 1370.94509

Ducas, L; Stehlé, D. Sanitization of FHE ciphertexts; 2016; Berlin, Springer: pp. 294-310. [DOI: https://dx.doi.org/10.1007/978-3-662-49890-3_12] 1384.94057

ElGamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms; 2000; Berlin, Springer: pp. 10-18. [DOI: https://dx.doi.org/10.1007/3-540-39568-7_2] 1359.94590

Engelsma, JJ; Jain, AK; Boddeti, VN. Hers: homomorphically encrypted representation search. IEEE Trans Biomet Behav Identity Sci; 2022; 4, 3 pp. 349-360. [DOI: https://dx.doi.org/10.1109/TBIOM.2021.3139866]

Fan J, Vercauteren F (2012) Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive

Gama N, Izabachène M, Nguyen PQ, et al (2016a) Structural lattice reduction: generalized worst-case to average-case reductions and homomorphic cryptosystems. In: Advances in cryptology—EUROCRYPT 2016: 35th annual international conference on the theory and applications of cryptographic techniques, Vienna, Austria, 8–12 May 2016, Proceedings, Part II 35. Springer, pp 528–558

Gama, N; Izabachène, M; Nguyen, PQ et al. Structural lattice reduction: generalized worst-case to average-case reductions and homomorphic cryptosystems; 2016; Berlin, Springer: pp. 528-558. [DOI: https://dx.doi.org/10.1007/978-3-662-49896-5_19] 1371.94635

Gentry C (2009) Fully homomorphic encryption using ideal lattices. In: Proceedings of the forty-first annual ACM symposium on theory of computing. ACM, STOC’09. https://doi.org/10.1145/1536414.1536440

Gentry, C; Sahai, A; Waters, B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based; 2013; Berlin, Springer: pp. 75-92. [DOI: https://dx.doi.org/10.1007/978-3-642-40041-4_5] 1310.94148

Gilad-Bachrach R, Dowlin N, Laine K, et al (2016) Cryptonets: applying neural networks to encrypted data with high throughput and accuracy. In: International conference on machine learning, PMLR, pp 201–210

Goldreich O, Micali S, Wigderson A (2019) How to play any mental game, or a completeness theorem for protocols with honest majority. In: Providing sound foundations for cryptography: on the work of Shafi Goldwasser and Silvio Micali, pp 307–328

Gong, Y; Chang, X; Mišić, J et al. Practical solutions in fully homomorphic encryption: a survey analyzing existing acceleration methods. Cybersecurity; 2024; 7, 1 5. [DOI: https://dx.doi.org/10.1186/s42400-023-00187-4] 1547.81204

Group A (2024) Secretflow: a privacy-preserving computing framework. https://github.com/secretflow/secretflow. Accessed 06 Jan 2025

Guimarães, A; Pereira, HVL; van Leeuwen, B. Amortized bootstrapping revisited: simpler, asymptotically-faster, implemented; 2023; Singapore, Springer: pp. 3-35. [DOI: https://dx.doi.org/10.1007/978-981-99-8736-8_1] 1547.94370

Halevi, S; Shoup, V. Algorithms in HElib; 2014; Berlin, Springer: pp. 554-571. [DOI: https://dx.doi.org/10.1007/978-3-662-44371-2_31] 1343.94061

Halevi, S; Shoup, V. Bootstrapping for Helib. J Cryptol; 2021; 4196013 [DOI: https://dx.doi.org/10.1007/s00145-020-09368-7] 1460.94046

Halevi S, Shoup V (2024) Helib. https://github.com/homenc/HElib. Accessed 06 Jan 2025

Han, K; Ki, D. Better bootstrapping for approximate homomorphic encryption; 2020; Berlin, Springer: pp. 364-390. [DOI: https://dx.doi.org/10.1007/978-3-030-40186-3_16] 1457.94138

He K, Zhang X, Ren S, et al (2016) Identity mappings in deep residual networks. In: Computer vision—ECCV 2016: 14th European conference, Amsterdam, The Netherlands, 11–14 Oct 2016, Proceedings, Part IV 14. Springer, pp 630–645

Henzinger A, Dauterman E, Corrigan-Gibbs H, et al (2023) Private web search with tiptoe. In: Proceedings of the 29th symposium on operating systems principles, pp 396–416

Hong, S; Kim, S; Choi, J et al. Efficient sorting of homomorphic encrypted data with k-way sorting network. IEEE Trans Inf Forensics Secur; 2021; 16, pp. 4389-4404. [DOI: https://dx.doi.org/10.1109/TIFS.2021.3106167] 1227.80021

Huang Z, Lu Wj, Hong C, et al (2022) Cheetah: lean and fast secure $\{$Two-Party$\}$ deep neural network inference. In: 31st USENIX security symposium (USENIX Security 22), pp 809–826

Ibarrondo A, Chabanne H, Despiegel V, et al (2023) Grote: group testing for privacy-preserving face identification. In: Proceedings of the 13th ACM conference on data and application security and privacy, pp 117–128

Inc. C (2024) Heaan: homomorphic encryption for arithmetic of approximate numbers. https://github.com/snucrypto/HEAAN. Accessed 17 Oct 2024

Jiang X, Kim M, Lauter K, et al (2018a) Secure outsourced matrix computation and application to neural networks. In: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security. ACM, CCS’18. https://doi.org/10.1145/3243734.3243837

Jiang X, Kim M, Lauter K, et al (2018b) Secure outsourced matrix computation and application to neural networks. In: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 1209–1222

Ju JH, Park J, Kim J, et al (2023) Neujeans: private neural network inference with joint optimization of convolution and bootstrapping. arXiv preprint arXiv:2312.04356

Jutla CS, Manohar N (2020) Modular Lagrange interpolation of the mod function for bootstrapping of approximate he. Cryptology ePrint Archive

Jutla, CS; Manohar, N. Sine series approximation of the mod function for bootstrapping of approximate HE; 2022; Berlin, Springer: pp. 491-520. [DOI: https://dx.doi.org/10.1007/978-3-031-06944-4_17] 1496.94053

Kales D, Rechberger C, Schneider T, et al (2019) Mobile private contact discovery at scale. In: 28th USENIX security symposium (USENIX Security 19), pp 1447–1464

Kim, A; Song, Y; Kim, M et al. Logistic regression model training based on the approximate homomorphic encryption. BMC Med Genomics; 2018; 11, pp. 23-31. [DOI: https://dx.doi.org/10.1186/s12920-018-0401-7] 1433.94087

Kim, A; Deryabin, M; Eom, J et al. General bootstrapping approach for RLWE-based homomorphic encryption. IEEE Trans Comput; 2024; 73, 1 pp. 86-96. [DOI: https://dx.doi.org/10.1109/tc.2023.3318405] 1528.94065

Kim, D; Guyot, C. Optimized privacy-preserving CNN inference with fully homomorphic encryption. IEEE Trans Inf Forensics Secur; 2023; 18, pp. 2175-2187. [DOI: https://dx.doi.org/10.1109/tifs.2023.3263631] 1476.92044

Kim J, Seo J, Song Y (2024b) Simpler and faster BFV bootstrapping for arbitrary plaintext modulus from CKKS. Cryptology ePrint Archive

Kim, S; Park, M; Kim, J et al. EvalRound algorithm in CKKS bootstrapping; 2022; Cham, Springer: pp. 161-187. [DOI: https://dx.doi.org/10.1007/978-3-031-22966-4_6] 1519.94143

Lee, E; Lee, JW; No, JS et al. Minimax approximation of sign function by composite polynomial for homomorphic comparison. IEEE Trans Depend Secure Comput; 2021; 19, 6 pp. 3711-3727. [DOI: https://dx.doi.org/10.1109/TDSC.2021.3105111] 1479.94208

Lee, E; Lee, JW; Kim, YS et al. Optimization of homomorphic comparison algorithm on RNS-CKKS scheme. IEEE Access; 2022; 10, pp. 26163-26176. [DOI: https://dx.doi.org/10.1109/ACCESS.2022.3155882] 1479.94208

Lee E, Lee JW, Lee J, et al (2022b) Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions. In: International conference on machine learning, PMLR, pp 12403–12422

Lee J, Lee E, Kim YS, et al (2023a) Optimizing layerwise polynomial approximation for efficient private inference on fully homomorphic encryption: a dynamic programming approach. arXiv preprint arXiv:2310.10349

Lee, JW; Lee, E; Lee, Y et al. High-precision bootstrapping of RNS-CKKS homomorphic encryption using optimal minimax polynomial approximation and inverse sine function; 2021; Berlin, Springer: pp. 618-647. [DOI: https://dx.doi.org/10.1007/978-3-030-77870-5_22] 1479.94208

Lee, JW; Kang, H; Lee, Y et al. Privacy-preserving machine learning with fully homomorphic encryption for deep neural network. IEEE Access; 2022; 10, pp. 30039-30054. [DOI: https://dx.doi.org/10.1109/access.2022.3159694] 1485.68235

Lee, Y; Lee, JW; Kim, YS et al. Near-optimal polynomial for modulus reduction using l2-norm for approximate homomorphic encryption. IEEE Access; 2020; 8, pp. 144321-144330. [DOI: https://dx.doi.org/10.1109/access.2020.3014369] 1497.94097

Lee, Y; Lee, JW; Kim, YS et al. High-precision bootstrapping for approximate homomorphic encryption by error variance minimization; 2022; Berlin, Springer: pp. 551-580. [DOI: https://dx.doi.org/10.1007/978-3-031-06944-4_19] 1496.94055

Lee, Y; Lee, JW; Kim, YS et al. High-precision bootstrapping for approximate homomorphic encryption by error variance minimization; 2022; Berlin, Springer: pp. 551-580. [DOI: https://dx.doi.org/10.1007/978-3-031-06944-4_19] 1496.94055

Lee, Y; Micciancio, D; Kim, A et al. Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption; 2023; Berlin, Springer: pp. 227-256. [DOI: https://dx.doi.org/10.1007/978-3-031-30620-4_8] 1528.94065

Li, B; Micciancio, D. On the security of homomorphic encryption on approximate numbers; 2021; Berlin, Springer: pp. 648-677. [DOI: https://dx.doi.org/10.1007/978-3-030-77870-5_23] 1479.94211

Lin G, Han W, Ruan W, et al (2024) Ents: an efficient three-party training framework for decision trees by communication optimization. arXiv preprint arXiv:2406.07948

Liu, FH; Wang, H. Batch bootstrapping I: a new framework for SIMD bootstrapping in polynomial modulus; 2023; Cham, Springer: pp. 321-352. [DOI: https://dx.doi.org/10.1007/978-3-031-30620-4_11] 1528.94066

Liu, FH; Wang, H. Batch bootstrapping II: bootstrapping in polynomial modulus only requires $\tilde{O}(1)$ FHE multiplications in amortization; 2023; Cham, Springer: pp. 353-384. [DOI: https://dx.doi.org/10.1007/978-3-031-30620-4_12] 1528.94067

Liu, Z; Wang, Y. Amortized functional bootstrapping in less than 7 ms, with $\tilde{O}(1)$ polynomial multiplications; 2023; Singapore, Springer: pp. 101-132. [DOI: https://dx.doi.org/10.1007/978-981-99-8736-8_4] 1547.94387

Liu Z, Micciancio D, Polyakov Y (2022) Large-precision homomorphic sign evaluation using FHEW/TFHE bootstrapping. In: International conference on the theory and application of cryptology and information security. Springer, Berlin, pp 130–160

Lu Wj, Huang Z, Zhang Q, et al (2023) Squirrel: a scalable secure $\{$Two-Party$\}$ computation framework for training gradient boosting decision tree. In: 32nd USENIX security symposium (USENIX Security 23), pp 6435–6451

Mahdavi RA, Kerschbaum F (2022) Constant-weight $\{$PIR$\}$: single-round keyword $\{$PIR$\}$ via constant-weight equality operators. In: 31st USENIX security symposium (USENIX Security 22), pp 1723–1740

Marandi, A; Alves, PGM; Aranha, DF et al. Lattice-based homomorphic encryption for privacy-preserving smart meter data analytics. Comput J; 2024; 67, 5 pp. 1687-1698.4761740 [DOI: https://dx.doi.org/10.1093/comjnl/bxad093] 1544.14005

Marcolla, C; Sucasas, V; Manzano, M et al. Survey on fully homomorphic encryption, theory, and applications. Proc IEEE; 2022; 110, 10 pp. 1572-1609. [DOI: https://dx.doi.org/10.1109/JPROC.2022.3205665] 1422.00030

Microsoft (2018) Sealpir: private information retrieval using seal. https://github.com/microsoft/SealPIR. Accessed 06 Jan 2025

Microsoft (2021a) Apsi: C++ library for asymmetric psi. https://github.com/microsoft/APSI. Accessed 06 Jan 2025

Microsoft (2021b) Eva:compiler for the seal homomorphic encryption library. https://github.com/microsoft/EVA. Accessed 06 Jan 2025

Microsoft (2024) Microsoft seal (simple encrypted arithmetic library). https://github.com/microsoft/SEAL. Accessed 06 Jan 2025

Mohassel P, Rindal P (2018) Aby3: a mixed protocol framework for machine learning. In: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 35–52

Mohassel P, Zhang Y (2017) Secureml: a system for scalable privacy-preserving machine learning. In: 2017 IEEE symposium on security and privacy (SP). IEEE, pp 19–38

Moore C, O’Neill M, O’Sullivan E, et al (2014) Practical homomorphic encryption: a survey. In: 2014 IEEE international symposium on circuits and systems (ISCAS). IEEE, pp 2792–2795

Morrison T, Scheffler S, Pal B, et al (2021) Private outsourced translation for medical data. In: Protecting privacy through homomorphic encryption, pp 107–116

Mouchet CV, Bossuat JP, Troncoso-Pastoriza JR, et al (2020) Lattigo: a multiparty homomorphic encryption library in go. In: Proceedings of the 8th workshop on encrypted computing and applied homomorphic cryptography, pp 64–70

Mughees MH, Chen H, Ren L (2021) Onionpir: response efficient single-server PIR. In: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 2292–2306

Paillier, P. Public-key cryptosystems based on composite degree residuosity classes; 1999; Berlin, Springer: pp. 223-238. [DOI: https://dx.doi.org/10.1007/3-540-48910-x_16] 0933.94027

Pereira HVL (2021a) Bootstrapping fully homomorphic encryption over the integers in less than one second. In: Public-key cryptography—PKC 2021: 24th IACR international conference on practice and theory of public key cryptography, virtual event, May 10–13, 2021, Proceedings, Part I 24. Springer, pp 331–359

Pereira, HVL. Bootstrapping fully homomorphic encryption over the integers in less than one second; 2021; Berlin, Springer: pp. 331-359. [DOI: https://dx.doi.org/10.1007/978-3-030-75245-3_13] 1479.94242

Popa, RA; Redfield, CM; Zeldovich, N et al. Cryptdb: processing queries on an encrypted database. Commun ACM; 2012; 55, 9 pp. 103-111. [DOI: https://dx.doi.org/10.1145/2330667.2330691] 1311.94082

Project TP (2024) Palisade lattice cryptography library. https://gitlab.com/palisade/palisade-release. Accessed 06 Jan 2025

Pulido-Gaytan LB, Tchernykh A, Cortés-Mendoza JM, et al (2020) A survey on privacy-preserving machine learning with fully homomorphic encryption. In: Latin American high performance computing conference. Springer, pp 115–129

Ren, X; Su, L; Gu, Z et al. Heda: multi-attribute unbounded aggregation over homomorphically encrypted database. Proc VLDB Endow; 2022; 16, 4 pp. 601-614. [DOI: https://dx.doi.org/10.14778/3574245.3574248]

Resende ACD, Aranha DF (2018) Faster unbalanced private set intersection. In: Financial cryptography and data security: 22nd international conference, FC 2018, Nieuwpoort, Curaçao, February 26–March 2, 2018, Revised Selected Papers 22. Springer, pp 203–221

Riazi MS, Weinert C, Tkachenko O, et al (2018) Chameleon: a hybrid secure computation framework for machine learning applications. In: Proceedings of the 2018 on Asia conference on computer and communications security, pp 707–721

Rivest, RL; Adleman, L; Dertouzos, ML et al. On data banks and privacy homomorphisms. Found Secure Comput; 1978; 4, 11 pp. 169-180.5212540368.94005

Rivest, RL; Shamir, A; Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM; 1983; 26, 1 pp. 96-99. [DOI: https://dx.doi.org/10.1145/357980.358017] 0368.94005

Rouhani BD, Riazi MS, Koushanfar F (2018) Deepsecure: scalable provably-secure deep learning. In: Proceedings of the 55th annual design automation conference, pp 1–6

Son Y, Cheon JH (2019) Revisiting the hybrid attack on sparse secret LWE and application to he parameters. In: Proceedings of the 7th ACM workshop on encrypted computing; applied homomorphic cryptography. ACM, CCS’19, pp 11–20. https://doi.org/10.1145/3338469.3358941

Tan, BHM; Lee, HT; Wang, H et al. Efficient private comparison queries over encrypted databases using fully homomorphic encryption with finite fields. IEEE Trans Depend Secure Comput; 2020; 18, 6 pp. 2861-2874. [DOI: https://dx.doi.org/10.1109/TDSC.2020.2967740] 1186.94376

Unal, D; Al-Ali, A; Catak, FO et al. A secure and efficient internet of things cloud encryption scheme with forensics investigation compatibility based on identity-based encryption. Futur Gener Comput Syst; 2021; 125, pp. 433-445. [DOI: https://dx.doi.org/10.1016/j.future.2021.06.050] 1510.90082

Vaswani A (2017) Attention is all you need. In: Advances in neural information processing systems

Viand A, Jattke P, Hithnawi A (2021) Sok: fully homomorphic encryption compilers. In: 2021 IEEE symposium on security and privacy (SP). IEEE, pp 1092–1108

Wang R, Wen Y, Li Z, et al (2024) Circuit bootstrapping: faster and smaller. In: Annual international conference on the theory and applications of cryptographic techniques. Springer, pp 342–372

Wang X, Tang H, Wang S, et al (2018) Idash secure genome analysis competition 2017

Wang Y, Liu J, Luo M, et al (2022) Privacy-preserving face recognition in the frequency domain. In: Proceedings of the AAAI conference on artificial intelligence, pp 2558–2566

Wood, A; Najarian, K; Kahrobaei, D. Homomorphic encryption for machine learning in medicine and bioinformatics. ACM Comput Surv (CSUR); 2020; 53, 4 pp. 1-35. [DOI: https://dx.doi.org/10.1145/3394658] 1395.68115

Wood, A; Najarian, K; Kahrobaei, D. Homomorphic encryption for machine learning in medicine and bioinformatics. ACM Comput Surv; 2020; 53, 4 pp. 1-35. [DOI: https://dx.doi.org/10.1145/3394658] 1395.68115

Xiang B, Zhang J, Deng Y, et al (2023) Fast blind rotation for bootstrapping FHES. In: Annual international cryptology conference. Springer, pp 3–36

Yang, W; Wang, S; Cui, H et al. A review of homomorphic encryption for privacy-preserving biometrics. Sensors; 2023; 23, 7 3566. [DOI: https://dx.doi.org/10.3390/s23073566] 1522.35376

Yang Z, Xie X, Shen H, et al (2021) Tota: fully homomorphic encryption with smaller parameters and stronger security. Cryptology ePrint Archive

Zama (2022a) Concrete ML: a privacy-preserving machine learning library using fully homomorphic encryption for data scientists. https://github.com/zama-ai/concrete-ml

Zama (2022b) TFHE-rs: a pure rust implementation of the TFHE scheme for Boolean and integer arithmetics over encrypted data. https://github.com/zama-ai/tfhe-rs. Accessed 06 Jan 2025

Zama (2024) Confidential EVM smart contracts using fully homomorphic encryption. https://github.com/zama-ai/fhevm

Zhang, J; Cheng, X; Yang, L et al. Sok: fully homomorphic encryption accelerators. ACM Comput Surv; 2024; 56, 12 pp. 1-32. [DOI: https://dx.doi.org/10.1145/3676955] 1551.94154

Zhang J, Yang X, He L, et al (2024b) Secure transformer inference made non-interactive. Cryptology ePrint Archive

Zhang, P; Huang, T; Sun, X et al. Privacy-preserving and outsourced multi-party k-means clustering based on multi-key fully homomorphic encryption. IEEE Trans Depend Secure Comput; 2022; 20, 3 pp. 2348-2359.1199.68100

Zhang Z, Bian S, Zhao Z, et al (2024c) Arcedb: an arbitrary-precision encrypted database via (amortized) modular homomorphic encryption. In: Proceedings of the 2024 on ACM SIGSAC conference on computer and communications security, pp 4613–4627

Zhao, B; Yuan, J; Liu, X et al. Soci: a toolkit for secure outsourced computation on integers. IEEE Trans Inf Forensics Secur; 2022; 17, pp. 3637-3648. [DOI: https://dx.doi.org/10.1109/TIFS.2022.3211707] 1538.90111