Efficient Arithmetic-and-Comparison Homomorphic Encryption with Space Switching
arXiv:2604.19890v1 [cs.CR] 21 Apr 2026
Erwin Eko Wahyudi, Yan Solihin, Qian Lou∗ University of Central Florida {wahyudierwin, yan.solihin, qian.lou}@ucf.edu Abstract—Fully homomorphic encryption (FHE) enables computation on encrypted data without decryption, making it central to privacy-preserving applications. However, no existing scheme efficiently supports both arithmetic and comparison operations in a unified framework. Prior approaches such as scheme switching and polynomial approximation face serious limitations: switching incurs prohibitive overhead for large inputs, while approximation methods introduce errors near critical points, restricting use in accuracy-sensitive tasks. We propose space switching method to integrate arithmetic and comparison computation seamlessly within FV-style schemes. Our approach identifies that the two types of operations require different plaintext spaces and introduces two procedures: a reduction step to transition from the number space Zpr to the digit space Zp , and a modulus-raising step to map results back to Zpr . This design enables continuous evaluation of arithmetic and comparison within the same scheme. Experiments show that our method achieves up to 17× faster performance than scheme switching and 15× faster than direct comparison on database workloads, demonstrating its practicality for real-world privacy-preserving computation. Code and artifacts are available at https://github.com/UCF-Lou-Lab-PET/ Universal-BGV.
1. Introduction Fully homomorphic encryption (FHE) enables computation directly on encrypted data without decryption, making it a powerful primitive for secure computation. Since Gentry’s seminal construction [25], numerous schemes have been proposed [9], [10], [15], [19], [20], [21], each improving efficiency or expanding functionality, and FHE has been applied to privacy-preserving machine learning [22], [28], [41], [43], [45], [46], [47], genomic data analysis [35], [52], [62], and finance [4], [31]. Broadly, schemes fall into word-wise and bit-wise families: word-wise schemes such as BFV [9], [21], BGV [10], and CKKS [15] are highly efficient for arithmetic (e.g., matrix multiplication and convolution) and benefit from SIMD packing [54], but evaluating non-arithmetic functions like comparisons is very expensive. In contrast, bit-wise schemes such as FHEW [20] and TFHE [19] support logic operations via functional ∗ Qian Lou is the corresponding author: [email protected].
bootstrapping and Boolean/LUT circuits, yet cannot perform arithmetic operations efficiently (e.g., a 16-bit multiplication can take ∼30 s [48]). This yields a dilemma: word-wise schemes excel at arithmetic operations but struggle with logic operations, while bit-wise excel at logic operations but struggle with arithmetic operations. One of the most pressing logic operations is comparison, which is relied upon by many important applications. For example, a single database query may involve a mixture of comparison and arithmetic operations. Figure 1 illustrates an example query pipeline where ciphertexts are compared (via the WHERE clause) and then multiplied and summed to produce encrypted query results. 1 Similarly, in privacypreserving machine learning applications, a single inference often involves both arithmetic operations (convolutions and matrix multiplications) and comparisons (in activation layers like ReLU). Some specialized workarounds exist, for example a comparison can be approximated using polynomials which allows converting it into arithmetic operations. However, an approximation is not always effective. For example, in genomics applications [35], [52], [62], exact comparisons are critical, since small errors can lead to incorrect conclusions. They may also result in non-negligible accuracy loss especially if low degree polynomials are used [28]. Even with high-degree polynomials, approximation methods (with CKKS) are generally valid only over small intervals, such as [−1, 1] [16], [39], and are inherently inaccurate near critical points such as zero. A more general-purpose approach to enabling mixed arithmetic and comparison uses homomorphic scheme switching [8], [48], where arithmetic is performed with word-wise schemes and comparison with bit-wise schemes, or functional bootstrapping [3], [38], where comparisons are performed via lookup tables (LUTs). While these approaches leverage the strengths of each category, scheme conversions and LUT evaluations remain prohibitively costly. Because the complexity grows exponentially with input bit-width, they typically restrict the bit-width [3], support only narrow intervals such as [−8, 8] [18], and may require additional bootstrapping [5]. 1. While some specialized solutions exist [7], [36], [37], [55] which show how word-wise FHE can filter (equality tests) and return exact matches, they are largely limited to retrieval-style queries and do not directly support aggregations such as SUM, which are essential for analytics.
Table ID
Price
Qty
1 2 3
1000 400 3000
7 3 10
4
600
6
Query SELECT SUM(Price * Qty) as TOTAL FROM Table WHERE Qty >= 5
CtxtPrice
1000
CtxtQty
7
400 3
3000
600
10
6
1
1
7000
1200
30000
3600
1
0
1
1
7000
0
30000
3600
0
0
Comparison Evaluation
RQty
1
0
SUM
Filter Result
1
0
1
1
Homomorphic Predicate Evaluation
40600
0
Homomorphic Aggregation Evaluation
Figure 1: Database queries inherently combine comparison (e.g., filtering with predicates) and arithmetic (e.g., multiplication and aggregation), requiring both to be supported efficiently under homomorphic encryption. Thus, we propose a new approach to address these limitations. The main idea is that comparing two numbers can be decomposed into multiple comparisons of their digits and their aggregation. Our key observation is that performing comparison at the digit level is much more efficient homomorphically because we can reduce the ciphertext number space to a much smaller digit space. Thus, in our space switching approach, we convert numbers from the number space Zpr to their digits, each in the base-p digit space Zp (where pr represents the plaintext modulus). This greatly reduces complexity, since we deal with much smaller polynomials (of degree p − 1 rather than pr − 1). Effectively, we transform a number-space comparison that incurs √ O pr/2 multiplications, into digit-space total of O r pr multiplications. This advantage grows as the numbers being compared are enlarged. For example, if r is fixed at 5, then as p grows, the gap in √ the number√of multiplications is quadratic to p, i.e. O p2 p vs. O p Practically, our space switching method offers multiple advantages over scheme switching. It avoids costly crossscheme conversions between word-wise and bit-wise HE, and supports large bit-widths and arbitrary ranges, while at the same time retains the SIMD benefit of the BGV/BFV schemes. It does not require special encodings and works fully homomorphically end to end. We integrated our space switching into a productiongrade library (HElib), enabling end-to-end performance evaluation that includes all the overheads including those from switching between number and digit spaces. We evaluate across multiple bit-widths and representative workloads against two baselines that support arithmetic and exact comparison. For primitive operators (e.g., LT, EQ), our method achieves up to 130× speedup over Morimura et al. [50] and up to 40× speedup over scheme switching [6] in the amortized (per-slot) sense. In a database workload, space switching achieves up to 17× speedup over scheme switching [6] and up to 15× over Morimura et al. [50]. We report complete configurations and breakdowns in Sections 6–7. To summarize, this paper makes the following contributions:
•
•
•
We present a novel space switching approach that enables mixed arithmetic and comparison operations by transitioning between number and digit spaces. We propose an efficient digit extraction technique to convert from number to digit space and a modulus raising technique to convert from digit to number space. The digit extraction technique is adapted from BGV/BFV bootstrapping but we adapt it in order order to remove its inefficiency. We integrate our technique into the production-grade FHE library HElib, and evaluate primitive operators and a database workload across multiple bitwidths. We show that our space switching technique achieves huge speedups over the state-of-theart scheme switching.
2. Related Works Table 1 organizes prior efforts on enabling logic (we focus on comparison) operations in homomorphic encryption into distinct categories, clarifying their underlying approaches and trade-offs. The table highlights key properties, including support for SIMD packing, arithmetic capability, exactness of comparison evaluation, scalability to large inputs, and the underlying scheme. SIMD packing is important to amortize a long latency computation over many operations, and is a key advantage of word-wise FHE schemes over bit-wise ones. Arithmetic capability is important for most FHE applications but some FHE schemes do not support them. Exactness of computation is important for many applications, especially when comparisons are involved. Scalability to large input determines how fast computation can be performed on larger bit widths; small bit widths restrict the applicability to a narrower set of applications. The table allows us to compare very different lines of work on a common basis and to identify where existing techniques fall short. Bit-wise approach. Bit-wise schemes [11], [19], [20] in general have very low arithmetic performance. For instance, multiplying two 16-bit integers in TFHE can take up to 30
TABLE 1: Comparison of prior works supporting comparison operations in FHE. Approach Bit-wise
Scheme Switching
Approximation
Interpolation
Functional Bootstrapping Others
Name
SIMD
Arithmetic
Exact
Bit-width scalability
TFHE [19]
✗
✗
✓
binary-circuit depth
Scheme TFHE
Chakraborty [11]
✗
✗
✓
binary-circuit depth
TFHE BFV/CKKS/TFHE
Chimera [8]
✗
✓
✓
binary-circuit depth
Pegasus [48]
✗
✓
✓
binary-circuit depth
BFV/CKKS/TFHE
HE3 DB [6]
✗
✓
✓
binary-circuit depth
BFV/CKKS/TFHE
Cheon et al. [16]
✓
✓
✗
approximation polynomial degree
CKKS
Lee et al. [39]
✓
✓
✗
Tan et al. [55]
✓
✗
✓
BFV/BGV BFV/BGV
Iliashenko et al. [33]
✓
✗
✓
approximation polynomial degree √ O(r p) √ O(r p)
Morimura et al. [50]
✓
✓
✓
O(pr/2 )
CKKS BFV/BGV
Liu et al. [40]
✓
✓
✓
LUT/domain size
BFV/BGV
Lee et al. [38]
✓
✓
✓
LUT/domain size
BFV/BGV/CKKS
Alexandru et al. [3]
✓
✓
✗
LUT/domain size
CKKS
XCMP [49]
✗
✗
✓
BFV/BGV
✓
✓
✓
input-domain size √ O(r pr)
Ours (Space Switching)
seconds [48]. While LUT-based bootstrapping enables accurate comparison, relying solely on bit-wise FHE becomes impractical for workloads dominated by arithmetic [34], [44], [45], [47]. Scheme switching. Homomorphic scheme switching performs arithmetic operations with word-wise schemes and switches to bit-wise schemes to perform comparison [8], [48]. The switching time is very costly and increases exponentially with the input bit-width, hence they typically limit the bit-width and only support narrow intervals such as [−8, 8] [18]. Each switch is often followed by bootstrapping [5], which is one of the most expensive operations in word-wise HE and is generally avoided in practice [33], [42], [57], [59]. Polynomial approximation. For the CKKS scheme, polynomial approximation is a popular method, which approximates a comparison function with polynomials. Several works [16], [17], [39], [60], [61] approximate comparison functions using either high-degree polynomials or compositions of lower-degree ones. The comparison function is fundamental, as it forms the basis for many comparison primitives such as step and sign functions, and can also be used to construct LUTs for arbitrary non-arithmetic functions [14]. However, these approximation methods are generally valid only over small intervals, such as [−1, 1] [16], [39], and are inherently inaccurate near critical points such as zero. Achieving higher accuracy and precision generally requires higher polynomial degree and larger CKKS scales, increasing depth, noise, and runtime, yet a zero-margin cannot be certified, so exact correctness is not guaranteed. Such errors make them unsuitable for applications requiring exact correctness, including genomics [35], [52], [62] and finance [4], [31]. Polynomial interpolation. For BFV/BGV schemes, exact comparison can be supported via polynomial interpolation. Prior works [33], [55] have demonstrated that comparison functions can be expressed as interpolation poly-
BFV/BGV
nomials over integers modulo p. Moreover, since FV-style schemes support SIMD, the cost of these comparisons can be amortized across many slots, promising to yield perinteger latencies comparable to or even better than those in bit-wise schemes [33]. However, the state-of-the-art comparison method [33], [58] relies on special plaintext encodings that prevent interpolation-based comparison from being used together with arithmetic operations in the same scheme [16], [50]. Another potential approach is to construct comparison polynomials directly in the native plaintext number space Zpr . However, the degree of such polynomials grows exponentially with r (up to pr ), making direct comparison evaluation in Zpr infeasible. Functional bootstrapping. Recently, several functional bootstrapping methods [3], [38], [40] have been proposed to allow arbitrary function computation during the bootstrapping process. Functional bootstrapping refreshes ciphertexts and applies a chosen function simultaneously, effectively removing noise while completing an LUT evaluation. Specifically, Lee et al. [38] proposed a functional bootstrapping technique that takes an RLWE ciphertext, i.e., CKKS or BFV, as input and outputs the refreshed BFV ciphertext, building upon BFV-style bootstrapping. However, such BFV-style bootstrapping is far from efficient; for instance, it can take about 3 minutes for a single evaluation due to the intrinsically inefficient slot utilization of BFV-style bootstrapping [3]. To address this issue, Alexandru et al. [3] presented a general functional bootstrapping technique based on CKKS-style bootstrapping, which has the best throughput among all FHE methods, to improve amortized performance. However, this method suffers from high computational complexity for large input spaces. Their experimental results are limited to 12-bit LUTs because the scaling factor nears the limit for 64-bit modular operations, and the complexity of polynomial evaluation increases significantly, i.e., approximately 1 minute per evaluation for 9-bit LUTs, but about 10 minutes for 12-bit LUTs.
Others. There are specialized methods targeting comparison, but they are limited in generality or efficiency. For example, XCMP [49] encodes numbers into exponents to facilitate comparison, but this design precludes SIMD packing and does not support arithmetic. Overall, our space switching enables arithmetic and comparison operations within a single FHE scheme (BFV/BGV), hence it retains its SIMD advantage. Due to a much higher efficiency, it supports exact comparison even with large inputs.
3. Background 3.1. The BGV Scheme The BGV scheme is a lattice-based cryptographic construction built on the Ring Learning with Errors (RLWE) assumption [10]. Although mathematically complex, RLWE is a fundamental problem that underpins the security of the scheme. The main parameters of BGV are summarized in Table 2, including p, r, m, n, and Q. The value pr specifies the plaintext modulus, whereas Q defines the ciphertext modulus. In practice, Q is chosen much larger than p TABLE 2: Parameters used in BGV. Parameter pr m n L Q λ
Description Plaintext coefficient modulus. Order of the cyclotomic ring. Degree of the cyclotomic polynomial. Maximum multiplicative level. Q Product of prime moduli: Q = L i=0 qi . Security parameter of a BGV instance.
In this setting, Φm (x) denotes the m-th cyclotomic polynomial of degree n. The relation between m and n is determined by the Euler totient function ϕ, with n = ϕ(m). Earlier works often restricted n to powers of two for simplicity, but more recent research suggests that non-power-of-two values of n yield better performance and stronger security flexibility [27], [33]. The polynomial ring Rpr is defined as Zpr [x]/(Φm (x)), consisting of polynomials modulo Φm (x) with coefficients in Zpr . Likewise, RQ is defined with modulus Q. In the BGV scheme, plaintexts are encoded in Rpr , while ciphertexts are represented in RQ . Let d = Ord(m, p) denote the multiplicative order of p modulo m, i.e. the smallest positive integer d such that pd ≡ 1 (mod m). According to the algebraic structure described in [54], the cyclotomic polynomial Φm (x)Qcan be deℓ composed into ℓ irreducible factors as Φm (x) = i=1 Fi (x) r (mod p ), where ℓ = ϕ(m)/d and each Fi (x) has degree d. Consequently, the quotient ring can be represented as Rpr = Zpr [x]/Φm (x) ∼ = Zpr [x]/F1 (x)⊗· · ·⊗Zpr [x]/Fℓ (x). That means a plaintext slot is an element of the extension field Zpr [x]/Fi (x), represented as a polynomial of degree at most d, which may in particular be a constant value in Zpr . The parameter ℓ also corresponds to the number of
Algorithm 1: BGV Encryption Input: plaintext m ∈ Rpr , secret key s ∈ RQ 2 Output: ciphertext c = (c0 , c1 ) ∈ RQ 1 c1 ← sample from (RQ ); 2 e ← sample from Rp ; r 3 c0 ← m + p · e − c1 · s; 4 return c = (c0 , c1 ); Algorithm 2: BGV Decryption 2 Input: ciphertext c = (c0 , c1 ) ∈ RQ , secret key s ∈ RQ Output: plaintext m ∈ Rpr ∗ 1 m ← c0 + c1 · s; ∗ r 2 m ← m mod p ; 3 return m;
available plaintext slots in BGV. These slots enable SIMDstyle packing, where each slot represents one plaintext value. Homomorphic addition and multiplication are performed on the ciphertext in RQ , while the corresponding slot values are recovered in the plaintext space after decryption. In the BGV scheme, the message m is encoded as a polynomial from Rpr . The secret key s ∈ RQ is a “small” polynomial, with each coefficient drawn from the set {−1, 0, 1}. The ciphertext corresponding to m is c = (c0 , c1 ) with c0 , c1 ∈ RQ , satisfying c0 + c1 · s ≡ m + pr e
(mod Q).
(1)
Having the plaintext m and a secret key s, the encryption process begins by sampling a polynomial c1 from RQ uniformly. The polynomial c0 in RQ is then computed based on c1 and an additional random polynomial e, which is generated from a predefined Gaussian distribution. This computation results in the ciphertext pair c0 and c1 , as shown in Algorithm 1. Decryption is performed by Algorithm 2: given a ciphertext c = (c0 , c1 ), it recovers the plaintext m. The parameters L and Q determine the supported multiplicative depth in FHE, i.e., the maximum number of sequential multiplications that can be applied to a ciphertext along any computation path. Multiplicative depth counts the longest chain of sequential multiplications, rather than the total number of multiplications. For example, computing R = (ab)(cd) requires three multiplications in total, but its multiplicative depth is only two: one level to compute R1 = ab and R2 = cd, and a second level to compute R = R1 R2 . If the multiplicative depth of a ciphertext exceeds the supported level L, then decryption becomes invalid, meaning that the decrypted result no longer matches the original plaintext.
3.2. Polynomial Interpolation The non-arithmetic operations are typically evaluated via polynomial interpolation in the field Zp in the FV-
style HE schemes. The interpolation polynomials are key to the comparison function [33], [55] as well as other non-arithmetic functions like modulo, Hamming weight and division [32], [50]. The construction of these interpolation polynomials relies on important theorems and lemmas that we will describe below. Theorem 1 (Fermat’s Little Theorem on Zp ). Let p be a prime, for any a ∈ Zp \ {0}, we have ap−1 = 1
(mod p).
With Fermat’s Little Theorem in Theorem 1, we can evaluate the equality function easily over Zp . The equality check for x, y ∈ Zp can be computed as (
1 0
FEQ (x, y) = 1 − (x − y)p−1 =
if x = y . otherwise
(2)
Based on the equality function, any multi-variable function can be evaluated via a multi-variate interpolation polynomial according to the following lemma: Lemma 1. Every n-variable function f : Znp → Zp is a polynomial function represented by a n-variate polynomial Pf (X1 , ..., Xn ) of degree at most p − 1 in each variable: Pf (X1 , ..., Xn ) =
X
f (a)
a∈Fn p
n Y
(1 − (Xi − ai )p−1 ),
i=1
where ai is the i-th coordinate of the length-n vector a. With Lemma 1, we know that for a uni-variate function f : Zp → Zp , the uni-variate interpolation polynomial has the following form: Pf (X) =
p−1 X
f (a) 1 − (X − a)p−1 .
a=0
The above interpolation polynomial has at most degree (p − 1). Such a univariate polynomial of degree (p − 1) √ can be computed with at most p − 1 non-scalar multiplications thanks to the following theorem and the PatersonStockmeyer algorithm: Theorem 2 (from [51]). Any polynomial of degree d over √ a ring can be evaluated using O( d) non-scalar multiplications and ⌈log2 d⌉ + 1 multiplicative levels. We illustrate the interpolation process using the lessthan-zero (LT 0) function over Zp , defined as ( 1 if x < 0, LT 0(x) = (3) 0 otherwise. The mapping between inputs and outputs for the LT 0 function is shown in Table 3. According to Theorem 1, we can interpolate LT 0 by summing the equality polynomials for all negative inputs: FLT 0 (x) =
−1 X i=−(p−1)/2
FEQ (x, i).
TABLE 3: The truth table for the LT 0 function over Zp . x LT 0(x)
− p−1 2 1
... ...
-1 1
0 0
1 0
... ...
p−1 2
0
By Lemma 1, the resulting polynomial √ FLT 0 (x) has degree p − 1, which can be evaluated in p − 1 non-scalar multiplications. This construction shows how the LT 0 function can be expressed as a polynomial suitable for homomorphic evaluation.
4. FV-Style Comparison Challenges In this section, we present a systematic analysis of the challenges of performing comparisons, such as lessthan (LT) and equality (EQ), in FV-style schemes. Section 4.1 establishes inherent limitations for comparisons over Zpr , and Section 4.2 reviews special plaintext encodings for comparisons proposed in [33], [55], highlighting their incompatibility with standard arithmetic within the same scheme.
4.1. Limitations of Comparison in Zpr The BGV and BFV schemes support SIMD-style computation by utilizing slots, where each slot contains an integer a ∈ Zpr . Under this representation, arithmetic operations such as addition and multiplication are well-defined and yield the correct results modulo pr . The situation is different for comparison. For example, consider the equality test. To determine whether two integers a, b ∈ Zpr are equal, one can equivalently test whether a − b = 0. This motivates the definition of the equality function EQ, where EQ(x, 0) = 1 for x = 0 and EQ(x, 0) = 0 otherwise. Over Zp (i.e., r = 1), the EQ function can be expressed by a polynomial of degree p − 1 as shown in Eq. (2). However, over Zpr with r > 1, two challenges arise. First, a direct comparison of EQ over the entire domain Zpr requires a polynomial of degree pr − 1, which is infeasible in practice due to the exponential growth in degree and the corresponding multiplicative depth. Second, by the theory of polyfunctions [23], for r > 1 the equality predicate over Zpr is not a polyfunction, meaning that it cannot be represented as a polynomial with integer coefficients over Zpr . This limitation is not restricted to equality. The less-than (LT) function over Zpr , defined by ( 1 if x < 0, LT(x, 0) = 0 otherwise, suffers the same challenges as the EQ function. Therefore, both EQ and LT in the domain Zpr , particularly for r > 1, are nontrivial and cannot be performed using polynomial interpolation. This reveals a fundamental obstacle to supporting comparison directly in the Zpr domain and motivates the use of the Zp domain, where such comparisons can be expressed via interpolation polynomials over Zp .
4.2. Limitations of Plaintext Encoding for Comparison Prior works have proposed special encoding techniques to enable comparison on large numbers [33], [55]. For a number a ∈ Zpr , the first step is to decompose a into Pr−1 i its base-p digits (a0 , a1 , . . . , ar−1 ) = a p , where i i=0 each digit ai lies in Zp . This decomposition is carried out in cleartext before encryption. The digits are then encoded as a polynomial over the extension field Fpd , namely Pd−1 i i=0 ai X , which serves as the encoded plaintext. As a result, each ciphertext slot holds a polynomial that compactly represents an entire multi-digit To perform Pd−1number. i a X are extracted comparisons, the coefficients of i=0 i homomorphically [33], producing ciphertexts corresponding to the individual digits a0 , a1 , . . . , ar−1 with ai ∈ Zp . Once the digits are extracted in encrypted form, comparison polynomials defined over Zp can be applied to evaluate functions such as equality or less-than. Although this special plaintext encoding supports comparison, it does not naturally extend to general arithmetic operations such as multiplication and addition that produce integers larger than the modulus. This limitation arises because numbers are expressed in vector form, and the arithmetic between specially encoded numbers follows the rules of polynomial rings rather than integers. For example, consider p = 5 and d = 3. Integers can be decomposed into base-5 digits. Suppose x, y ∈ Z53 with x = 33 and y = 19. Under the special encoding, x is represented by its base-5 digits xi ∈ Z5 , i.e., {x0 , x1 , x2 } = {3, 1, 1}, and encoded as 3X 0 + 1X 1 + X 2 . Similarly, y is encoded as 4X 0 +3X 1 +0X 2 . Arithmetic on these encodings is carried out in the polynomial ring Z5 [X]/(X 3 + 1). Adding x and y yields x + y = 2X 0 + 4X 1 + X 2 . Decoding this result gives 47, which does not match the expected integer addition result of 33 + 19 = 52 modulo 53 . In summary, the special encoding is effective for applying comparisons over digits, but it is not compatible with standard integer arithmetic within the same ciphertext layout. Mixing arithmetic with such encodings would require re-encoding or additional conversions, which breaks the simplicity of the word-wise workflow. This motivates a different approach that keeps plaintexts as integers in Zpr for arithmetic, temporarily reduces to Zp only to evaluate comparisons, and then lifts the result back to Zpr , which we detail in Section 5.
5. Method This section presents our proposed method for interleaving arithmetic and comparison within a single FVstyle scheme. The main challenge is connecting the number space Zpr used for arithmetic and the digit space Zp used for comparison. Section 5.1 specifies the BGV extension that enables arithmetic over Zpr along with comparison evaluation. Section 5.2 details a homomorphic reduction from the original plaintext space Zpr to the digit space
Zp . Comparisons are then performed efficiently in the digit space Zp via polynomial interpolation (Section 5.3). Finally, Section 5.4 describes a modulus-raising step that restores the plaintext space from the digit space Zp back to Zpr , allowing continuous computation.
5.1. Connecting Arithmetic and Comparison Section 4.1 shows that comparisons in the plaintext space Zpr are nontrivial when r > 1. A natural alternative is to perform both arithmetic and comparison in Zp [50]. However, efficient evaluation of interpolation polynomials over Zp typically requires small primes, which limits the practicality for large inputs. For example, p ranges from 27 in [55], is at most 173 in [33], and at most 257 in [50]. Restricting all computation to Zp is therefore either unable to handle large numbers or incurs exponential overhead as the input bit-width increases. This motivates an alternative approach that separates arithmetic and comparison into their natural domains, Zpr for arithmetic and Zp for comparison, while providing an efficient conversion mechanism between them.
(1) Reduction
(2) Comparison
(3) Aggregation
(4) Modulus Raising
Figure 2: Overview of continuous evaluation of arithmetic operations over Zpr and comparisons over Zp . As illustrated in Figure 2, the proposed method enables both arithmetic and comparison operations within the BGV scheme. We start with an integer a ∈ Zpr , which may be either a raw input or the result of a prior arithmetic computation. To prepare a for comparison, we first apply the reduction step, which produces the digit decomposition {ai }r−1 i=0 with each ai ∈ Zp . Once represented in the digit space Zp , comparison functions such as equality and lessthan can be efficiently evaluated on a per-digit basis using polynomial interpolation, yielding intermediate results bi . These per-digit outputs are then aggregated into a final comparison result b. Since b resides in the digit space Zp , we apply modulus raising so that b is expressed in Zpr , ensuring the result is usable in subsequent arithmetic computations. Figure 2 is straightforward to implement in plaintext. We now describe how the workflow in Figure 2 is realized in ciphertext. We start from a single ciphertext in RQ with ℓ
packed plaintext slots, where each slot represents a plaintext value in Zpr . The reduction stage produces r new ciphertexts, where every slot in the i-th ciphertext represents the i-th base-p digit of the original slot value. Slot positions are preserved, so slot k in every reduced ciphertext corresponds to the same original slot k . Comparison is then evaluated digit by digit within the digit space Zp . For each digit position i, we evaluate the predicate on the i-th reduced ciphertext, producing an indicator ciphertext whose slots contain the per-slot result for digit i. These r indicator ciphertexts are then aggregated homomorphically into a single packed ciphertext whose slots contain the final comparison result (for example, 0 or 1) for each original slot. Finally, modulus raising re-embeds that packed comparison result from Zp into Zpr without changing the packing layout, so it can be used immediately by subsequent arithmetic. All steps act slotwise and preserve SIMD packing. This approach addresses the challenge of combining arithmetic and comparison operations within a single FVstyle scheme. It leverages the native plaintext space Zpr for efficient arithmetic while utilizing the digit space Zp for comparison evaluation. The reduction and modulus-raising steps that enable this integration are described in detail in the following sections.
5.2. Reduction from Zpr to Zp The reduction in FV-style schemes from Zpr to Zp amounts to extracting, for a value a ∈ Zpr , its r base-p digits {ai ∈ Zp }r−1 i=0 . This procedure is closely related to the digitextraction techniques used in BGV/BFV bootstrapping [12], [23], [24], [26], [30]. Conceptually, it is equivalent to recursively extracting the least-significant digit (LSD) from the input. In both settings, the central challenge is to extract digits homomorphically. Two widely used approaches are the Halevi-Shoup method [30] and the Chen-Han method [12]. Define ai,j for any integer whose least significant digit in base p is ai , with the next j least significant digits all equal to zero. Formally, this means ai,j = ai (mod pj+1 ). Halevi-Shoup [30] introduced a polynomial Fp based on the following lemma: Lemma 2 (Corollary 5.5 in [30]). For every prime p and e ≥ 1 there exists a degree-p polynomial Fp such that for every integer z0 , z1 with z0 ∈ [p] and every 1 ≤ t ≤ e, we have Fp (z0 + pt z1 ) = z0 (mod pt+1 ). We refer to [30] for details of the explicit construction of Fp . Moreover, the polynomial Fp also satisfies Fp (ai,j ) = ai,j+1 for every j ≤ r. In other words, this construction enables us to compute a valid ai,j+1 from any given ai,j by zeroing out one additional digit at each step. For example, assuming a ∈ Zp4 , we have Fp (ai,1 ) = Fp (xy0ai ) = x00ai . We will show how to use this polynomial to obtain digits. As a toy example, consider r = 4, so that a ∈ Zp4 can P3 be decomposed as a = i=0 ai pi with ai ∈ Zp . In Figure 3,
starting with a = a0,0 on the first row, we repeatedly compute a0,i+1 = Fp (a0,i ) until we obtain a0,3 = 000a0 . This completes the computation for the first row. In the second row, we compute a1,0 = (a−a0,1 )/p and then repeat the same procedure as in the first row.In the third row, we compute a2,0 = (a − a0,2 )/p − a1,1 /p and again apply the same procedure used in the previous rows. The same process is repeated for the fourth row. At the end, the last entry of each row corresponds to one digit of a; specifically, the last element in the i-th row gives ai−1 . a0,0
a0,1
a0,2
a1,0
a1,1
a1,2
a2,0
a2,1
a0,3
a3,0
Figure 3: Example of digit decomposition in Zp4 . The Chen-Han method [12] uses a similar approach to Halevi-Shoup, with the main difference being in how the last number of each row is computed. In Chen-Han, they introduced another polynomial Gp,e based on the following lemma: Lemma 3 (Section 3.2 in [12]). For every prime p and e ≥ 1, there exists a polynomial Gp,e of degree at most (e − 1)(p − 1) + 1 such that for every integer z0 , z1 with −p/2 < z0 ≤ p/2, we have Gp,e (z0 + pz1 ) = z0
(mod pe ).
We refer to [12] for details of the explicit construction of Gp,e . Using Lemma 3, we can apply the polynomial Gp,e directly to the input, in this case, the first number of a row, to obtain the last number in the same row. Compared to HaleviShoup, this method is more efficient because the degree of Gp,e is (p − 1)(e − 1) + 1, whereas in Halevi-Shoup it is pe−1 due to repeated evaluations of the polynomial Fp over e − 1 steps. Another digit-extraction approach is proposed by Geelen et al. [23]. They use the family {Gp,t }t≥1 to compute intermediate values within the same row directly from the input which is the first number in the row. For example, with the first row with first element a, they set a0,1 ← Gp,2 (a),
a0,2 ← Gp,3 (a),
a0,3 ← Gp,4 (a), . . .
so that all subsequent entries share the same input a rather than chaining through Fp . They also give two practical optimizations for evaluating Gp,e . First, they show a parity property: Gp,e is even when p = 2 and odd when p is odd, so it can be written using only even (resp. only odd) exponents. In particular, for odd p one can write Gp,e (x) = x · H(x2 ) for some polynomial H of degree (p − 1)(e − 1)/2, enabling reuse of a single x2 and an efficient baby-step/giant-step evaluation of H(x2 ).
Second, they apply a lattice-based coefficient selection to replace Gp,e by an equivalent representative with smaller integer coefficients, which reduces ciphertext-noise growth during homomorphic evaluation. In the context of bootstrapping, where only a few digits need to be removed (to realign noise and scale) rather than all digits, the Chen-Han or Geelen et al. methods are advantageous over the Halevi-Shoup method because they avoid computing every intermediate value between ai−1,0 and ai−1,r−i+1 for each row i and reduce the number of polynomial evaluations. In the context of digit decomposition, however, the situation is different: the first element of each row depends on values from previous rows that lie on the same diagonal, which means that all intermediate numbers must be computed. In contrast to the previous methods, we propose a digitdecomposition procedure that does not rely on intermediate values. Consider the first row in Figure 3 as an example. Let bi−1 denote the first element of row i. For the first row, b0 = a. To compute a0,3 , the Halevi-Shoup method requires three evaluations of Fp , or alternatively two evaluations of Fp and one evaluation of Gp,4 using the Chen-Han method; in Geelen et al., it needs one evaluation each of Gp,4 , Gp,3 , and Gp,2 . In contrast, our method computes a0,3 directly as a0,3 = Gp,4 (b0 ), avoiding intermediate values and requiring only a single evaluation of Gp,4 . Once a0,3 is obtained, the first element of the second row is b1 = (b0 − a0,3 )/p. The same process is then applied to the remaining rows, giving b2 = (b1 − a1,2 )/p and b3 = (b2 − a2,1 )/p. An illustration of this procedure is provided in Figure 4. As before, the last element in the i-th row gives ai−1 , where {ai }r−1 i=0 are the digits of a. Note that, except for the first row, the first numbers of the corresponding rows in Figure 3 and Figure 4 come from different constructions and therefore need not coincide numerically. However, in both constructions, the last element in each row yields the same digit output. b0 = a
a0,1
a0,2
b1
a1,1
a1,2
b2
a2,1
a0,3
b3
Figure 4: Example of proposed digit decomposition in Zp4 . As illustrated in Figure 3, when r = 4, the Halevi-Shoup method requires a total of six evaluations of the polynomial Fp . If the Chen-Han method is used, the cost becomes three evaluations of Fp together with one evaluation each of Gp,4 , Gp,3 , and Gp,2 . If the Geelen et al. method is used, the cost becomes three evaluations of Gp,2 , two evaluations of Gp,3 , and one evaluation of Gp,4 . In comparison, our method avoids all intermediate computations by directly applying a single Gp,e polynomial at each step. This results in a substantial reduction in the number of evaluations. For r = 4, this saves three evaluations of Fp in total.
In the general case, the Halevi-Shoup method requires O(r2 ) evaluations of Fp , the Chen-Han method requires O(r) evaluations of Fp plus O(r) evaluations of Gp,e , and the Geelen et al. method requires O(r2 ) evaluations of Gp,e , since all intermediate values are required for subsequent rows. By contrast, our approach reduces the cost to exactly r evaluations of Gp,e , one per row. Thus, our method achieves lower computational overhead and improved efficiency compared to Halevi-Shoup, Chen-Han, and Geelen et al., although it does not reduce the multiplicative depth relative to those methods. Switch to the digit space Zp . The digits obtained from the above decomposition process have different plaintext moduli, because the plaintext modulus is reduced only during the division-by-p operation in the vertical direction. We need to unify the plaintext space of these digits to Zp before evaluating comparison operations. For example, in Figure 3 and Figure 4, a0,3 represents the LSD of the input a and has modulus p4 . The next three digits, a1,2 , a2,1 , and b3 = a3,0 , have moduli p3 , p2 , and p, respectively. More formally, at the message level, the division-by-p operation is defined as DivideByP(kp) = k
(mod pt−1 ),
for some k ∈ Zpt−1 and t > 1. In the actual procedure, the input is a ciphertext encrypting a value congruent to kp (mod pt ), and the output is a ciphertext encrypting k (mod pt−1 ). Thus, both the message and the plaintext modulus are reduced by a factor of p [12], [30]. This homomorphic division-by-p is realized by multiplying the ciphertext by the constant p−1 (mod Q) [12], [30]. Now that the digits have different plaintext moduli, we need to reduce the plaintext modulus without reducing the message. Therefore, we define a function ChangeModToP as: ChangeModToP(k) = k (mod p), which takes as input an encryption of k (mod pt ) and returns k (mod p), for some k ∈ Zpt . In other words, it sets the plaintext modulus of the ciphertext from pt to p without changing the content of the ciphertext. The correctness of ChangeModToP follows from Lemma 4. Lemma 4. For every prime p and integers 1 ≤ m ≤ n, if a ≡ b (mod pn ), then a ≡ b (mod pm ). Proof. Since a ≡ b (mod pn ), we have that pn divides a−b. Because m ≤ n, it follows that pm divides pn , hence pm divides a − b and therefore a ≡ b (mod pm ). In other words, Lemma 4 ensures that if we have the correct base-p digits modulo pt for any t ≥ 1, then those digits are also correct modulo p. Operationally, this does not change the ciphertext itself; it only affects the decryption step in Algorithm 2, particularly line 2, where the final reduction is taken modulo the current plaintext modulus p rather than pr . This is consistent with the BGV relation c0 + c1 · s ≡ m + pr e = m + p · pr−1 e (mod Q).
Algorithm 3: Reduction from Zpr to Zp Input: a ∈ Zpr Pr−1 i Output: {ai }r−1 i=0 with ai ∈ Zp and a = i=0 ai p 1 b ← a; 2 for i ← 0 to r − 2 do 3 ai ← Gp, r−i (b); // Horizontal reduction 4 b ← DivideByP b − ai ; // Vertical reduction 5 end 6 ar−1 ← b; 7 for i ← 0 to r − 1 do 8 ai ← ChangeModToP(ai ); // Modulus reduction to Zp 9 end r−1 10 return {ai }i=0 ;
from Eq. (1). With Lemma 4 and ChangeModToP, we can reduce the plaintext modulus of all digits to p. For example, given an input a ∈ Zp4 , we know its LSD is a0 ∈ Zp . As shown in Figure 3 and Figure 4, by evaluating either the polynomial Fp or Gp,e , we can obtain a0,3 = a0 (mod p4 ). By Lemma 4, we know a0,3 = a0 (mod pm ) for any 1 ≤ m ≤ 4. Thus, a0,3 = a0 (mod p). Accordingly, we can obtain the digit a0 modulo p by directly reducing the modulus of a0,3 to p. This is achieved by calling ChangeModToP(a0,3 ). Similarly, we have a1 = ChangeModToP(a1,2 ) and a2 = ChangeModToP(a2,1 ). By integrating the digit decomposition with ChangeModToP, we obtain the reduction procedure from FV over Zpr to Zp , as shown in Algorithm 3. Complexity of the reduction function. As described in Algorithm 3, the reduction from Zpr to Zp consists of three steps: horizontal reduction, vertical reduction, and modulus reduction. The vertical reduction involves only subtraction and division by p, where in FV-style HE the division by p is implemented as a scalar multiplication. Since subtraction and scalar multiplication incur negligible cost [12], their overhead is marginal. The modulus reduction step operates only on the plaintext modulus of the message and does not require any ciphertext evaluation, and can therefore be considered essentially free. Consequently, the dominant cost of the reduction function lies in the horizontal reduction. The horizontal reduction requires evaluating the polynomial Gp,r−i (·). Lemma 3 guarantees that such a polynomial always exists with degree (p − 1)(e − 1) + 1. Moreover, Gp,e (x) can be expressed as x · H(x2 ) or H(x2 ), where the degree of H is half the degree p of Gp,e . This implies that (p − 1)(e − 1) + 1 multievaluating Gp,e requires O plications using the Paterson-Stockmeyer algorithm, and consumes O(log((p − 1)(e − 1) + 1)) multiplicative depth. In Algorithm 3, reducing the plaintext space of a ∈ Zpr to its digit representation {ai }r−1 i=0 ∈ Zp involves r rows in the horizontal direction. The last element in
each row, ai,r−i−1 , corresponds to the i-th digit of the input a. In each row, the polynomial Gp,r−i is evaluated once to compute ai,r−1 . Thus, the reduction requires exactly Pr−1 pone evaluation of each Gp,r−i , for a total of (p − 1)(r − i − 1) + 1 multiplications. i=0 The multiplicative depth of the reduction is determined by the longest computation path, which corresponds to traversing all digits as illustrated in Figure 4. Along this path, there are r − 1 evaluations of Gp,e , yielding a depth Pr−1 of i=0 log (p − 1)(r − i − 1) + 1 .
5.3. Efficient Comparison in Zp Given the reduction from Zpr to Zp (Section 5.2), we evaluate comparisons by applying standard per-digit tests in the digit space Zp and then aggregating the digit results. Unlike prior work that centers comparisons inside special plaintext encodings, we use interpolation polynomials only as per-digit predicates in Zp , while keeping arithmetic in Zpr and avoiding special encodings. Typical comparison functions include equality (EQ), inequality (NEQ), less-than (LT), less-than-or-equal (LE), greater-than (GT), and greater-than-or-equal (GE). In this work, however, we focus on constructing only EQ and LT homomorphically, since GT can be derived in the same manner as LT, while NEQ, GE, and LE can be obtained from simple transformations: NEQ = 1 − EQ, GE = 1 − LT, and LE = 1 − GT. Consistent with [33], [55], we rely on univariate interpolation, which is faster than bivariate in homomorphic settings. To make this possible, we restrict comparisons to zero, since arbitrary comparisons such as a < b can always be reduced to checking whether a−b < 0. Digit-wise comparison. The EQ function is defined as EQ(x, 0) = 1 for x = 0 and EQ(x, 0) = 0 otherwise. By Theorem 1, we can express it as FEQ (x, 0) = 1 − xp−1 . This follows directly from Fermat’s little theorem and makes EQ straightforward and efficient. In contrast, constructing a polynomial for LT is not as trivial as in the case of EQ. The LT function is defined as LT (x, 0) = 1 for x < 0 and LT (x, 0) = 0 otherwise. The polynomial for LT can be derived using a univariate interpolation polynomial over Zp [33], resulting in FLT (x, 0) =
p−2 X p + 1 p−1 x + ci xi , 2 i=1,odd
P(p−1)/2 p−1−i where ci = j . Similarly, the polynomial j=1 FGT (x) for the GT function can be derived. Unlike EQ, the LT construction requires higher-degree interpolation and more terms, making it computationally more expensive. Both FEQ and FLT have the same degree of p − 1. We note that both FEQ and FLT are defined over Zp . Digit-wise evaluation and aggregation. The polynomials FLT and FEQ defined in the previous paragraph are over Zp and therefore cannot be applied directly to inputs in
Algorithm 4: LT Comparison in Zpr Input: integers a mod pr and b mod pr Output: comparison result in Zp 1 d←a−b ; 2 digits ← Reduce(d, p, r) ; 3 for i ← 0 to r − 1 do 4 LTi ← FLT (digitsi , 0) ; // Digit-wise comparison 5 EQi ← FEQ (digitsi , 0); 6 end 7 LT ← LTr−1 ; 8 EQ ← EQr−1 ; 9 for i ← r − 2 to 0 do 10 LT ← LT + EQ · LTi ; // Aggregation 11 EQ ← EQ · EQi ; 12 end 13 return LT ;
Zpr . Suppose we want to compare a number z ∈ Zpr with 0. We first apply the reduction function to map z to its digit representation {zi }r−1 i=0 ∈ Zp . Since each digit now lies in Zp , we can evaluate FLT or FEQ on each digit individually. By aggregating the per-digit results, we obtain the comparison result for the original number z . The aggregation can be defined as r−1 Y
FEQ (zi , 0)
i=0
RaiseModToP2R(k) = Gp,r (k̄) (mod pr ),
which can be viewed as the inverse of ChangeModToP. Thus, RaiseModToP2R internally performs modulus extension followed by the evaluation of Gp,r , and directly outputs the canonical lifted value in Zpr : k ∈ Zpr .
This ensures that the resulting value is correctly represented in the FV domain over Zpr .
for the EQ case, or FLT (zi , 0)
Let b denote the result after the aggregation step (Section 5.3). Since b ∈ Zp , the output of the comparison computation still resides in the Zp domain. To enable further arithmetic operations, we propose a function that homomorphically maps b mod p in Zp back to b mod pr in FV over Zpr , which we call modulus raising. To perform this modulus raising, the first step is to enlarge the plaintext modulus of the underlying message. Given an encryption of k (mod p), this step produces k̄ (mod pr ), where only the modulus has been extended to pr . However, in general k̄ ̸= k (mod pr ). Simply enlarging the modulus ensures that the least significant digit (LSD) of k̄ matches k , while the higher-order digits remain undetermined. In other words, the reverse of Lemma 4 does not hold: although k̄ is congruent to k modulo p, the equality does not extend to modulo pr . To recover the correct value k (mod pr ), we must clear the higher digits of k̄ . This task is equivalent to extracting the LSD of k̄ , which can be accomplished through horizontal reduction in Algorithm 3, restricted to the first row. More directly, we define
k = Gp,r (k̄),
i=0
r−1 X
5.4. Modulus Raising from Zp to Zpr
r−1 Y
FEQ (zj , 0)
5.5. Overall Complexity
j=i+1
for the LT case. The result of the aggregation step lies in Zp . Comparing two numbers in Zpr . Suppose we have two integers a, b ∈ Zpr and want to test whether a < b. Section 4.1 showed that comparison directly over Zpr is infeasible for r > 1. To overcome this, we first apply the reduction process, allowing us to use polynomials defined over the digit space Zp . Specifically, we compute the difference d = a − b in Zpr , reduce d into its base-p digits in Zp , and then compare each digit to zero using FLT and FEQ . Finally, the per-digit results are aggregated to obtain the overall comparison between a and b. The full procedure is summarized in Algorithm 4 for the LT operation. The comparison computation in Zp is dominated by the evaluation of interpolation polynomials of degree p − 1. For √ r digits, this costs r p − 1 non-scalar multiplications and consumes log p multiplicative depth. The aggregation step uses only O(r) additions and multiplications, which can be performed efficiently.
Among all available operations in FHE, non-scalar (ciphertext-ciphertext) multiplication is the costliest primitive. Therefore, it is essential to reduce the number of nonscalar multiplications. The LT evaluation √ for direct comparison in Zp′ where √ p′ ≈ pr requires O( p′ ) ≈ O( pr ) = O(pr/2 ) nonscalar multiplications. Our space switching instead begins with digit extraction: extracting the i-th digit evaluates a polynomial of degree (p − 1)(r − 1) + 1, costp − i√ ing O (p − 1)(r − i − 1) + 1 ≈ O( pr) multiplica√ tions, so extracting all r digits costs about O(r pr). √ Per-digit√ comparison then costs O( p) each, for a total of O(r p). Aggregating the per-digit results uses O(r) non-scalar multiplications. Finally, step p the modulus-raising √ costs O (p − 1)(r − 1) + 1 ≈ O( pr). Summing these terms yields √ √ √ √ O (r pr + r p + r + pr) ≈ O(r pr) , so space switching reduces√the non-scalar multiplication count from O pr/2 to O r pr .
Let w = r log2 p be the bit-width. As w increases, direct comparison costs O(pr/2 ). This grows exponentially in r when p is fixed, and as pr/2 when r is fixed. In √ contrast, space switching costs O(r3/2 p) up to constants. For small fixed p (e.g., p ≤ 17), the direct comparison cost explodes with r, while our space switching cost grows √ roughly linearly in r with an additional√ p factor. For fixed r, increasing p raises our cost by p, whereas the direct method grows as pr/2 . This gap explains why space switching dominates at larger bit-widths.
6. Experiments In this section, we describe the experimental setup and evaluation methodology. Section 6.1 presents the platforms, hardware environment, and software dependencies. Section 6.2 outlines the workloads used in our evaluation, and Section 6.3 introduces the schemes against which we compare.
6.1. Implementation Details System Setup. We implement our work on HElib [29] and the NTL library [53]. We mainly leverage the BGV scheme [10] as the underlying HE scheme. We also adapted the implementation of [23] for efficient polynomial evaluation. All experiments are conducted on a server with Intel(R) Xeon(R) W-2235 equipped with 128GB RAM running at 3.80GHz. All parameters for BGV are set to ensure λ > 120, i.e., at least 120-bits security unless otherwise specified. The security level can be approximated by the LWE estimator [2]. All experiments are single-threaded, consistent with [23], [33]. The code can be accessed in this repository. Parameter Setup. We set the encryption parameters for all experiments according to the following strategies. Fixed parameters. We set the Hamming weight of the secret key as t = 120 for all experiments. The Hamming weight represents the number of non-zero coefficients in the secret key. We set the columns of the key-switching matrix to c = 2. We align these two parameters with previous works [33], [50], [55]. The plaintext modulus. The plaintext modulus in the FV space is determined by pr . We can choose p and r according to the input bit-width b such that pr has a size of at least b bits. The choice of p and r determines both the complexity of the plaintext switching and the complexity of comparison operations as it affects the polynomials Fp and Gp,r . The ciphertext modulus. The ciphertext modulus Q affects the multiplicative depth, that is the maximum number of non-scalar multiplications an HE instance can support before decryption fails due to noise [13], [30], [55]. Therefore, Q is chosen to match the depth of the evaluation circuit. The degree of polynomial ring. Once we have chosen p, r and Q, we can choose an appropriate degree of polynomial to meet the security level λ > 120. By setting the cyclotomic order of the polynomial ring m, at the same time we also set the degree of polynomial ring n, the order of the base prime d = Ord(m, p), and the number of SIMD slots ℓ = n/d.
6.2. Workloads Evaluated We evaluate the performance of our proposed method across four aspects. First, we analyze the runtime of comparison operations, focusing on the LT function over inputs of different bit-widths. Second, we assess its effectiveness on database workloads using the TPC-H benchmark suite [56], specifically Query 6. This query involves four columns, each encrypted into a single ciphertext, resulting in four ciphertexts in total. All columns are represented as 16-bit integers. The query includes two core operations: filtering, which applies comparison conditions to select rows, and aggregation, which computes summary values such as SUM or COUNT over the filtered results. To ensure compatibility with our encrypted framework, we preprocess the dataset so that all values are represented as integers, and we select parameters so that every ciphertext can pack all rows (i.e., the number of slots exceeds the dataset size). Third, we provide a runtime breakdown to identify the relative cost of each sub-operation in our method. Finally, we perform a sensitivity study by examining LT performance across varying bit-widths.
6.3. Schemes Evaluated We compare three approaches that support both arithmetic and comparison operations on encrypted data, all producing exact results without approximation errors: space switching (our work), scheme switching, and the work from [50] which we refer to as direct comparison. We exclude schemes that do not give exact results, such as polynomial approximation, because the workloads that we test require precise comparison results. Space switching is designed to support both arithmetic operations over Zpr and comparison operations natively within the same scheme, avoiding the need to alternate between arithmetic- and bit-oriented schemes. By contrast, scheme switching [6], [8], [48] combines a word-wise HE scheme with a bit-wise scheme, incurring overhead from ciphertext conversions. Direct comparison [50] evaluates both arithmetic and comparisons in a single arithmetic HE scheme over Zp . This avoids conversions but requires p to grow exponentially with bit-width; as p increases, the interpolation degree (p−1) inflates multiplicative depth, noise, and evaluation cost.
7. Evaluation Results 7.1. Performance on the LT Operator We compare our space switching against direct comparison [50] and HE3 DB [6], which we adopt as the representative scheme-switching method. Figure 5 presents the runtime of space switching in comparison with scheme switching and direct comparison for the LT operator across 8- to 20-bit inputs. The parameters for space switching and direct comparison are shown in Table 4, while parameters
Bitwidth
log Q
Space Switching (pr , m, ℓ)
Direct Comparison (p, m, ℓ)
8 12 16 20
376 672 840 1280
(73 , 17195, 1080) (75 , 30025, 3000) (413 , 59595, 3808) (374 , 46981, 8540)
(257, 30256, 960) (4099, 34833, 2728) (65537, 50643, 3960) (1048583, 39872, 9968)
Scheme switching
Amortized Runtime (ms)
104
Direct comparison
Space switching
103 102 101 100
8
12
Bits
16
20
Figure 5: Amortized runtime comparison for the LT operator across Scheme Switching, Direct Comparison, and Space Switching. for scheme switching follow [6]. Runtimes are reported as amortized per-slot runtime. For the LT operator (Figure 5), space switching requires 4.34 ms and 7.66 ms for 8- and 12-bit inputs, respectively. These values represent up to a 3× speedup over direct comparison and a 21× speedup over scheme switching. In this lower bit-width range, direct comparison runs faster than scheme switching, but both remain significantly slower than space switching. As the bit-width increases to 16 and 20, the trend reverses: direct comparison incurs very high cost, exceeding even scheme switching, while space switching maintains runtimes of 19.05 ms and 17.36 ms, corresponding to 18×-136× improvements over direct comparison and 13×-20× over scheme switching. This indicates that the relative efficiency of direct comparison is limited to small bit-widths, whereas space switching remains the most scalable approach, consistent with the complexity analysis in Section 5.5.
7.2. Database Workload Evaluation Results For the database workload, we compare space switching with two alternative methods, direct comparison and scheme switching, in the database workload with varying numbers of rows. The results are shown in Figure 6. Direct comparison suffers very high runtime because the interpolation degree grows exponentially with input size: 212 rows take 2 hours 24 minutes and 214 exceed 3.5 hours. Although it avoids reduction and digit extraction, the bottleneck is evaluating the comparison polynomial of degree p−1; for a 16-bit prime p this becomes prohibitively expensive. Scheme switching performs somewhat better than direct comparison at smaller scales, with runtimes of 1 hour 35
Running Time (s)
TABLE 4: Parameters for space switching and direct comparison.
Scheme switching
105
Direct comparison
Space switching
104 103 102
212
213
Rows
214
Figure 6: Runtime comparison for the TPC-H Benchmark [56] Query 6 across scheme switching, direct comparison, and space switching. minutes and 3 hours 19 minutes for 212 and 213 rows, respectively. However, at 214 rows, scheme switching becomes significantly worse, taking more than 6 hours, nearly twice as slow as direct comparison. This inefficiency arises from the way comparison operations are handled. Initially, the database consists of N ciphertexts in LWE form, and to evaluate a comparison predicate each ciphertext must be processed individually. Every LWE ciphertext is first converted into a TFHE ciphertext, where the comparison function is executed. After all rows have been processed, the comparison results are repacked into a single RLWE ciphertext to support aggregation queries. This pipeline introduces several layers of overhead: (i) repeated conversions from LWE to TFHE for every ciphertext; (ii) row-by-row evaluation in TFHE, where aggregating multiple comparison outputs through homomorphic AND operations requires repeated bootstrapping-heavy computations; and (iii) repacking from many LWE ciphertexts back into a single RLWE ciphertext, which adds costly external products and key switches. These costs compound with dataset size, explaining why scheme switching scales poorly and even becomes slower than direct comparison at 214 rows. Space switching, by contrast, achieves substantially lower runtime across all tested scales. For 212 rows, space switching completes in only 9 minutes 24 seconds, yielding a 15× speedup over direct comparison and a 10× speedup over scheme switching. At 213 rows, space switching runs in 20 minutes, corresponding to 9× and 10× improvements, respectively. For the largest dataset of 214 rows, space switching completes in 21.5 minutes, giving a 10× speedup compared to direct comparison and a 17× improvement over scheme switching. Overall, space switching consistently reduces runtime by more than an order of magnitude relative to direct comparison and up to 17× relative to scheme switching. More importantly, while both baselines show steep runtime growth as the dataset scales, with direct comparison hindered by the cost of evaluating high-degree polynomials and scheme switching burdened by scheme-switching and packing overheads, space switching maintains near-linear growth and remains within practical runtime ranges even for the largest tested dataset. This scalability advantage underscores the suitability of space switching for encrypted query processing at larger scales.
TABLE 5: The runtime breakdown of the LT evaluation. Time is in seconds. Bit-width
(p, r)
Reduction
Comparison
Aggregation
Modulus Raising
Total
8 12 16 20
(7, 3) (7, 5) (41, 3) (37, 4)
1.89 12.06 30.32 71.65
1.65 6.45 29.04 54.6
0.44 2.21 2.51 5.77
0.71 2.27 10.69 16.26
4.69 22.99 72.56 148.28
TABLE 6: Runtime of the proposed method for LT evaluation across different bit-widths. Bit-width 8
12
16
20
(p, r)
log Q
(m, n)
ℓ
Total Running Time (s)
Amortized Time (ms)
(5, 4) (7, 3) (17, 2) (7, 5) (11, 4) (17, 3) (67, 2) (17, 4) (41, 3) (257, 2) (17, 5) (37, 4) (131, 3)
456 376 432 672 784 672 780 872 840 896 1200 1280 1280
(12851, 12600) (17195, 12960) (21513, 14000) (30025, 24000) (44289, 23328) (55328, 20736) (32259, 21504) (56889, 31752) (59595, 30464) (40025, 32000) (83811, 44064) (46981, 42700) (62447, 48600)
840 1080 1400 3000 3888 1152 2688 756 3808 2000 7344 8540 8100
4.68 4.69 6.30 22.99 40.37 38.43 33.26 68.98 72.56 79.82 185.42 148.28 223.35
5.57 4.34 4.50 7.66 10.38 33.36 12.37 91.24 19.05 39.91 25.25 17.36 27.57
In addition to its runtime advantages, space switching also offers a more favorable memory footprint than scheme switching. Across datasets of size 212 , 213 , and 214 rows, space switching consumes 6.6 GB, 12.6 GB, and 44 GB of memory, respectively, whereas scheme switching requires 57.5 GB, 62.2 GB, and 62.3 GB. Direct interpolation uses 5.8 GB, 13.6 GB, and 31 GB. A similar trend appears in evaluation key size. Space switching requires 1.3 GB, 2.5 GB, and 8.5 GB of evaluation keys, while scheme switching consistently requires 26.7 GB across all cases. Direct interpolation requires 0.6 GB, 1.9 GB, and 5.3 GB. These results show that space switching achieves substantial runtime improvements without incurring the very large memory and key-size overheads of scheme switching, while remaining within a similar overall resource range as direct interpolation. Larger bit-width. We also evaluated space switching on 32bit inputs, where it achieves up to 9× speedup over scheme switching for 214 rows. In contrast, direct comparison becomes impractical at 32-bit because it requires a large 32-bit prime p, and constructing the comparison polynomial incurs O(p2 ) cost, which is infeasible in practice. Furthermore, space switching completes in 1 hour 18 minutes for 56-bit inputs with 212 rows, whereas HE3 DB, as a representative scheme-switching method, does not support bit-widths beyond 32-bit.
7.3. Runtime Breakdown for Computation Stages We provide a detailed runtime analysis in Table 5. Space switching links arithmetic in the number space Zpr with comparisons in the digit space Zp via four stages:
(1) reduction from Zpr to Zp , (2) comparison in Zp via interpolation, (3) aggregation of digit-wise results, and (4) modulus raising from Zp to Zpr . As shown in Table 5, the relative contributions of these stages shift as the bit-width increases. For 8-bit inputs, the total runtime is 4.69s, with each stage contributing relatively evenly: reduction 1.89s (40%), interpolation 1.65s (35%), aggregation 0.44s (9%), and modulus raising 0.71s (15%). At 12 bits, the runtime grows to 22.99s, dominated by reduction at 12.06s (52%) and interpolation at 6.45s (28%), while aggregation and modulus raising remain modest at 2.21s (10%) and 2.27s (10%). With 16-bit inputs, the imbalance becomes stronger: reduction increases to 30.32s (42% of the 72.56s total) and interpolation to 29.04s (40%), while aggregation and modulus raising contribute only 2.51s (4%) and 10.69s (15%). At 20 bits, the runtime reaches 148.28s, where reduction alone takes 71.65s (48%), interpolation 54.60s (37%), aggregation 5.77s (4%), and modulus raising 16.26s (11%). Two main insights emerge from this breakdown. First, aggregation is consistently lightweight across all bit-widths, remaining under 10% of the total computation. This reflects its dependence primarily on r and a small number of multiplications, so its contribution stays limited even as the overall workload grows. Second, the dominant costs are the reduction and interpolation steps in the Zp domain. Both grow significantly as the bit-width increases and together account for 75–85% of the runtime, depending on the values of p and r. Choosing a larger p allows for a smaller r, meaning fewer digits to extract, but this also increases the cost of evaluating the comparison polynomial. In contrast, modulus raising shows moderate but steady growth, while
aggregation remains negligible. Overall, the primary bottleneck of the proposed method lies in the reduction and interpolation steps, especially as the input size increases.
7.4. Performance with Varying Bit-Width Table 6 reports the runtime of space switching for comparison operations across different bit-widths. Each row lists the chosen parameter set (p, r), the ciphertext modulus size log Q, the polynomial ring parameters (m, n), the total runtime, and the amortized per-comparison runtime. Space switching achieves amortized latencies as low as 4.34 ms for 8-bit comparisons. For larger bit-widths, the amortized runtime remains within a few to tens of milliseconds, ranging from 7.66 ms for 12-bit inputs, 19.05 ms for 16-bit inputs, and 17.36 ms for 20-bit inputs. The amortized cost is strongly influenced by the order d = Ord(p) modulo m. With n fixed, a smaller d yields a larger SIMD packing factor ℓ, which allows more comparisons to be processed in parallel, thereby reducing per-operation runtime. We also observe that as the bit-width of the input increases, both the total runtime and the amortized runtime generally increase. This is because larger inputs typically require a larger prime p and exponent r. A larger p leads to higher-degree polynomial Gp,r (·), as well as the interpolation of comparison polynomials over Zp . Meanwhile, r determines the number of digits that must be processed: the larger r is, the more the polynomial Gp,r (·) need to be evaluated, and the more computation is required in comparison operation over Zp . While the overall runtime increases with the input bitwidth, we can achieve better amortized runtime by choosing appropriate encryption parameters. For example, the amortized runtime on 20-bit input can be as little as 17.36 ms, comparable to or even faster than the 12-bit input. This implies that the choice of the p and r is non-trivial. When the input bit-width is fixed, we can choose different sets of (p, r). The larger the prime p is, the smaller power r is needed. Smaller r means we need to evaluate the polynomial Gp,r (·) less frequently. On the other hand, the larger the prime p is, the higher degree the interpolation polynomial and the polynomial Gp,r have. This, in turn, increases the evaluation time. By choosing the proper p and r, we can achieve a better runtime.
7.5. Discussion CKKS-based approximate comparison. We additionally measured the runtime of CKKS-based approximate comparison. In this setting, the CKKS inputs can be discretized and scaled to fit the approximation interval. We use the CKKS implementation in OpenFHE [1], with the LT operator implemented based on Cheon et al. [16]. In CKKS, the number of SIMD slots is always half of the ring dimension (n/2), which significantly reduces the amortized runtime per value. The amortized runtime for evaluating an LT operator is 0.58 ms for 8-bit inputs, 0.93 ms for 12-bit inputs, 1.39 ms for 16-bit inputs, and 1.99 ms for 20-bit inputs. CKKS is generally faster in this setting because it performs
only a single polynomial evaluation for the comparison itself, and its output can be directly used in subsequent arithmetic operations without additional processing, whereas space switching requires additional steps, including reduction before digit comparison, followed by aggregation and modulus raising to return to the arithmetic domain. However, CKKS comparison remains approximate: its outputs are not exactly 0 or 1, but values close to them. Although discretization and scaling improve the practical behavior of CKKS-based comparison, they do not eliminate the main issue at the critical point of equality in a strict LT test, since the comparison function remains discontinuous there. In particular, when two inputs are equal, the approximation produces 0.5, whereas for a strict LT operation the expected result should be 0. This approximation error may propagate to subsequent arithmetic or aggregation operations, such as SUM in Figure 1, and thus does not provide exact semantics after comparison. Moreover, achieving higher precision in CKKS requires higher-degree polynomials, which increases both runtime and multiplicative depth. Functional bootstrapping approaches. Functionalbootstrapping-based methods implement comparison through LUT evaluation during refresh and are most effective for relatively small input domains. Their cost scales with the LUT domain size, making them less suitable as bit-width grows. For example, Lee et al. [38] report 47.3 s for 9-bit inputs and 172.1 s for 12-bit inputs, and Liu et al. [40] report 6.7 ms for 9-bit inputs and 39.1 ms for 12-bit inputs. These results suggest that functional bootstrapping can be competitive for relatively small input domains, but its cost grows more rapidly as bit-width increases. In contrast, our method increases from 4.34 ms at 8-bit to 7.66 ms at 12-bit. These results illustrate that our digit-level decomposition scales more favorably with bit-width than LUT-based functional bootstrapping. Therefore, while functional bootstrapping is a general approach, our work addresses a different and more scalable operating regime for exact comparison in leveled FV/BGV.
8. Conclusion In this work, we presented space switching, a method to seamlessly integrate arithmetic and comparison operations within FV-style schemes such as BFV and BGV. While prior research shows that FV-style encryption can efficiently support arithmetic and accurately evaluate comparisons, performing these operations in succession has remained a challenge. Our approach resolves this by separating computations into their natural plaintext spaces, arithmetic in Zpr and comparisons in Zp , and introducing reduction and modulus-raising procedures to transition between them. We conducted extensive experiments across varying bit-widths, showing that space switching surpasses scheme switching by more than 20× for LT operator and by more than 100× compared to direct comparison. For database workloads, space switching achieves up to 17× speedup over scheme switching and up to 15× improvement over direct comparison.
We believe this work enhances the universality of FV-style schemes for general-purpose computation, making them more practical for applications such as privacy-preserving machine learning and genomic analysis. Extending space switching to support even more complex functions remains an important direction for future research.
9. Acknowledgments We thank the anonymous reviewers for their valuable feedback and the shepherd for the invaluable guidance provided throughout the revision process. This material is based upon work supported by the National Science Foundation under Grant Nos. CCF-2523407 and CNS-2413232. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
References [1]
Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. Openfhe: Open-source fully homomorphic encryption library. In Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC’22, page 53–63, New York, NY, USA, 2022. Association for Computing Machinery.
[2]
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. J. Math. Cryptol., 9(3):169–203, 2015.
[3]
Andreea Alexandru, Andrey Kim, and Yuriy Polyakov. General functional bootstrapping using ckks. In Advances in Cryptology – CRYPTO 2025: 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2025, Proceedings, Part III, page 304–337, Berlin, Heidelberg, 2025. Springer-Verlag.
[4]
Frederik Armknecht, Colin Boyd, Christopher Carr, Kristian Gjøsteen, Angela Jäschke, Christian A. Reuter, and Martin Strand. A guide to fully homomorphic encryption. IACR Cryptol. ePrint Arch., page 1192, 2015.
[5]
Ahmad Al Badawi, Jack Bates, Flávio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, R. V. Saraswathy, Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. Openfhe: Open-source fully homomorphic encryption library. In WAHC@CCS, pages 53–63. ACM, 2022.
[6]
[7]
[8]
Song Bian, Zhou Zhang, Haowen Pan, Ran Mao, Zian Zhao, Yier Jin, and Zhenyu Guan. 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, CCS ’23, page 2930–2944, New York, NY, USA, 2023. Association for Computing Machinery. Dan Boneh, Craig Gentry, Shai Halevi, Frank Wang, and David J. Wu. Private database queries using somewhat homomorphic encryption. In Michael Jacobson, Michael Locasto, Payman Mohassel, and Reihaneh Safavi-Naini, editors, Applied Cryptography and Network Security, pages 102–118, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Christina Boura, Nicolas Gama, Mariya Georgieva, and Dimitar Jetchev. CHIMERA: combining ring-lwe-based fully homomorphic encryption schemes. J. Math. Cryptol., 14(1):316–338, 2020.
[9]
Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical gapsvp. In CRYPTO, volume 7417, pages 868–886. Springer, 2012.
[10] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory, 6(3):13:1–13:36, 2014. [11] Olive Chakraborty and Martin Zuber. Efficient and accurate homomorphic comparisons. In WAHC@CCS, pages 35–46. ACM, 2022. [12] Hao Chen and Kyoohyung Han. Homomorphic lower digits removal and improved FHE bootstrapping. In EUROCRYPT (1), volume 10820, pages 315–337. Springer, 2018. [13] Hao Chen, Kyoohyung Han, Zhicong Huang, Amir Jalali, and Kim Laine. Simple encrypted arithmetic library v2. 3.0. Microsoft Research, December, 13, 2017. [14] Jung Hee Cheon, Hyeongmin Choe, and Jai Hyun Park. Treebased lookup table on batched encrypted queries using homomorphic encryption. IACR Cryptol. ePrint Arch., page 87, 2024. [15] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic encryption for arithmetic of approximate numbers. In ASIACRYPT (1), volume 10624, pages 409–437. Springer, 2017. [16] Jung Hee Cheon, Dongwoo Kim, and Duhyeong Kim. Efficient homomorphic comparison methods with optimal complexity. In ASIACRYPT (2), volume 12492, pages 221–256. Springer, 2020. [17] Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun-Hee Lee, and Keewoo Lee. Numerical method for comparison on homomorphically encrypted numbers. In ASIACRYPT (2), volume 11922, pages 415– 445. Springer, 2019. [18] Jung Hee Cheon, Wootae Kim, and Jai Hyun Park. Efficient homomorphic evaluation on large intervals. IEEE Trans. Inf. Forensics Secur., 17:2553–2568, 2022. [19] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: fast fully homomorphic encryption over the torus. J. Cryptol., 33(1):34–91, 2020. [20] Léo Ducas and Daniele Micciancio. FHEW: bootstrapping homomorphic encryption in less than a second. In EUROCRYPT (1), volume 9056, pages 617–640. Springer, 2015. [21] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. IACR Cryptol. ePrint Arch., page 144, 2012. [22] Bo Feng, Qian Lou, Lei Jiang, and Geoffrey C Fox. Cryptogru: Low latency privacy-preserving text analysis with gru. arXiv preprint arXiv:2010.11796, 2020. [23] Robin Geelen, Ilia Iliashenko, Jiayi Kang, and Frederik Vercauteren. On polynomial functions modulo pe and faster bootstrapping for homomorphic encryption. In EUROCRYPT (3), volume 14006, pages 257–286. Springer, 2023. [24] Robin Geelen and Frederik Vercauteren. Bootstrapping for bgv and bfv revisited. Journal of Cryptology, 36(2):12, 2023. [25] Craig Gentry. Fully homomorphic encryption using ideal lattices. In STOC, pages 169–178. ACM, 2009. [26] Craig Gentry, Shai Halevi, and Nigel P. Smart. Better bootstrapping in fully homomorphic encryption. In Public Key Cryptography, volume 7293, pages 1–16. Springer, 2012. [27] Craig Gentry, Shai Halevi, and Nigel P. Smart. Fully homomorphic encryption with polylog overhead. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012, volume 7237, pages 465–482, Germany, 2012. Springer Berlin Heidelberg. [28] Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International conference on machine learning, pages 201–210. PMLR, 2016.
[29] Shai Halevi and Victor Shoup. Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Paper 2020/1481, 2020.
[48] Wen-jie Lu, Zhicong Huang, Cheng Hong, Yiping Ma, and Hunter Qu. PEGASUS: bridging polynomial and non-polynomial evaluations in homomorphic encryption. In SP, pages 1057–1073. IEEE, 2021.
[30] Shai Halevi and Victor Shoup. Bootstrapping for helib. J. Cryptol., 34(1):7, 2021.
[49] Wenjie Lu, Jun-Jie Zhou, and Jun Sakuma. Non-interactive and output expressive private comparison from homomorphic encryption. In AsiaCCS, pages 67–74. ACM, 2018.
[31] Kyoohyung Han, Seungwan Hong, Jung Hee Cheon, and Daejun Park. Logistic regression on homomorphic encrypted data at scale. In AAAI, pages 9466–9471. AAAI Press, 2019. [32] Ilia Iliashenko, Christophe Nègre, and Vincent Zucca. Integer functions suitable for homomorphic encryption over finite fields. In WAHC@CCS, pages 1–10. WAHC@ACM, 2021. [33] Ilia Iliashenko and Vincent Zucca. Faster homomorphic comparison operations for BGV and BFV. Proc. Priv. Enhancing Technol., 2021(3):246–264, 2021. [34] Lei Jiang, Qian Lou, and Nrushad Joshi. Matcha: A fast and energyefficient accelerator for fully homomorphic encryption over the torus. In The Design Automation Conference (DAC 2022), 2022.
[50] Koki Morimura, Daisuke Maeda, and Takashi Nishide. Accelerating polynomial evaluation for integer-wise homomorphic comparison and division. J. Inf. Process., 31:288–298, 2023. [51] Mike Paterson and Larry J. Stockmeyer. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput., 2(1):60–66, 1973. [52] Jean Louis Raisaro, Gwangbae Choi, Sylvain Pradervand, Raphael Colsenet, Nathalie Jacquemont, Nicolas Rosat, Vincent Mooser, and Jean-Pierre Hubaux. Protecting privacy and security of genomic data in i2b2 with homomorphic encryption and differential privacy. IEEE ACM Trans. Comput. Biol. Bioinform., 15(5):1413–1426, 2018. [53] Victor Shoup et al. Ntl: A library for doing number theory. 2001.
[35] Miran Kim and Kristin E. Lauter. Private genome analysis through homomorphic encryption. BMC Medical Informatics Decis. Mak., 15-S(5):S3, 2015.
[54] Nigel P. Smart and Frederik Vercauteren. Fully homomorphic SIMD operations. Des. Codes Cryptogr., 71(1):57–81, 2014.
[36] Myungsun Kim, Hyung Tae Lee, San Ling, Shu Qin Ren, Benjamin Hong Meng Tan, and Huaxiong Wang. Better security for queries on encrypted databases. Cryptology ePrint Archive, Paper 2016/470, 2016.
[55] Benjamin Hong Meng Tan, Hyung Tae Lee, Huaxiong Wang, Shu Qin Ren, and Khin Mi Mi Aung. Efficient private comparison queries over encrypted databases using fully homomorphic encryption with finite fields. IEEE Trans. Dependable Secur. Comput., 18(6):2861–2874, 2021.
[37] Myungsun Kim, Hyung Tae Lee, San Ling, and Huaxiong Wang. On the efficiency of fhe-based private queries. IEEE Trans. Dependable Secur. Comput., 15(2):357–363, 2018.
[56] Transaction Processing Performance Council. Tpc benchmarktm h standard specification. Technical report, Transaction Processing Performance Council, San Francisco, CA, 2022.
[38] Dongwon Lee, Seonhong Min, and Yongsoo Song. Functional bootstrapping for packed ciphertexts via homomorphic lut evaluation. Cryptology ePrint Archive, 2024. [39] Eunsang Lee, Joon-Woo Lee, Jong-Seon No, and Young-Sik Kim. Minimax approximation of sign function by composite polynomial for homomorphic comparison. IEEE Trans. Dependable Secur. Comput., 19(6):3711–3727, 2022. [40] Zeyu Liu and Yunhao Wang. Amortized functional bootstrapping in less than 7 ms, with Õ(1) polynomial multiplications. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, pages 101–132, Singapore, 2023. Springer Nature Singapore. [41] Qian Lou, Bo Feng, Geoffrey Charles Fox, and Lei Jiang. Glyph: Fast and accurately training deep neural networks on encrypted data. Advances in neural information processing systems, 33:9193–9202, 2020. [42] Qian Lou, Bo Feng, Geoffrey C Fox, and Lei Jiang. Glyph: Fast and accurately training deep neural networks on encrypted data. NeurIPS 2020 (Advances in Neural Information Processing Systems), 2019. [43] Qian Lou and Lei Jiang. She: A fast and accurate deep neural network for encrypted data. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. [44] Qian Lou and Lei Jiang. She: A fast and accurate deep neural network for encrypted data. In Advances in Neural Information Processing Systems (NeurIPS) 2019, pages 10035–10043, 2019. [45] Qian Lou and Lei Jiang. Hemet: A homomorphic-encryption-friendly privacy-preserving mobile neural network architecture. ICML 2021, 2021. [46] Qian Lou, Wen-jie Lu, Cheng Hong, and Lei Jiang. Falcon: Fast spectral inference on encrypted data. NeurIPS 2020 (Advances in Neural Information Processing Systems), 33, 2020. [47] Qian Lou, Yilin Shen, Hongxia Jin, and Lei Jiang. Safenet: A secure, accurate and fast neural network inference. In International Conference on Learning Representations, 2021.
[57] Jiaqi Xue, Xin Xin, Wei Zhang, Mengxin Zheng, Qianqian Song, Minxuan Zhou, Yushun Dong, Dongjie Wang, Xun Chen, Jiafeng Xie, et al. Sok: Can fully homomorphic encryption support general ai computation? a functional and cost analysis. PoPETs 2026, 2026. [58] Ardhi Wiratama Baskara Yudha, Jiaqi Xue, Qian Lou, Huiyang Zhou, and Yan Solihin. Boostcom: Towards efficient universal fully homomorphic encryption by boosting the word-wise comparisons. In (PACT’24) The International Conference on Parallel Architectures and Compilation Techniques (PACT), 2024. [59] Yancheng Zhang, Xun Chen, and Qian Lou. Hebridge: Connecting arithmetic and logic operations in fv-style he schemes. In Proceedings of the 12th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 23–35, 2023. [60] Yancheng Zhang, Jiaqi Xue, Mengxin Zheng, Mimi Xie, Mingzhe Zhang, Lei Jiang, and Qian Lou. Cipherprune: Efficient and scalable private transformer inference. arXiv preprint arXiv:2502.16782, 2025. [61] Yancheng Zhang, Mengxin Zheng, Yuzhang Shang, Xun Chen, and Qian Lou. Heprune: Fast private training of deep neural networks with encrypted data pruning. Advances in Neural Information Processing Systems, 37:51063–51084, 2024. [62] Yuchen Zhang, Wenrui Dai, Xiaoqian Jiang, Hongkai Xiong, and Shuang Wang. FORESEE: fully outsourced secure genome study based on homomorphic encryption. BMC Medical Informatics Decis. Mak., 15-S(5):S5, 2015.
Appendix A. Meta-Review The following meta-review was prepared by the program committee for the 2026 IEEE Symposium on Security and Privacy (S&P) as part of the review process as detailed in the call for papers.
A.1. Summary This paper proposes “space switching”, a technique to efficiently support both arithmetic operations and comparisons within a single BFV/BGV homomorphic encryption scheme. The key idea is to convert between a number space (Zpr ) suited for arithmetic and a digit space (Zrp ) suited for polynomial-interpolation-based comparison, using digit extraction techniques adapted from the bootstrapping literature and a modulus raising procedure. The approach is evaluated on primitive operators and database workloads, demonstrating significant speedups over scheme-switchingbased methods.
A.2. Scientific Contributions • •
Addresses a Long-Known Issue. Provides a Valuable Step Forward in an Established Field.
A.3. Reasons for Acceptance 1)
2)
Efficiently combining arithmetic and comparison operations within a single FHE scheme is a wellknown problem. Prior approaches either require expensive scheme switching between different FHE schemes or rely on polynomial approximations that sacrifice exactness. This paper presents a principled approach that avoids both limitations, achieving up to 15× speedups over scheme-switching-based methods for comparison operations. The paper repurposes digit decomposition techniques, previously used only in BFV/BGV bootstrapping, as a general-purpose tool for bridging arithmetic and comparison within a single scheme. While the underlying digit extraction algorithms build on prior bootstrapping literature, the conceptual insight that these techniques can be applied cost-effectively outside of bootstrapping is valuable and may encourage the community to reconsider the practical utility of digit decomposition more broadly.