💻 computer science

Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator

This paper presents a triple-hoisted baby-step giant-step algorithm and a corresponding memory-optimized FPGA hardware accelerator that significantly reduce ciphertext rotations, off-chip memory access, and computational latency for linear transformations in CKKS homomorphic encryption.

Original authors: Sajjad Akherati, Xinmiao Zhang

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sajjad Akherati, Xinmiao Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a secret agent trying to solve a complex puzzle, but you are only allowed to work with the puzzle pieces while they are locked inside a heavy, unbreakable safe. You can't open the safe to see the pieces, yet you still need to rearrange them to solve the puzzle. This is the challenge of Homomorphic Encryption (HE): performing calculations on data that remains encrypted the entire time.

This paper presents a new, super-efficient way to solve a specific type of puzzle called a Linear Transformation (a math operation used heavily in Artificial Intelligence and neural networks) while the data is still locked in the safe.

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "Heavy Lifting" of Moving Data

In the world of encrypted data, moving a piece of information from one spot to another inside the safe is incredibly expensive. It's like trying to move a grand piano up a flight of stairs; it takes a lot of time, energy, and special equipment (called "rotation keys").

The Old Way: To solve the puzzle, previous methods had to move the piano up the stairs thousands of times. This created a massive traffic jam, slowing everything down and requiring a huge warehouse (memory) to store all the keys and intermediate steps.
The Bottleneck: The biggest delay wasn't actually doing the math; it was constantly running back and forth to the "warehouse" (off-chip memory) to grab keys and data. This is like a chef running to the grocery store for every single pinch of salt.

2. The Solution: The "Triple-Hoisted" Elevator System

The authors propose a new algorithm called Triple-Hoisted Baby-Step Giant-Step (TH-BSGS).

The "Baby-Step Giant-Step" Concept: Imagine you need to walk 100 miles. Instead of taking 100 tiny steps, you take 10 "giant" steps, and for each giant step, you take 10 "baby" steps. This reduces the total number of times you have to stop and check your map.
The "Triple-Hoisting" Innovation: Previous versions of this method had two layers of these steps. The authors realized they could break the "baby steps" down even further into a third layer.
- The Analogy: Think of "hoisting" as using a crane to lift heavy boxes. In the old method, you had to stop and re-arrange the boxes every time you lifted a layer. The new "Triple-Hoisted" method sets up a system where you can lift three layers of boxes at once without stopping to re-arrange them. You do the heavy lifting once, and the math flows smoothly.
- The Result: This drastically reduces the number of times you have to "move the piano" (perform ciphertext rotations).

3. The Hardware: A Custom "Assembly Line"

Even with a better algorithm, the hardware needs to be built to match. The authors designed a custom FPGA accelerator (a specialized computer chip).

The "Permutation Circuit" Trick: A major part of the process involves shuffling data around (like rearranging cards in a deck). Usually, this requires a lot of temporary storage space (scratchpads) and takes a long time.
- The Innovation: The authors discovered a specific pattern in how the data shuffles. Instead of using a messy, general-purpose shuffling machine, they built a custom conveyor belt that follows this exact pattern.
- The Benefit: This custom belt is twice as fast and requires half the space of previous designs because it doesn't need to stop and store data in temporary buffers.

4. The Memory Optimization: The "Just-in-Time" Kitchen

The paper also redesigned the data path to minimize trips to the "grocery store" (off-chip memory).

The Strategy: They broke the calculation into six distinct phases. In each phase, they load exactly what is needed, do all the work with that data while it's sitting on the counter (on-chip memory), and only then move to the next phase.
The Result: This prevents the system from constantly fetching data. Compared to the best previous designs, this approach reduced the amount of data fetched from the external warehouse by 2.9 to 4.2 times.

The Bottom Line

The authors tested their new system on a high-end chip (Xilinx Virtex UltraScale+). Compared to the best existing hardware accelerators for this task:

Speed: They made the calculation 5.8 times faster (in terms of pure computation time).
Efficiency: They reduced the need to fetch data from external memory by 2.9 times.
Cost: They achieved this without needing significantly more hardware resources (chips and memory) than the previous best designs.

In short, they found a smarter way to organize the work and built a specialized tool to do it, turning a slow, traffic-jammed process into a streamlined, high-speed operation.

Technical Summary: Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator

Problem Statement
Homomorphic Encryption (HE), particularly the CKKS scheme, enables privacy-preserving computations on encrypted data, which is critical for applications like medical diagnosis, financial analysis, and genome sequencing. A fundamental operation in HE-based neural networks and transformers is the Linear Transformation (HE-LT). While the diagonal method allows HE-LT by packing matrix diagonals into polynomials, it requires a prohibitive number of ciphertext rotations for high-dimensional matrices. These rotations involve complex automorphism and key-switching operations, leading to significant computational overhead and massive off-chip memory access. Existing hardware accelerators, even those utilizing Baby-Step Giant-Step (BSGS) decomposition and double-hoisting techniques, still suffer from substantial latency and memory bandwidth bottlenecks, often requiring hundreds of gigabytes of off-chip data transfer for typical parameter sets.

