IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
1
Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator
arXiv:2605.17222v1 [cs.CR] 17 May 2026
Sajjad Akherati, and Xinmiao Zhang The Ohio State University, Columbus, OH 43210, U.S. Emails: {akherati.1, zhang.8952}@osu.edu
Abstract—Computations can be directly carried out over ciphertexts using homomorphic encryption (HE), which is indispensable for privacy-preserving cloud computing. Linear transformation is widely used in neural networks, including large language models. However, the implementation of linear transformation over HE requires a large number of ciphertext rotations, which incur significant memory and hardware overhead despite existing simplification techniques. This paper proposes a triple-hoisted baby-step giant-step algorithm that decomposes the baby step further to substantially reduce the number of ciphertext rotations needed for the CKKS HE evaluation of linear transformation. Moreover, to reduce off-chip memory access, which contributes to the majority of the latency, a memoryoptimized data path is proposed by partitioning the algorithm into multiple phases. Furthermore, an efficient FPGA-based hardware accelerator with an optimized permutation circuit for message routing is designed for the proposed scheme. For a set of typical parameters, the proposed design reduces the off-chip memory access by 2.9× compared to the best prior design. Synthesized for Xilinx Virtex UltraScale+ devices, the proposed design achieves a 5.8× reduction in computational latency compared with the baseline design. Index Terms—Baby-step giant-step decomposition, CKKS, Hardware accelerator, Homomorphic encryption, Linear transformation.
I. I NTRODUCTION Homomorphic encryption (HE) enables computations to be performed directly on encrypted data without requiring decryption. It is essential for realizing machine learning for applications demanding user data privacy [1], such as medical diagnosis [2], financial data analysis [3], and genome sequencing. The Ring Learning With Errors (RLWE) problem is widely adopted in HE schemes, including CKKS [4], BGV [5], BFV [6], and TFHE [7]. In particular, the CKKS scheme [4] is the most efficient among available HE schemes. In these schemes, a ciphertext consists of two polynomials, ct = (c0 , c1 ) ∈ R2Q , where RQ = ZQ [x]/(xN + 1). The polynomials in RQ have degree at most N − 1 and their coefficients are integers modulo Q. N is typically a power of two in the order of thousands and Q has several hundred bits to achieve the desired security level. The multiplication of long polynomials with large coefficients can be simplified by various approaches. The complexity can be reduced by decomposing the operands and incorporating the modular reduction by xN + 1 into the decomposed components [8]. The number theoretic transform (NTT) [9] lowers the complexity by mapping polynomial multiplications to coefficient-wise multiplications in the transformed domain.
The hardware acceleration for NTT has been intensively investigated [9], [10], [11], [12]. Integer modular multiplication for the coefficients can be optimized using techniques such as Montgomery multiplication, Barrett reduction [13], [14], and Karatsuba decomposition. Additionally, the residue number system (RNS) reduces the complexity of integer arithmetic by representing an integer a mod Q through its residues with respect to the pairwise co-prime factors of Q [15]. Linear transformations (LTs) are widely employed in HE applications such as neural networks [16], transformers [17], and bootstrapping [18]. To efficiently utilize the long polynomials in the ciphertexts, multiple input data are packed into the same ciphertext. As a result, ciphertext rotations are needed to shift the entries in the ciphertext polynomials and derive the matrix multiplication result. Ciphertext rotations have very high complexity and need large rotation keys. The HE linear transformation (HE-LT) is carried out through diagonalizing the constant matrix of the LT and packing the entries in the same diagonal into a separate polynomial [19]. However, it requires a large number of ciphertext rotations for high-dimensional LTs. To mitigate this, the design in [20] decomposes the matrix into multiple matrices consisting of different diagonals and applies a baby-step giant-step (BSGS) ciphertext rotation procedure. Additionally, the complexity of ciphertext rotation is reduced by a double hoisting technique [18], [21], which re-orders the computations to enable the combination of intermediate results. Several hardware accelerators over FPGA devices have been developed for HE evaluation of LT [22], [23], [24], [25], [26] based on the diagonal method in [19]. The designs in [22], [23] target low-dimensional LTs. The CHAM accelerator [24] employs the PackLWE algorithm [27] to pack the input data without encoding. However, it needs to store a large number of intermediate ciphertexts due to the automorphism operations and the tree structure used for packing intermediate ciphertexts. The design in [25] accelerates the diagonal method of LT by exploiting three forms of parallelism: partialsum parallelism, RNS polynomial parallelism, and coefficient parallelism. Recently, FAME [26] proposed a hardware accelerator for encrypted matrix-matrix multiplication, which is decomposed and implemented by LTs [28]. It improves performance upon [25] by combining intermediate results. For large LTs, storing matrices, rotation keys, NTT twiddle factors, and intermediate results may require hundreds of gigabytes of off-chip memory. Consequently, data transfers from off-chip memory introduce substantial latency. To mitigate this overhead, [25], [26] reduces off-chip memory access by storing
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
frequently reused data on-chip. Despite these efforts, HE-LT still requires substantial off-chip memory access and has very long latency. This paper first proposes to decompose the baby step in the BSGS algorithm into two layers to further reduce the number of required ciphertext rotations. Then, hoisting is applied across the three layers of ciphertext rotations to enable intermediate result combination. By adjusting the algorithm parameters, flexible trade-offs between the number of required rotation keys and computational complexity can be achieved. The second contribution of this work is an optimized data path for the proposed triple-hoisted (TH)-BSGS algorithm that substantially reduces off-chip memory access. Specifically, the algorithm is partitioned into phases, and the computations in each phase are re-ordered to maximize on-chip data reuse. The third endeavor is the development of an efficient hardware accelerator for implementing the proposed algorithm. In particular, the complexity of the automorphism used in ciphertext rotation is reduced by half by exploiting data permutation patterns. Our proposed design is evaluated over Xilinx FPGA devices. Compared to the best prior hardware accelerator supporting HE under the same parameter setting, the proposed design reduces the computational latency and off-chip memory access by 2.9∼10.6× and 1.9∼4.2×, respectively, while requiring similar hardware resources. The organization of this paper is as follows. Section II introduces background information on the CKKS scheme and the BSGS algorithm. Section III presents our new TH-BSGS algorithm, and Section IV proposes the data path optimization. The proposed hardware accelerator is detailed in Section V. Evaluation results and conclusions are provided in Sections VI and VII, respectively. II. BACKGROUND This section reviews essential information for the RNSCKKS scheme [15] and BSGS algorithm for HE-LT. A. RNS-CKKS Scheme In the CKKS scheme [4], a ciphertext is denoted as ct = (c0 , c1 ), where c0 , c1 ∈ RQ . To mitigate the complexity of modular operations on the very large polynomial coefficients, the RNS representation factors the modulus Q into L + 1 pairwise co-prime integers, i.e., Q = q0 q1 · · · qL , where the factors qj (0 ≤ j ≤ L) have about the same bit lengths and are referred to as the RNS moduli. Accordingly, an integer a mod Q can be uniquely expressed as the set (j) a = a mod qj | 0 ≤ j ≤ L . As a result, arithmetic operations on a, such as multiplication or addition, can be carried out as L independent operations on the corresponding residues a(j) [29]. In most existing work, such as [18], [19], [22], [24], [25], it is assumed that the constant matrix of the LT is in plaintext and the data input is encrypted. The multiplication of a ciphertext (j) (j) ct = {(c0 , c1 )} and a plaintext polynomial f = {f (j) } (0 ≤ j ≤ L) is carried out as o n (j) (j) (j) (j) (j) f × ct = c× = c×,0 , c×,1 = f (j) c0 , f (j) c1 .
2
ModUp
ModUp
ModDown
ModUp Decompose
ModDown
Figure 1. The block diagram for the key switching operation in the RNSCKKS scheme [18].
Random noise vectors have been added during the encryption, and the noise increases after each multiplication. To reduce the noise, the rescaling operation is carried out as h i (j) (j) (L) −1 rescale(c× ) = qL c× − c × , (0 ≤ j < L), (1) qj
where [·]qj denotes modulo reduction by qj . In the CKKS scheme [15], an input vector of N/2 entries can be packed into a ciphertext by canonical embedding. A rotation operation [4], [15] can be applied to the ciphertext for an input vector to derive another ciphertext corresponding to the same input vector cyclically shifted by r < N/2 positions. Let g be an integer that has order N/2 modulo 2N , e.g. g = 5. The ciphertext rotation by r slots to the direction of the least significant slot can be achieved by first applying the ring automorphism with parameter g r mod N as follows: (j)
(j)
ϕr : cl (x) 7→ cl (x(g
r
mod N )
)
(mod xN + 1).
(2)
Denote the secret key of the HE scheme by s(x). The result of the above automorphism is a ciphertext encrypted r under the transformed secret key ϕr (s(x)) = s(x(g mod N ) ) (mod xN +1). Hence, a key switching is required to re-encrypt it under the original secret key s(x). The generalized key-switching procedure in [18], [30] allows tradeoffs on the computation complexity and multiplicative depth. Its computations are outlined in Fig. 1. Let us ′(j) ′(j) assume that the ciphertext ct′ = (c0 , c1 ) is derived under ′(j) a secret key s′ . In the key switching, the polynomials c1 are firstly divided into β = ⌈(L + 1)/α⌉ groups, where each group contains α polynomials, except the last group, which may contain fewer than α polynomials. For such a division, a set of β switching keys swkb = (swkb,0 , swkb,1 ) ∈ R2P Q (0 ≤ b < β) are pre-determined based on s′ and s to which switching is performed. Here P is an integer that can be factored into α co-prime factors, p0 , p1 , · · · , and pα−1 , each of which has a similar bit length as ql . Since the modulus of the b-th group of the RNS representation of ciphertext ct′ is Qmin (α(b+1)−1,L+1) qj for b ∈ {0, 1, · · · , β − 1}, a Modup j=αb operation needs to be applied to raise its modulus to P Q before it can be multiplied with swkb as shown in Fig. 1. The ModUp is realized by applying a basis conversion process. In particular, a number represented in RNS format with respect to basis Q, {a(j) }, can be converted to the RNS representation
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
The BSGS algorithm [20] improves upon the diagonal method. To reduce the number of ciphertext rotations, which incur significant computational cost as explained in the previous section, the HE-LT is formulated as ! nX nX 2 −1 1 −1 LTF (ct) = Rot Rot (ct, i) · f̂n1 j+i , n1 j , (5)
Algorithm 1: Double hoisted BSGS algorithm (DHBSGS) for HE-LT[18]. Parameters: decomposition factors α, β, and n1 , n2 such that n1 n2 = n. g = ϕ−1 (swk ), Input: ct′ , swk i i i −1 g swk n1 j = ϕn1 j (swkn1 j ), f̂n1 j+i = ϕ−n1 j (fn1 j+i ) (0 ≤ i < n1 , 0 ≤ j < n2 ).
j=0
d ← Decompose(c′1 , α, β, Q, P ); ′ ′ 2 (a0 , b0 ) ← (P · c0 , P · c1 ) (mod P Q); 3 for i = 0 to i < n1 do g ⟩ ; 4 ai ← ϕi a0 + ⟨d, swk i,0 g ⟩ ; 5 bi ← ϕi ⟨d, swk i,1 6 (c0 , c1 ) ← (0, 0); 7 for j = 0 to j < n2 do Pn1 −1 8 (u0 , u1 ) ← i=0 (ai , bi ) · f̂n1 j+i ; 9 u1 ← ModDown(u1 ); 10 d ← Decompose(u1 , α, β, Q, P ); g 11 c0 ← c0 + ϕn1 j (u0 + ⟨d, swk n1 j,0 ⟩); g 12 c1 ← c1 + ϕn1 j (⟨d, swkn1 j,1 ⟩); 13 ct ← rescale (ModDown(c0 ), ModDown(c1 )) ; 1
Output: ct
with respect to basis P as [15] BConv({a
(j)
L X [q̂j−1 a(j) ]qj q̂j }, Q, P ) =
(mod pi ), (3)
j=0
where q̂j = Q/qj . After the inner product ĉ = ⟨d, swk⟩ = Pβ−1 b=0 db ·(swkb,0 , swkb,1 ) mod P Q is computed, the ModDown operation is carried out to bring the modulus back to Q. It is performed as c̃(j) = P −1 ĉ(j+α) − BConv({ĉ(i) }, P, Q) mod qj , (4) (j)
(j)
3
(j)
for 0 ≤ j ≤ L and 0 ≤ i < α [15]. Finally, ct = (c0 +c̃0 , c̃1 ) is the ciphertext under the secret key s. The (I)NTT can be applied to reduce the polynomial multiplication complexity. By reformulating the involved computations, the number of (I)NTTs is substantially reduced in [31].
i=0
where n = n1 n2 and f̂n1 j+i = ϕ−n1 j (fn1 j+i ) [20]. By decomposing the rotation and summation into two layers as in (5), the number of ciphertext rotations needed is reduced from n − 1 to n1 + n2 − 2. √ The complexity can be minimized by setting n1 ≃ n2 ≃ n. In (5), the inner rotations and summations are referred to as the baby step, while the outer rotations and summations are the giant step. The double-hoisted BSGS algorithm [18] reduces the complexity of the BSGS algorithm, and it is summarized in Algorithm 1. A ciphertext rotation applies the ϕ function as defined in (2), followed by the key switching procedure shown in Fig. 1, which consists of three steps: Decompose, switching key inner product computation, and ModDown. Since each rotation in (5) has a different offset, the key switching in each rotation has different inputs and therefore requires a separate Decompose operation. Hoisting delays the application of the ϕ function until after the switching key inner product computation, so that all the Decompose operations for the inner layer rotations in (2) are performed on the same inputs, requiring only a single Decompose operation. To enable this, the inverse ϕ function is applied to the switching keys. The same hoisting is applied to all the rotations in the outer layer of (2). Instead of performing the ModDown operation at the end of each key switching operation, as shown in Fig. 1, the DHBSGS algorithm changes the order of the ModDown operation and the multiplication with f̂ in the inner layer computation of (5). As a result, only a single ModDown operation is required on the accumulated sum of the products. Overall, the DH-BSGS algorithm requires n2 Decompose operations, n2 + 1 ModDown operations, and n1 + n2 − 2 switching keys. Although decreasing n2 reduces the computational complexity, it increases the number of switching keys. Therefore, a tradeoff between the memory usage and computational complexity can be achieved by adjusting the parameters.
B. BSGS Algorithm for HE-LT Without loss of generality, consider an LT whose constant matrix F is of dimension n × n and n ≤ N/2. If the matrix size is not a power of two, zeros are padded. If n > N/2, the matrix must first be decomposed into smaller blocks with dimensions at most N/2, since up to N/2 data elements can be packed into a polynomial using the packing scheme in [15]. The diagonal method of HE-LT in [19] divides F into n diagonal lines. The entries in the i-th diagonal are packed into the polynomial fi (0 ≤ i < n). Then, the ciphertext corresponding to the linearly input vector can be Ptransformed n Rot(ct, i) · fi , where ct is computed as LTF (ct) = i=0 the ciphertext of the input data vector, and Rot(ct, i) denotes ciphertext rotation by i positions.
III. P ROPOSED T RIPLE -H OISTED BSGS A LGORITHM This section proposes a new TH-BSGS algorithm for HELT. It decomposes the baby step computation of the DH-BSGS algorithm into two layers of ciphertext rotations. The hoisting technique is then applied to reduce the Decompose operations. Furthermore, the ModDown operations in all three layers are delayed/combined as much as possible to minimize the computational complexity. With lower computational complexity, the proposed algorithm achieves a substantial reduction in memory requirements compared to the DH-BSGS algorithm. Decompose n into n′1 n′2 n′3 . Then (5) can be reformulated
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
as LTF (ct) =
X k=0
Rot
′ ′ nX 2 −1 n 1 −1 X
j=0
Rot Rot(ct, i), n′1 j
i=0
· f̂n′1 n′2 k+n′1 j+i , n′1 n′2 k .
Algorithm 2: Proposed TH-BSGS Algorithm for HELT. Parameters: decomposition factors α, β, and n′1 , n′2 , and n′3 such that n′1 n′2 n′3 = n. ′ g g ′ , swk g ′ ′ , and Input: ct , swki , swk n1 j n1 n2 k f̂n′1 n′2 k+n′1 j+i = ϕ−n′1 n′2 k (fn′1 n′2 k+n′1 j+i ) (0 ≤ i < n′1 , 0 ≤ j < n′2 , and 0 ≤ k < n′3 ),
(6)
By applying hoisting and other reformulations to eliminate and/or combine computations in this formula, our new THBSGS algorithm is proposed, as summarized in Algorithm 2. By applying the hoisting technique, a single Decompose operation can be shared among all inner rotations for 1 ≤ i < n′1 . This is reflected in Line 1 of Algorithm 2. Since the ai values in Line 4 of Algorithm 2 are not multiplied by any switching keys, the corresponding ModDown operations can be delayed until the end. However, the inner-layer rotations are immediately followed by the middle-layer rotations rather than by sum-of-products computations. Therefore, the ModDown operation on bn′1 j+i cannot be delayed in the same manner as in the DH-BSGS algorithm. For the middle layer of rotations in (6), the hoisting technique is also applied, requiring only n′1 − 1 Decompose operations, as shown in Line 7 of Algorithm 2. Since this stage is followed by sum-of-products computations, the ModDown operations can be delayed and applied only to the accumulated sum, as shown in Line 16. Similarly, the hoisting technique can also be applied to the outer layer of rotations. Table I compares the complexity of the proposed THBSGS method with the diagonal method [26], the BSGS algorithm [32], and the double-hoisted BSGS algorithm [18]. The computational complexity is mainly dominated by Decompose, ModDown, and coefficient-wise polynomial multiplication operations. Compared with the switching keys, the twiddle factors required for the (I)NTTs in the Decompose and ModDown blocks are very small; therefore, they are omitted from the comparison. From Algorithm 2, it can be directly observed that the TH-BSGS algorithm requires n′1 + n′3 − 1 Decompose operations, n′1 + n′3 ModDown operations, and n′1 + n′2 + n′3 − 3 switching keys. Since each switching key has modulus P Q, it is represented using (L + 1 + α) RNS components. Following the notations in [26], the RNS components are also referred to as limbs in this paper. In addition, each switching key consists of two polynomials. The multiplications with the switching keys contribute to the first term of the coefficient-wise polynomial multiplication complexity listed in Table I. The second term arises from multiplying the input ciphertext by the diagonals of the LT constant matrix. Since the BSGS algorithm carries out these computations over modulus Q, rather than modulus P Q as in the other three methods listed in Table I, its multiplications are performed over L + 1 limbs instead of L + 1 + α limbs. In the proposed design, trade-offs between computational complexity and the number of switching keys can be achieved by tuning n′1 , n′2 , and n′3 , subject to the constraint n′1 n′2 n′3 = n. Assume that w = 54 bits are used to represent each polynomial coefficient in RNS format. For N = 216 , n = 215 , α = 12, and L = 31, Fig. 2 plots the trade-off between computational complexity and number of switching
d0 ← Decompose(c′1 , α, β, Q, P ); ′ ′ 2 (a0 , b0 ) ← (P · c0 , P · c1 ) (mod P Q); ′ 3 for i = 1 to i < n1 do g ⟩); 4 ai ← ϕi (a0 + ⟨d0 , swk i,0 g ⟩); 5 bi ← ϕi (⟨d0 , swk i,1 6 b′i ← ModDown(bi ); 7 di ← Decompose(b′i , α, β, Q, P ); ′ 8 for i = 0 to i < n1 do 9 for j = 1 to j < n′2 do g ′ ⟩); 10 an′1 j+i ← ϕn′1 j (ai + ⟨di , swk n1 j,0 g ′ ⟩); 11 bn′1 j+i ← ϕn′1 j (⟨di , swk n1 j,1 Pn′1 n′2 12 (c0 , c1 ) ← i=0 (ai , bi ) · f̂ i ; ′ 13 for k = 1 to k < n3 do Pn′1 n′2 14 (u0 , u1 ) ← i=0 (ai , bi ) · f̂ n′1 n′2 k+i ; 15 u1 ← ModDown(u1 ); 16 d ← Decompose(u1 , α, β, Q, P ); g ′ ′ ⟩); 17 c0 ← c0 + ϕn′1 n′2 k (u0 + ⟨d, swk n1 n2 k,0 g ′ ′ ⟩); 18 c1 ← c1 + ϕn′1 n′2 k (⟨d, swk n1 n2 k,1 19 ct ← rescale (ModDown(c0 ), ModDown(c1 )) ; Output: ct 1
1e11
Number of Modular Multiplications (×1011)
n′3 −1
4
# of Modular Multiplications vs Memory BSGS Double Hoisted BSGS Triple Hoisted BSGS
(n1, n2) : (27, 28) Memory : 41.55 GB # of MMs: 2.82e+11
2.8 2.6
(n1, n2) : (27, 28) Memory : 41.55 GB # of MMs: 2.46e+11
2.4
(n1, n2) : (29, 26) Memory : 62.43 GB # of MMs: 2.12e+11
2.2 2.0 0
(n01, n02, n03) : (25, 25, 25) Memory : 10.12 GB # of MMs: 2.03e+11 (n01, n02, n03) : (24, 27, 24) Memory : 17.08 GB # of MMs: 50 1.98e+11 100
150
Memory of Switching Keys (GB)
200
Figure 2. Number of modular multiplications and switching key size of different LT algorithms for n = 215 , L = 31, w = 54, and α = 12.
keys achieved by the proposed design. In this figure, the sum of the numbers of coefficient modular multiplications from Decompose, ModDown, and polynomial multiplications is used to represent the overall computational complexity. The data points from left to right correspond to increasing values of n′2 . For each n′2 , the parameters n′1 and n′3 are selected
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
5
Table I C OMPLEXITY COMPARISONS OF TH-BSGS ALGORITHM AND PRIOR METHODS FOR RING DIMENSION N , MATRIX DIMENSION n ≤ N/2, DECOMPOSITION PARAMETERS α AND β, L + 1 RNS MODULI OF BIT LENGTH w, AND n′1 n′2 n′3 = n1 n2 = n. Algorithm
Decompose
ModDown
Diagonal method [19]
1
2
BSGS [32]
n1 + n2 − 2
2(n1 + n2 − 2)
DH-BSGS [18]
n2
n2 + 1
Proposed TH-BSGS
n′1 + n′3
n′1 + n′3 + 1
Coeff.-Wise Poly. Mult. 2β(n − 1)(L + 1 + α) +2n(L + 1 + α) 2β(n1 + n2 − 2)(L + 1 + α) +2n(L + 1) 2β(n1 + n2 − 2)(L + 1 + α) +2n(L + 1 + α) 2β(n′1 +n′2 +n′3 −3)(L+1+α)
to be approximately equal while satisfying n′1 n′2 n′3 = n in order to minimize the computational complexity. It can be observed that the proposed design achieves significantly better memory–computation trade-offs than the BSGS and DH-BSGS schemes. The diagonal method requires a very large number of polynomial multiplications and switching keys and is therefore omitted from further comparison. For each of the DH-BSGS and TH-BSGS algorithms, two points are highlighted in Fig. 2: one corresponding to the setting with the minimum memory requirement and the other corresponding to the setting with the lowest computational complexity. The memory requirement of the proposed TH-BSGS design is √ minimized when n′1 ≃ n′2 ≃ n′3 ≃ 3 n. The configuration achieving the lowest computational complexity requires slightly more memory and is therefore considered to provide the best trade-off. For the best trade-off settings, the TH-BSGS algorithm reduces the memory requirement by 62.43/17.08 = 3.65× compared with the DH-BSGS algorithm. For the BSGS algorithm, the lowest computation complexity and number of switching keys are both achieved when n1 is about the same as n2 . Hence, only one point is shown in Fig. 2 for this algorithm. Although the TH-BSGS algorithm substantially reduces the complexity of ciphertext rotations, the overall computational complexity becomes dominated by the polynomial multiplications. Consequently, the proposed design achieves a computational complexity similar to that of the BSGS and DH-BSGS algorithms. IV. M EMORY-O PTIMIZED HE-LT DATAPATH The proposed TH-BSGS algorithm substantially reduces the number of switching keys and, consequently, the required off-chip storage. However, large LTs still require access to gigabytes of data stored in off-chip memory. For a typical HE parameter set used in practical applications, the TH-BSGS algorithm needs to access >300 GB of off-chip memory data to evaluate the LT during bootstrapping. Accessing offchip memory introduces significant latency and accounts for the majority of the overall HE-LT latency. In this section, a memory-optimized data path is proposed to maximize onchip data reuse and minimize off-chip memory traffic for the TH-BSGS algorithm. Although data path optimizations have previously been proposed for the diagonal method [25], [26],
+2n(L + 1 + α)
# of Switching Keys β(n − 1)(L + 1 + α) β(n1 + n2 − 2)(L + 1 + α) β(n1 + n2 − 2)(L + 1 + α) β(n′1 +n′2 +n′3 −3)(L+1+α)
the hoisting technique along with the BSGS method changes the order of computations. Therefore, the data path must be redesigned accordingly. Considering the data-access patterns, Algorithm 2 is partitioned into six phases to reduce off-chip memory access. In each phase, data is first read from off-chip memory, intermediate results are stored and reused in on-chip memory, and the final outputs are written back to off-chip memory at the end of the phase. Phase 1 consists of Lines 1–5 of Algorithm 2. Due to the very large polynomial sizes involved in HE, computations over the limbs are performed one after another by sharing hardware units. Since the ModDown operation in Line 6 requires all RNS components before it can begin, the ModDown and Decompose operations in Lines 6 and 7 are grouped into Phase 2. The two nested ‘for’ loops in Lines 8–11 and the computation in Lines 12–14 access data using different patterns. Therefore, they are separated into Phases 3 and 4, respectively. Since each limb generated by the ModDown and Decompose operations in Lines 15–16 is immediately consumed by the computations in Lines 17–18, these operations are grouped into Phase 5. Finally, Phase 6 consists of the final ModDown and rescaling operations in Line 19. The data flow for each phase is illustrated in Fig. 3. In this figure, an NTT operation is applied before each polynomial multiplication, and an INTT operation is applied to transform the results back to the polynomial domain for modulus switching. The (I)NTT blocks are explicitly shown in the figure, and the polynomials expressed in the NTT domain are denoted using uppercase boldface letters (e.g., A = NTT(a)). The blue and green lines in Fig. 3 represent reading/writing from/to off-chip and on-chip memories, respectively. The black lines indicate data dependencies without memory accesses. To reduce the latency, ping-pong buffers are employed for reading/writing data from/to off-chip memory. The solid lines in Fig. 3 denote simultaneous reading/writing of all polynomial limbs from/to memory. Due to the limited on-chip memory, some functions process only a subset of the limbs at a time; these operations are represented by dashed lines in Fig. 3. The data flow in the proposed design has been optimized to maximize data reuse, as detailed below. Phase 1: The computations in Lines 1–5 of Algorithm 2
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
ModDown
Decompose BConv
BConv
NTT
6
Decompose BConv
NTT
BConv
NTT
-
INTT BConv
NTT
Limb iteration loop Index iteration loop
INTT
(b)
Limb iteration loop (c)
Index iteration loop Limb iteration loop (a) ModDown
BConv INTT
Indexes iteration loop Limb iteration loop
Decompose BConv
NTT
BConv
NTT
INTT
BConv
-
NTT
-
(f)
Index iteration loop
(d)
Limb iteration loop
off-chip transfer
on-chip transfer
off-chip limb transfer
on-chip limb transfer
(e)
Figure 3. Block diagrams of the proposed memory-optimized data path of (a) Lines 1–5 (Phase 1); (b) Lines 6–7 (Phase 2); (c) Lines 8–11 (Phase 3); (d) Line 12–14 (Phase 4); (e) Lines 15–18 (Phase 5); (f) Line 19 (Phase 6) of the TH-BSGS Algorithm 2.
are performed in this phase, and the corresponding data flow is illustrated in Fig. 3(a). Since the input to the Decompose block contains only L + 1 limbs, the INTT operations for all components are carried out in parallel, and the results are stored in on-chip memory. However, the output of each BConv block contains L + 1 + α limbs, and the available on-chip memory may not be sufficient to store all of these results simultaneously. In the proposed design, l1 (l1 ≤ L + 1 + α) limbs are computed at a time for each of the β BConv units, requiring ⌈(L + 1 + α)/l1 ⌉ rounds to complete the computation. The NTT computation then follows, and each limb is simultaneously multiplied by m1 switching keys. It takes ⌈(n1 − 1)/m1 ⌉ iterations to complete the multiplication with all switching keys associated with the l1 limbs. Therefore, the overall number of iterations in this process is ⌈(L + 1 + α)/l1 ⌉ ⌈(n1 − 1)/m1 ⌉. The parameters l1 and m1 can be tuned to achieve optimal memory–computation tradeoffs. Phase 2: This phase performs the computations in Lines 6–7 of Algorithm 2, and its data flow is depicted in Fig. 3(b). The Decompose block is implemented similarly to that in Phase 1. To allow more flexibility in the memory–computation complexity trade-off, the parallelism levels of the BConv and NTT blocks are configured as m2 and l2 on the number of ModDown/Decopose operations and polynomial limbs processed at a time, respectively. Phase 3: This phase executes Lines 8–11 of Algorithm 2 and its data flow is shown in Fig. 3(c). Each of Ai Di , and SWKn′1 j has L+1+α, β(L+1+α), and 2β(L+1+α) limbs. To minimize off-chip memory access, the maximum possible number of switching keys should be loaded into the available on-chip memory and reused as much as possible. Assume that m3 (1 ≤ m3 < n′2 ) switching keys can be loaded into on-chip memory, and the remaining on-chip memory can hold m4 Ai and Di with l3 limbs each. Then the two loops in Lines 6-7 can be completed in ⌈n′1 /m4 ⌉⌈(n′2 − 1)/m3 ⌉⌈(L + 1 + α)/l3 ⌉
Table II PARALLELISMS FOR OPTIMIZED DATAPATH IN THE TH-BSGS ALGORITHM . Parameter
Description
m1
Number of switching keys processed simultaneously in Phase 1. Number of ModDown/Decompose operations performed simultaneously in Phase 2. Number of switching keys processed simultaneously in Phase 3. Number of Ai and Di values processed simultaneously in Phase 3. Number of ciphertexts partially accumulated at a time in Phase 4. Number of ModDown/Decompose operations and switching keys processed simultaneously in Phase 5. Limb-level parallelism in Phase 1 ≤ p ≤ 5.
m2 m3 m4 m5 m6 lp
rounds. Phase 4: The computations in Lines 12-14 of Algorithm 2 are realized in this phase, as shown in Fig. 3(d). The polynomials Ai , Bi , U0,k , and U1,k have the same number of limbs. However, the number of possible values of k and i are n′3 and n′1 n′2 , respectively. Since n′3 ≪ n′1 n′2 , to minimize the off-chip memory access, Ai and Bi should be reused as much as possible once loaded into the on-chip memory. If the onchip memory is not sufficient, intermediate polynomials U0,k and U1,k will be written/read to/from the off-chip memory. The number of polynomials and the number of limbs in each polynomial to process each time are set to m5 and l4 , respectively, in our design. The parameter m5 is set to its maximum possible value to minimize off-chip memory access. Phase 5: Lines 15–18 of Algorithm 2 are executed in this phase. The block diagram for this phase is illustrated in Fig. 3(e). The number of polynomials and the number of limbs in each polynomial to process each time are set to m6 and l5 , respectively. The design is similar to that for phase 1 and 2.
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
7
Table III M EMORY REQUIREMENT FOR THE PROPOSED OPTIMIZED DATA PATH OF THE TH-BSGS ALGORITHM . off-chip memory access
1 2
(I)NTT
LT matrix (F̂)
switching key
0
2(n′1 −1)β
2(L+1+α) n′1 −1 m1
3
(L+1+α) 0
peak on-chip memory
polynomial read
(L+1+α)
2(L+1)
2n′1 (L+1+α) (n′1−1)β(L+1+α)
0
0
(n′1 −1)(L+1+α)
0
2(n′2 −1)β
n′2 −1 ′ n1 (β +1)(L+1+α) m3
(L+1+α)
′
4
L+1+α
n(L+1+α)
5
n′3 (L+1+α) m6
0
6
L+1+α
0
Set-A
10.00
(0.9 × , 2.7 × )
7.50
n′1 n′2 ′ 2 m n3 5
(L+1+α)
(L+1+α)
2.116
′
n′
2(n′3 −1)β
2.469
2n′1 n′2 (L+1+α)
n1 n2 2(n′1 n′2+( m −1)n′3 ) 5
2(n′3 + m3 −1) (L+1+α)
0
2(L+1+α)
Set-B
6
+2βl2 ) + 2l2 2l3 ((β + 1)m4 + 2βm3 +2m3 m4 ) 6m5 l4 + 5l4 m6 (L+1+α)+ (5βm6+2m6+6)l5 +2l5 2(L+1+α)
Set-C
1e11
400
1.019
4000
9.092
350
0.891
3500
7.956
0.764
3000
6.819
250
0.637
2500
200
0.509
150
(2.9 × , 3.8 × ) 0.382
2000
300
(1.5 × , 3.6 × )
5.00
1.411
3.75
(1.9 × , 2.8 × ) 1.058
2.50
0.705
100
0.255
1000
1.25
0.353
50
0.127
500
0.00
0.000 THBSGSReuse
0
0.000 THBSGSReuse
0
(I)NTT
m2 (2(L + 1) + α
1e11
1.764
DHBSGS
+(4β + 6)m1 l1
2(L+1)
6.25
DiagonalReuse
2(L + 1) + (β + 4)l1
n′
2 m3 (L+1+α)
6
(L+1+α)
1e9 2.822
8.75
Off-chip Access Cost (GB)
0
requirement
polynomial write
LT matrix
DiagonalReuse
DHBSGS
SWK
polynomial read
# of Modular Multiplication
Phase
5.683
(2.2 × , 4.5 × )
1500
4.546
(4.2 × , 4.8 × )
3.410 2.273 1.137
DiagonalReuse
DHBSGS
0.000 THBSGSReuse
polynomial write
Figure 4. Comparisons of off-chip memory access (left axis) and number of modular multiplications (right axis) for the diagonal method [26], DH-BSGS [18], and proposed memory-optimized TH-BSGS method for HE parameters in Table V. The numbers inside parentheses represent the improvements in memory and computation complexity relative to the diagonal method [26].
Phase 6: This phase implements the combined ModDown and rescaling in Line 19 of Algorithm 2 [33]. All limbs in the polynomials are processed simultaneously. The parallelisms utilized for the six phases are summarized in Table II. Table III lists the breakdown of off-chip memory access and the peak on-chip memory requirement for the proposed TH-BSGS algorithm across different phases in terms of the number of limbs. In this table, the memory access associated with reading the twiddle factors is included under the (I)NTT column. The maximum amount of on-chip memory required at any point during the execution of each phase is also reported. The overall on-chip memory requirement is determined by the maximum value among all six phases. According to the formulas provided in Table III, the parallelism parameters listed in Table II can be tuned to minimize off-chip memory access and/or on-chip memory requirement. Consider the implementation on the Xilinx UltraScale+ U280 FPGA as an example. The device provides 43 MB of onchip memory. For the three sets of typical HE and LT parameters listed in Table V, all feasible parallelism configurations that do not exceed the on-chip memory available are exploited, and the setting achieving the lowest off-chip memory access are plotted in Fig. 4. It can be observed that the proposed
TH-BSGS design achieves approximately a 50% reduction in off-chip memory access compared with the DH-BSGS scheme. The proposed scheme also significantly reduces the number of Decompose and ModDown operations required for ciphertext rotations, as shown in Table I. However, polynomial multiplications still account for the majority of the overall computational complexity. Consequently, the total number of modular multiplications required by the proposed design is only slightly lower than that of the DH-BSGS algorithm. V. H ARDWARE ACCELERATOR FOR HE-LT This section presents a hardware accelerator for the proposed memory-optimized TH-BSGS algorithm for HE-LT. In particular, a new permutation method is proposed to implement the automorphism in (2) without requiring scratchpad memory, while reducing the latency by half. The top-level architecture of the proposed accelerator is illustrated in Fig. 5. It consists of five main components: an array of nPE processing elements (PEs), an array of nTA tree adders (TAs), nPC copies of the permutation circuit (PC), a bank of scratchpad memories, and a control unit. The on-chip memory is the primary resource bottleneck of the HE-LT accelerator. Given the available onchip memory blocks and the HE parameters, the storage
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
AXI 0
Stack 1
AXI 31
FIFO 1
FIFO 15
FIFO 31
Table IV PE CONTROL BITS CONFIGURATION FOR VARIOUS OPERATION MODES .
PE Array
Tree Adder Array
Control Unit
AXI 15
FIFO 0 Scratchpad Memory
HBM 2
HBM Controller
Stack 0
AXI 1
8
Permutation Circuit Array
Sel. Sig.
NTT
INTT
CWPM
CWPA
CM
CWPA-CM
s0
1
0
x
x
x
0
s1
1
0
x
0
x
x
s2 s3
00
10
01
xx
01
11
s4
0
0
1
x
0
0
s5
1
0
x
x
x
x
s6 s7
00
01
10
00
10
10
Figure 5. Top-level architecture of the proposed accelerator for HE-LT.
Figure 6. Architecture for the PE.
capacity for the polynomials, and consequently the number of coefficients in each polynomial that can be processed simultaneously, denoted as dp, is determined. The product of dp and the number of polynomials processed concurrently determines nPE . By analyzing the data flow across the six phases of Algorithm 2, the required number of TAs for the summations in Decompose, ModDown, the inner product with switching keys, and Lines 12 and 14 can then be determined. nPC is simply equal to the number of polynomials processed simultaneously during the automorphism operation. Similar to prior designs [26], it is assumed that the off-chip memory is implemented using high-bandwidth memory (HBM) comprising two stacks, each with 16 AXI channels capable of transferring 256 bits of data in parallel. FIFOs are employed to decouple communication between the off-chip and on-chip memories. The details of each of the five components in the proposed accelerator are described below. PE Array: Each PE supports six operating modes: butterfly operations for NTT and INTT, coefficient-wise polynomial multiplication (CWPM), coefficient-wise polynomial addition (CWPA), constant multiplication (CM), and a combined CWPA-CM operation. In the NTT and INTT modes, each PE takes three inputs: a0 , a1 , and a twiddle factor tf. In NTT mode, the outputs are a0 +a1 ·tf and a0 −a1 ·tf. In INTT mode, the outputs are (a0 +a1 )/2 and ((a0 −a1 )/2)·tf. In CWPM and CWPA modes, the inputs are a0 and a1 , producing the outputs a0 a1 and a0 + a1 , respectively. In CM mode, the inputs are a constant c and a polynomial coefficient a0 , and the output is ca0 . Finally, in CWPA-CM mode, the inputs are a constant c and two polynomial coefficients a0 and a1 , and the output is c(a0 − a1 ). All six operating modes can be implemented using the PE architecture shown in Fig. 6 by configuring
the multiplexer select signals according to Table IV. The adders, multiplier, and × 12 units perform modular arithmetic operations and can be implemented using the designs in [12], [13]. The modular multiplier internally incorporates pipeline stages [14]. TA Array: The number of inputs to a TA can be β +1, α, or m5 , depending on the computation. To support the processing of dp coefficients in each polynomial, dp TAs are required for each polynomial. Accordingly, nTA can be determined based on the memory-optimized data path shown in Fig. 3. Permutation Circuit Array: The permutation circuits reorder polynomial coefficients to support two types of operations: (I)NTT and the ϕr (·) automorphism in (2). Since dp coefficients from each polynomial are processed simultaneously, each permutation circuit has dp inputs. The data in each butterfly stage of the (I)NTT are accessed according to constant strided patterns [9], [12]. By exploiting these switching patterns, the permutation circuit in [34] can be significantly simplified. Prior works have also employed the permutation circuits in [34] to implement automorphism operations. However, the automorphism defined in (2) possesses special properties that enable substantial simplifications in the permutation circuit. The proposed design is described below. As shown in Fig. 3, the inputs to each ϕr (·) function are in the NTT domain. In this case, the automorphism operation in (2) needs to be modified such that it maps the coefficient Ai to Aj , where j = ((gr (2i + 1)
mod 2N ) − 1)/2,
(7)
and gr = g r mod N . Besides, the outputs of the NTT operations are stored in bit-reversed order in memory. This also needs to be taken into account when permuting coefficients to implement the automorphism. In the proposed design, the coefficients of an NTT transformed polynomial, Ai (0 ≤ i < N ), are stored across dp memory blocks, where block f stores Abitrev(i,log N ) for f N/dp ≤ i ≤ (f + 1)N/dp − 1. The function bitrev(·, n) reverses the bits of an n-bit integer. For example, bitrev(1, 3) = bitrev(‘001’, 3) = ‘100’ = 4. To carry out the automorphism, one coefficient is read from each of the dp memory blocks. It will next be shown that these dp coefficients are permuted to another set of dp coefficients, with exactly one coefficient mapped to each of the dp memory blocks according to the automorphism. These coefficients replace the coefficients stored at the corresponding memory addresses, while the coefficients previously stored at those
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
addresses are routed to the permutation circuit for switching. Since the automorphism guarantees a one-to-one mapping, repeating this process eventually covers all coefficients involved in the permutation. Since the coefficients are stored in bit-reversed order, for the coefficient stored in address nf of memory block f , its index in the polynomial is given by
9
Table V S ETS OF HE PARAMETERS FOR 128- BIT SECURITY USED FOR EVALUATION . N
L+1
α
β
w
Set-A
213
5
5
1
54
Set-B
215
16
8
2
54
Set-C
216
32
12
3
54
idx = bitrev(f N/dp+nf , log N ) = if N/dp+jf dp+kf , where kf = bitrev(f, log dp). It is assumed that dp is a power of two and is much smaller than N/dp. Hence, jf and if correspond to the log N/(dp2 ) least significant bits and the remaining higher bits of bitrev(nf , log(N/dp)), respectively. Plugging in (7), the automorphism maps the coefficient to the coefficient with the index below. [gr (2if N/dp + 2jf dp + 2kf + 1)]2N − 1 idx′ = 2 gr−1 N = [gr if ]dp dp +[gr jf ] N dp + gr kf + 2 N (8) dp N = [gr if + tf ]dp + [gr jf + uf ] N dp + vf dp dp = i′f N/dp + jf′ dp + kf′ , where vf , uf , and tf are the log(dp) least significant bits, log(N/(dp)2 ) middle bits, and rest higher bits in gr kf + (gr − 1)/2, respectively. In another word, gr kf + (gr − 1)/2 = tf N/dp+uf dp+vf . Besides, let kf′ = vf to keep the notations consistent. For f1 ̸= f2 , it can be shown that kf′ 1 ̸= kf′ 2 . A proof by contradiction is given as follows. Suppose kf′ 1 = kf′ 2 and hence vf1 = vf2 . Then the following equation must hold: gr (kf1 − kf2 ) = (tf1 − tf2 )N/dp + (uf1 − uf2 )dp = (tf1 − tf2 )N/dp2 + (uf1 − uf2 ) dp. Since gr is an odd number, the above equation implies that |kf1 − kf2 | ≥ dp. On the other hand, since 0 ≤ kf1 , kf2 < dp, the inequality |kf1 − kf2 | < dp hold, which is a contradiction. From (8), the polynomial coefficient from address nf of memory block f becomes the coefficient with new index idx′ . Rewrite bitrev(idx′ ) as bitrev(i′f N/dp + jf′ dp + kf′ , log N ) = f ′ N/dp + n′f , where f ′ = bitrev(kf′ , log dp) corresponds to the log(dp) most significant bits, and n′f corresponds to the remaining bits. The coefficient with index idx′ is then written to address n′f in memory block f ′ . For f1 ̸= f2 , kf′ 1 ̸= kf′ 2 and consequently f1′ ̸= f2′ . Therefore, coefficients from different memory blocks are not written back to the same memory block after the permutation. From the above analysis, the coefficient permutation for the automorphism can be implemented using dp dp-to-1 multiplexers. These multiplexers are controlled by f ′ , which can either be computed on-the-fly or precomputed and stored in a look-up table (LUT). Compared with the permutation circuit in [34], the proposed design reduces the number of multiplexers by half and eliminates the additional memory buffers, thereby reducing the latency by half.
VI. E XPERIMENTAL R ESULTS AND C OMPARISONS This section first presents the setting for experimental evaluation over FPGAs. Next, it compares our proposed design with prior works in terms of hardware resource requirements and latency. The proposed HE-LT accelerator is described in System Verilog HDL and synthesized on the Virtex UltraScale+ U280 FPGA using Vivado 2023.2. The FPGA contains 1304K LUTs, 2607K FFs, 2016 BRAMs, 960 URAMs, and 9024 DSPs. The proposed design is synthesized for the three sets of HE parameters listed in Table V, each supporting a different multiplication depth, L. In this table, w denotes the bit width of the modulus for each RNS component. For HE defined over the ring RQ = ZQ [x]/(xN + 1), at most N/2 slots can be packed into a ciphertext. Therefore, an LT dimension of n = N/2 is considered in the evaluation, as listed in Table VI. The values of n′1 , n′2 , and n′3 in the proposed design are selected to achieve the best tradeoff between computational complexity and the number of switching keys. Given the amount of on-chip memory available on the U280 FPGA, the maximum parallelism that can be exploited in each phase is determined as shown in Table II. The number of coefficients from each polynomial that can be processed simultaneously, dp, is determined by the URAM size and the value of N . After determining these parallelism parameters, the numbers of computation units, namely nPE , nTA , and nPC , are chosen as listed in the table. The FPGA resource utilization and maximum achievable clock frequency from the synthesis reports are listed in Table VII. Python is used to emulate the number of clock cycles needed to carry out the computations needed for HE-LT. Multiplying the number of clock cycles with the achievable clock period, the computation latency in terms of millisecond is also listed in the table. This latency does not include the latency for off-chip memory access, which contributes to the majority of the overall latency. The off-chip memory access latency is dependent on the bandwidth, communication protocols, and many other factors. Since such simulation model is not available, the amount of data to be read from/written to off-chip memories are listed in Table VII for comparison. The HE-LT design in [25], CHAM [24], and FAME [26] are among the most efficient hardware accelerators for HE-LT. Their synthesis results are listed in Table VII for comparison. FAME uses the same set of HE parameters as our proposed design. Compared to those in FAME, the numbers of LUTs, flip-flops (FFs), BRAMs, URAMs, and DSP blocks required by our design are either smaller or bigger, but they are in a similar scale. However, our proposed design reduces the com-
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
10
Table VI T HE ALGORITHMIC AND HARDWARE PARAMETERS FOR DIFFERENT HE PARAMETER SETS . n
(n′1 , n′2 , n′3 )
(m1 , l1 )
(m2 , l2 )
(m4 , m3 , l3 )
(m5 , l4 )
(m6 , l5 )
nPE
nTA
nPC
dp
Set-A
212
(23 , 26 , 23 )
(7, 5)
(7, 10)
(1, 63, 1)
(103, 1)
(8, 5)
196
244
98
2
Set-B
214
(24 , 27 , 23 )
(4, 2)
(1, 12)
(1, 11, 1)
(25, 1)
(4, 1)
256
193
30
8
Set-C
215
(24 , 27 , 24 )
(1, 1)
(1, 1)
(1, 4, 1)
(12, 1)
(1, 1)
396
195
33
16
Table VII T HE HARDWARE RESOURCE UTILIZATION OF THE PROPOSED WORK COMPARED WITH THOSE OF PRIOR HE-LT ACCELERATORS .
Design
HE-LT in [25] CHAM [24] FAME [26]
Proposed
kFF
BRAM URAM DSP Freq. (MHz)
Computation Latency
Off-Chip Mem.
# of clks (×106 ) | ms
Cost (GB)
Parameters
Device
kLUT
Set-A′
Xilinx U200
756.3
610.4
224
656
4896
200
154.79 | 773.96
5.70
Set-B′
Xilinx U200
835.6
1093.2
896
742
5712
180
2061.15 | 11450.86
100.40
Set-C′
Xilinx U200
835.6
1093.2
896
742
5712
180
27854.91 | 154749.49
1464.68
N=212 , L+1=2 Xilinx VU9P
752.9
483.6
1558
595
1986
300
16.83 | 56.09
0.46
1024
0
5376
350
18.95 | 54.14
6.33
Set-A
Xilinx U280
636.0
998.0
Set-B
Xilinx U280
701.0
1147.0
640
192
5376
350
837.13 | 2391.80
405.02
Set-C
Xilinx U280
803.0
1660.0
3328
672
5376
300
7500.78 | 25002.61
4158.02
Set-A
Xilinx U280
420.0
505.3
2008
960
3332
350
6.60 | 18.87
3.36
Set-B
Xilinx U280
639.5
639.2
2016
960
4352
350
145.24 | 414.98
140.75
Set-C
Xilinx U280 1377.5
986.4
2016
960
6732
300
708.24 | 2360.79
998.60
putation latency and off-chip memory access by 2.9∼10.6× and 1.9∼4.2×, respectively, for the three sets of parameters. The HE parameters adopted in the HE-LT design from [25] are smaller. Nonetheless, our design achieves 23.4∼39.3× computation latency reduction and also significant off-chip memory access reduction at the scale. The CHAM design only supports N = 212 and L + 1 = 2. All previous hardware accelerators for HE-LT, including those in [24], [25], [26], are based on the diagonal method or PackLWE algorithm [27]. There is no existing hardware accelerator based on the BSGS or DH-BSGS algorithm. However, from the analysis in Section III, the DH-BSGS algorithm would require similar hardware resources as our proposed design. On the other hand, our design reduces the off-chip memory access by around twice from Section IV.
R EFERENCES [1]
[2]
[3]
[4]
VII. C ONCLUSIONS This paper proposes a triple-hoisted BSGS algorithm for HE-LT. The decomposition of the baby step enables reformulations that eliminate redundant computations and combine complex operations efficiently. Furthermore, an optimized data path is proposed to maximize on-chip data reuse and reduce off-chip memory accesses. An efficient hardware accelerator is also developed for the proposed algorithm. By exploiting the automorphism pattern, the permutation circuit is significantly simplified. Compared with prior hardware accelerators, the proposed design achieves substantial reductions in both computation latency and off-chip memory access while maintaining similar hardware resource requirements. Future work will focus on further optimizing linear transformations for specific applications.
[5]
[6]
[7]
M. Moradi, M. Najafi, Z. Lin, and H. Pan, “Advancing sensor network optimization and data analytics for smart wastewater and stormwater collection systems: An overview”, in Pipelines 2025, pp. 463–472. B. Song, D. Zhao, J. Yan, H. Li, and H. Jiang, “BioDeepHash: Generating consistent templates for secure biometric recognition”, IEEE Trans. on Dependable and Secure Comp., pp. 1–18, 2026. V. V. L. D. Allavarpu, V. S. Naresh, and A. K. Mohan, “Privacy-preserving machine learning techniques based on homomorphic encryption for credit risk analysis”, Electronic Commerce Research, 2026. J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in Proc. of Intl. Conf. on the Theory and Appl. of Cryptol. and Info. Secur., Cham, Switzerland, 2017, pp. 409–437. Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without bootstrapping,” in Proc. of Innov. in Theoret. Comp. Sci. Conf., Cambridge, Massachusetts, 2012, pp. 309–325. S. Halevi, Y. Polyakov, and V. Shoup, “An improved RNS variant of the BFV homomorphic encryption scheme”, in Topics in Cryptology, M. Matsui, Ed., Cham: Springer International Publishing, 2019, pp. 83– 105. I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, “Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE,” in Advances in Cryptology, Cham, Switzeland, 2017, pp. 377–408.
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS , VOL. X, NO. X, FEBRUARY 2026
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20] [21]
X. Zhang, Z. Huai, and K. K. Parhi, “Polynomial multiplication architecture with integrated modular reduction for R-LWE cryptosystems,” Journ. of Sig. Process. Syst., vol. 94, no. 8, pp. 799–809, 2022. S.-H. Liu, C.-Y. Kuo, Y.-N. Mo, and T. Su, “An areaefficient, conflict-free, and configurable architecture for accelerating NTT/INTT,” IEEE Trans. on Very Large Scale Integ. (VLSI) Syst., vol. 32, no. 3, pp. 519–529, 2024. P. Duong-Ngoc, S. Kwon, D. Yoo, and H. Lee, “Areaefficient number theoretic transform architecture for homomorphic encryption,” IEEE Trans. on Circ. and Syst. I, vol. 70, no. 3, pp. 1270–1283, 2023. S.-W. Chiu and K. K. Parhi, “Low-complexity NTT and INTT structures via twiddle shifting”, in IEEE Intl. Midwest Symp. on Circ. and Syst., 2025, pp. 444–448. W. Tan, S. W. Chiu, A. Wang, Y. Lao, and K. K. Parhi, “PaReNTT: Low-latency parallel residue number system and NTT-based long polynomial modular multiplication for homomorphic encryption,” IEEE Trans. on Info. Foren. and Secur., vol. 19, pp. 1646–1659, 2024. S. Akherati, J. Cai, and X. Zhang, “Efficient generalized integer division and modular reduction architectures for homomorphic encryption”, Journ. of Sig. Process. Syst., vol. 97, no. 2, pp. 157–171, 2025. S. Kim, K. Lee, W. Cho, J. H. Cheon, and R. A. Rutenbar, “FPGA-based accelerators of fully pipelined modular multipliers for homomorphic encryption”, in Intl. Conf. on ReConFigurable Comp. and FPGAs, 2019, pp. 1–8. J. H. Cheon, K. Han, A. Kim, M. Kim, and Y. Song, “A full RNS variant of approximate homomorphic encryption,” in Proc. of Select. Areas in Cryptog. Intl. Conf., Springer, 2019, pp. 347–368. J. Feng, Y. Wu, H. Sun, S. Zhang, and D. Liu, “Panther: Practical secure two-party neural network inference”, IEEE Trans. on Inf. Forensics and Sec., vol. 20, pp. 1149–1162, 2025. R. Zhang, Z. Zheng, and W. Bao, “Practical secure inference algorithm for a fine-tuned large language model based on fully homomorphic encryption”, IEEE Trans. on Inf. Forensics and Sec., vol. 21, pp. 17–29, 2026. J. P. Bossuat, C. Mouchet, J. Troncoso Pastoriza, and J. P. Hubaux, “Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys,” in Advances in Cryptology, Cham, Switzerland, 2021, pp. 587–617. C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan, “GAZELLE: A low latency framework for secure neural network inference,” in Proc. of the USENIX Conf. on Secur. Symp., Baltimore, MD, USA, 2018, pp. 1651– 1668. S. Halevi and V. Shoup, “Bootstrapping for HElib”, J. Cryptol., vol. 34, no. 1, 2021. S. Halevi and V. Shoup, “Faster homomorphic linear transformations in HElib”, in Advances in Cryptol-
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]
[33]
[34]
11
ogy, Santa Barbara, CA, USA: Springer-Verlag, 2018, pp. 93–120. S. Bian, D. E. S. Kundi, K. Hirozawa, W. Liu, and T. Sato, “APAS: Application-specific accelerators for RLWE-based homomorphic linear transformations”, IEEE Trans. on Inf. Forensics and Sec., vol. 16, pp. 4663–4678, 2021. Y. Yang, S. R. Kuppannagari, R. Kannan, and V. K. Prasanna, “FPGA accelerator for homomorphic encrypted sparse convolutional neural network inference”, in IEEE Intl. Symp. on Field-Program. Custom Comp. Machines, 2022, pp. 1–9. X. Ren, Z. Chen, Z. Gu, Y. Lu, R. Zhong, W.-J. Lu, J. Zhang, Y. Zhang, H. Wu, X. Zheng, H. Liu, T. Chu, C. Hong, C. Wei, D. Niu, and Y. Xie, “CHAM: A customized homomorphic encryption accelerator for fast matrix-vector product”, in ACM/IEEE Design Automation Conf., 2023, pp. 1–6. Y. Yang, S. R. Kuppannagari, R. Kannan, and V. K. Prasanna, “Bandwidth efficient homomorphic encrypted matrix vector multiplication accelerator on FPGA”, in Intl. Conf. on Field-Program. Tech., 2022, pp. 1–9. Z. Xu, R. Kannan, and V. K. Prasanna, FAME: FPGA acceleration of secure matrix multiplication with homomorphic encryption, 2025. arXiv: 2512 . 15515 [cs.AR]. [Online]. Available: https://arxiv.org/abs/ 2512.15515 H. Chen, W. Dai, M. Kim, and Y. Song, “Efficient homomorphic conversion between (Ring) LWE ciphertexts,” in Proc. of Appli. Cryptog. and Network Secur., Kamakura, Japan, 2021, pp. 460–479. Y. Gao, G. Quan, S. Homsi, et al., “Secure and efficient general matrix multiplication on cloud using homomorphic encryption”, The Journal of Supercomputing, vol. 80, pp. 26 394–26 434, 2024. S. Akherati and X. Zhang, “Improved ciphertext multiplication for RNS-CKKS homomorphic encryption”, in IEEE Work. on Sig. Process. Syst., 2024, pp. 136–140. K. Han and D. Ki, “Better bootstrapping for approximate homomorphic encryption”, in Topics in Cryptology, San Francisco, CA, USA, 2020, pp. 364–390. S. Akherati and X. Zhang, “Multi-input ciphertext multiplication for homomorphic encryption”, IEEE Trans. on Circ. and Syst. I: Regular Papers, pp. 1–12, 2026. S. Halevi and V. Shoup, “Algorithms in HElib”, in Advances in Cryptology, J. A. Garay and R. Gennaro, Eds., Berlin, Heidelberg, 2014, pp. 554–571. R. Agrawal, L. d. Castro, C. Juvekar, A. Chandrakasan, V. Vaikuntanathan, and A. Joshi, “MAD: Memoryaware design techniques for accelerating fully homomorphic encryption”, in IEEE/ACM Intl. Symp. on Microarchitecture, 2023, pp. 685–697. R. Chen and V. K. Prasanna, “Automatic generation of high throughput energy efficient streaming architectures for arbitrary fixed permutations”, in Intl. Conf. on Field Program. Logic and App., 2015, pp. 1–8.