Fully Homomorphic Encryption (FHE) offers a powerful privacy guarantee: it allows a server to compute functions directly on encrypted data without ever decrypting it. This capability is highly desirable for privacy-preserving neural network inference, where a client wants to leverage a powerful cloud model without revealing sensitive inputs.
However, running deep learning models under FHE is notoriously slow. While basic arithmetic operations like addition and multiplication are relatively straightforward to implement homomorphically, the true bottleneck lies in an unexpected place: moving data within the ciphertext itself. Recent research focuses heavily on mitigating this ciphertext rotation bottleneck to make encrypted inference practical.
The SIMD Packing Dilemma
To understand why data movement is so expensive, we must look at how data is structured in modern FHE schemes (such as BFV or CKKS).
FHE ciphertexts are mathematically represented as large polynomials. To process data efficiently, libraries use Single Instruction, Multiple Data (SIMD) packing. This technique allows thousands of plaintext values (scalars) to be encoded into the individual "slots" of a single ciphertext polynomial. When you perform an addition or multiplication on two ciphertexts, the operation happens simultaneously and element-wise across all slots.
Ciphertext A: [ x1 , x2 , x3 , x4 ]
+ + + +
Ciphertext B: [ y1 , y2 , y3 , y4 ]
= = = =
Result: [x1+y1, x2+y2, x3+y3, x4+y4]
This parallelization is excellent for element-wise operations, but neural networks rarely rely on element-wise arithmetic alone. Linear layers—such as fully connected layers, convolutions, and self-attention mechanisms—fundamentally require cross-slot communication. For example, computing a dot product requires multiplying slots element-wise and then summing the results across the slots of the same ciphertext. Similarly, performing a spatial convolution requires shifting neighboring pixels so they align with the filter weights.
To achieve this cross-slot alignment, FHE schemes rely on an operation called ciphertext rotation (or cyclic shifting).
Why Rotations Dominate Execution Time
In plaintext computing, shifting an array index is virtually free—it is a simple pointer manipulation. In the encrypted domain, however, a rotation is a heavy cryptographic operation.
Rotating slots requires an algebraic evaluation called an automorphism. This process alters the underlying structure of the ciphertext, dramatically increasing its cryptographic noise and requiring a highly complex operation known as "key switching" to restore the ciphertext to a usable state. Key switching involves multiplying the ciphertext by massive evaluation keys, which incurs heavy memory overhead and computational latency.
As a result, ciphertext rotations are orders of magnitude more expensive than homomorphic additions or multiplications. Work by Qian Lou et al. in Falcon: Fast Spectral Inference on Encrypted Data and Ran Ran et al. in SpENCNN demonstrates that ciphertext rotations frequently account for over 90% of the total execution time in encrypted neural network inference. Whether processing convolutional layers (Kejie Huang et al.) or neuro-fuzzy inference systems (Hao Ren 0001 et al.), managing data movement between slots is the primary barrier to real-time performance.
To overcome this bottleneck, researchers have attacked the problem from three main angles: global packing optimization, mathematical domain transformations, and algorithmic refinements.
Strategy 1: Global and Inter-Layer Packing Optimization
Traditional approaches to encrypted deep learning optimize each neural network layer in isolation. However, this creates a compounding problem: the data layout output by a convolutional layer rarely matches the layout expected by the subsequent activation or pooling layer, forcing expensive realignments.
To solve this, the authors of Unlocking Private Computation at Scale: The Acceleration of Homomorphic Encryption developed flexible data-packing libraries designed to prevent rigid realignments after convolutions. Taking this a step further, Qiao Zhang et al. introduced COIN, a framework that performs conjunctive optimization across consecutive layers. By tracking and adjusting the data layout across multiple layers simultaneously, COIN eliminates the need for intermediate rotations entirely, yielding massive speedups on deep architectures like ResNet.
A similar philosophy applies to Transformer architectures. In MOAI: Module-Optimizing Architecture for Non-Interactive Secure Transformer Inference, Linru Zhang et al. proposed a "rotation-free" design. By enforcing consistent data packing strategies throughout the self-attention blocks, they ensure that token vectors naturally align for matrix multiplications without requiring explicit slot shifts.
Strategy 2: Mathematical Domain Transformations
If shifting data in the spatial domain is too expensive, an alternative strategy is to transform the problem into a mathematical domain where shifts are natively cheaper or unnecessary.
In Falcon, Qian Lou et al. leverage the Convolution Theorem by moving encrypted inference into the frequency (spectral) domain. In the spatial domain, a convolution requires sliding a filter across an image, which translates to a massive sequence of ciphertext rotations. In the spectral domain, however, convolution becomes a simple element-wise multiplication. By performing the heavy lifting in the frequency domain, Falcon bypasses spatial rotations entirely.
Spatial Domain: Encrypted Image <-- (Many Rotations + Multiplications) --> Filter
│ │
Fourier Transform Fourier Transform
▼ ▼
Frequency Domain: Spectral Image <-------- (Element-wise Mult Only) -------> Spectral Filter
Another transformation strategy targets matrix-vector multiplications in linear layers. Tianshi Xu et al. introduced PrivCirNet, which compresses neural network weights into block circulant structures. This structural constraint allows the authors to map standard matrix math into encryption-friendly convolutions, drastically reducing the number of encrypted slot manipulations required to align vectors.
Strategy 3: Algorithmic and Architectural Refinements
When rotations cannot be avoided entirely, they can still be mathematically optimized or offloaded.
One approach focuses on optimizing the underlying linear algebra routines within FHE libraries. In Faster Linear Transformations in $\textsf{HElib}$ , Revisited, Hyeongmin Choe et al. re-engineered how linear transformations are handled mathematically. By generalizing the "baby-step/giant-step" algorithm, they reduced the number of expensive automorphisms required per transformation from two to one. Similarly, Han Xuanyuan et al. and Francisco Vargas et al. integrated the Halevi-Shoup matrix-vector product method into intermediate CNN layers, minimizing the growth of cryptographic operations as network layers scale in size.
Other frameworks look at the boundary between different cryptographic primitives. For instance, Yundi Wen et al. optimized the conversion bottlenecks between different ciphertext domains (like LWE and Ring-LWE) during circuit bootstrapping. In multi-party settings, frameworks like FASTLMPI (Yuntian Chen et al.) combine FHE with Secret Sharing to handle fine-grained matrix operations more fluidly. Finally, when the threat model permits, frameworks like SIMC 2.0 (Guowen Xu et al.) eliminate rotation bottlenecks by strategically shifting specific linear computations into the plaintext domain during collaborative protocols.
Conclusion
The evolution of homomorphic encryption from a theoretical curiosity to a practical tool for secure AI hinges on solving data movement. By treating ciphertext rotation not merely as a fixed cost, but as an optimization target, recent literature has successfully minimized this cryptographic bottleneck. Whether through global layout planning, frequency-domain transformations, or tighter algebraic bounds, eliminating rotations is paving the way toward zero-trust, real-time private inference.
Key Foundational Work
Falcon: Fast Spectral Inference on Encrypted Data (2020) — contributed 2 concept elements to this direction.
Faster Linear Transformations in $\textsf{HElib}$ , Revisited (2019) — contributed 1 concept elements to this direction.