Minimizing Ciphertext Rotations for Secure Neural Inference

This direction is merged into another direction: homomorphic encryption overhead, compact ciphertext packing. Its last version stays readable and citable here.

Version 1 of 176 papers117 conceptsfrozen 2026-10-04

Fully Homomorphic Encryption (FHE) is often called the "holy grail" of privacy-preserving computation because it allows a server to process data without ever seeing it in plaintext. However, running modern neural networks—especially Transformers—under FHE introduces a massive performance penalty. While additions and multiplications are relatively efficient, the primary bottleneck is the ciphertext rotation.

In FHE schemes like CKKS or BFV, data is packed into "slots" within a single ciphertext (a large polynomial). To perform operations like a dot product or a convolution, the system must shift these slots so that the correct values align for summation. These shifts, known as rotations, can account for over 90% of total execution time Ran Ran. Recent research focuses on "rotation-aware" architectures that minimize these shifts through clever data packing, algorithmic decomposition, and global layout optimization.

The Rotation Tax and Data Packing

The fundamental challenge of FHE is that it treats data as a one-dimensional vector of slots, while neural networks operate on high-dimensional tensors. A naive mapping of a matrix to a ciphertext requires a rotation for almost every element-wise alignment.

To mitigate this, researchers have moved toward specialized packing strategies. For example, Andrey Kim proposed multi-dimensional packing, which treats the ciphertext as a tensor rather than a flat vector, allowing for more "natural" matrix operations. In the context of CNNs, Minsik Kang introduced Channel-By-Channel (CBC) packing, which bundles the same channel from multiple images into one ciphertext. This ensures that the sliding window of a convolution aligns across the batch, reducing the number of unique rotation keys the server needs to store and communicate.

Algorithmic Efficiency: Baby-Step Giant-Step

Even with good packing, large matrix-vector products (the core of Transformer layers) still require many rotations. A breakthrough in this area is the application of the Baby-Step Giant-Step (BSGS) algorithm to homomorphic rotations.

Instead of rotating a ciphertext $N$ times to sum $N$ elements, BSGS decomposes the process into two stages: a set of "baby" rotations (small shifts) and "giant" rotations (large shifts). This reduces the computational complexity from $O(N)$ to $O(\sqrt{N})$. Linhan Yang and Wangchen Dai utilized a "double-BSGS" approach in the ARION framework, which optimizes rotations across the entire triple-matrix sequence of an attention mechanism, reducing rotations by over 80%.

Rotation-Free Architecture and Global Alignment

The most recent frontier is the design of "rotation-free" or "module-optimized" architectures. Rather than optimizing a single layer, frameworks like MOAI, developed by Xiangning Wang and Zhicong Huang, align data layouts across sequential operations.

The intuition is simple: if the output of a linear layer is already in the exact format required by the following Softmax or LayerNorm, no reformatting (and thus no rotation) is needed between modules. By ensuring that values intended for summation occupy identical slot positions across multiple ciphertexts, complex non-linear functions can be executed using only element-wise additions. This "plug-and-play" alignment allows for significant speedups without requiring the model to be retrained.

Trading Memory for Latency

When computation is the bottleneck, memory can sometimes be used as a lever. Seungwan Hong and colleagues demonstrated that data duplication—encrypting redundant copies of the input in different shifted positions—can eliminate the need for rotations during the inference phase. While this increases the initial encryption time and memory footprint, it dramatically lowers the latency of the actual computation, which is critical for real-time applications like tumor classification or biometric authentication.

Because the "optimal" layout depends heavily on the specific network architecture (e.g., the ratio of input to output dimensions), manual optimization is becoming impractical. Compilers like CHET and Rotom have emerged to automate this process. Edward Chen and Wenting Zheng showed that automated search heuristics can identify non-obvious data arrangements—such as using cyclic rotations to perform axis swaps—that outperform hand-tuned protocols by up to 4x.

By treating the ciphertext layout as a first-class optimization target, these researchers are transforming FHE from a theoretical curiosity into a viable backend for private AI.

Papers in this version

Showing 60 of 76 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_minimizing_ciphertext_rotations_for_secu_ae8d8877,
  title = {Minimizing Ciphertext Rotations for Secure Neural Inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimizing-ciphertext-rotations-for-secure-neural-inference/rdr_ae8d887765d5427d9049091f4f0c0bdf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_minimizing_ciphertext_rotations_for_secu_ae8d8877_v1,
  title = {Minimizing Ciphertext Rotations for Secure Neural Inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimizing-ciphertext-rotations-for-secure-neural-inference/rdr_ae8d887765d5427d9049091f4f0c0bdf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}