Methodology
The paper proposes a comprehensive solution addressing both algorithmic complexity and hardware data flow:

Triple-Hoisted BSGS (TH-BSGS) Algorithm:
The authors extend the existing double-hoisted BSGS algorithm by further decomposing the "baby step" into two layers, creating a three-layer structure ( $n = n'_1 n'_2 n'_3$ ).
- Triple Hoisting: The technique is applied across all three layers of rotations. By reordering computations and applying inverse automorphisms to switching keys, the algorithm ensures that the Decompose operation (a costly key-switching step) is performed only once for all inner rotations in a layer.
- Delayed ModDown: Similar to previous hoisting methods, the ModDown operations are delayed and combined. In the proposed design, ModDown is applied only to accumulated sums rather than intermediate products, significantly reducing the number of required modular operations.
- Trade-off Flexibility: By tuning the decomposition factors $n'_1, n'_2, n'_3$ , the algorithm allows for flexible trade-offs between the number of required switching keys (memory) and computational complexity.
Memory-Optimized Data Path:
To address the latency caused by off-chip memory access, the TH-BSGS algorithm is partitioned into six distinct phases.
- Phase Partitioning: The algorithm is restructured so that data is read from off-chip memory, processed with intermediate results stored and reused on-chip, and written back only at the end of each phase.
- Data Reuse: The design maximizes on-chip memory reuse by carefully scheduling the loading of switching keys and polynomial limbs. For instance, in the middle layers, switching keys are loaded into on-chip memory and reused across multiple iterations to minimize traffic.
- Parallelism Tuning: Six parallelism parameters ( $m_1$ through $m_6$ ) are introduced to balance the processing of switching keys, polynomial limbs, and ciphertexts, ensuring the design fits within the constraints of FPGA on-chip memory (e.g., 43 MB on Xilinx U280).
Hardware Accelerator Architecture:
An efficient FPGA-based accelerator is designed to implement the proposed algorithm.
- Optimized Permutation Circuit: A novel permutation circuit is introduced to implement the automorphism $\phi_r$ . By exploiting the specific properties of the automorphism in the NTT domain and the bit-reversed storage order of coefficients, the design reduces the number of multiplexers by half compared to prior art and eliminates the need for scratchpad memory buffers. This halves the latency of the permutation operation.
- Modular Components: The architecture includes a Processing Element (PE) array supporting NTT, INTT, and coefficient-wise operations; a Tree Adder (TA) array for summations; and a Permutation Circuit (PC) array.

Key Contributions

Algorithmic Innovation: The proposal of the Triple-Hoisted BSGS algorithm, which decomposes the baby step further to reduce the number of ciphertext rotations and Decompose operations compared to the double-hoisted approach.
Data Path Optimization: A phase-based memory optimization strategy that drastically reduces off-chip memory traffic by maximizing on-chip data reuse, specifically tailored to the reordered computations of the TH-BSGS algorithm.
Hardware Efficiency: The development of a hardware accelerator featuring a simplified permutation circuit that reduces automorphism latency by 50% and eliminates extra memory buffering.

Experimental Results
The design was synthesized on Xilinx Virtex UltraScale+ (U280) devices and evaluated against state-of-the-art hardware accelerators (including FAME, CHAM, and designs from [25]) under three different HE parameter sets (Set-A, Set-B, Set-C) supporting 128-bit security.

Off-Chip Memory Access: The proposed design reduces off-chip memory access by 2.9× to 4.2× compared to the best prior design (FAME) under the same parameter settings. Compared to the diagonal method, improvements reach up to 10.6× in memory access reduction.
Computational Latency: The proposed accelerator achieves a 2.9× to 10.6× reduction in computational latency compared to prior hardware accelerators.
Resource Utilization: The design maintains hardware resource requirements (LUTs, FFs, DSPs, BRAMs) comparable to or slightly better than existing solutions, despite the significant performance gains.
Algorithmic Comparison: While the TH-BSGS algorithm reduces the memory requirement for switching keys by approximately 3.65× compared to the double-hoisted BSGS (DH-BSGS) algorithm, the overall computational complexity remains similar to DH-BSGS and BSGS because polynomial multiplications dominate the total complexity.

Significance
The paper claims that the proposed TH-BSGS algorithm and its associated hardware accelerator represent a significant advancement in the efficiency of HE-LT. By simultaneously addressing the algorithmic overhead of key switching and the hardware bottleneck of off-chip memory access, the design enables faster and more scalable privacy-preserving linear transformations. The reduction in off-chip memory traffic is particularly critical, as data transfers constitute the majority of the latency in HE-LT operations. The work demonstrates that further decomposition of the baby step, combined with rigorous data path optimization and specialized hardware, can yield substantial performance improvements without increasing hardware resource costs. Future work is noted to focus on further optimizing linear transformations for specific applications.

1. The Problem: The "Heavy Lifting" of Moving Data

2. The Solution: The "Triple-Hoisted" Elevator System

3. The Hardware: A Custom "Assembly Line"

4. The Memory Optimization: The "Just-in-Time" Kitchen

The Bottom Line

More like this