Homomorphic Encryption (HE) promises a world where a cloud server can compute on sensitive data without ever decrypting it. However, when applying HE to modern workloads like Transformer inference or large-scale neural networks, systems hit a massive performance wall.
In plaintext, matrix multiplication is a highly parallelizable sequence of multiply-accumulate operations. In the encrypted domain, it becomes a battle against two hidden bottlenecks: ciphertext slot rotations (a heavy computational tax) and ciphertext sparsity (a severe communication tax).
To make secure inference practical, a major research direction has emerged around compact ciphertext packing. By rethinking how matrices are geometrically mapped into encrypted memory, these techniques minimize internal data movement and eliminate wasted space, transforming the efficiency of encrypted linear algebra.
The Hidden Cost of Encrypted Vector Spaces
To understand why naive encrypted matrix multiplication fails, we must look at how modern HE schemes (such as CKKS or BGV) store data.
These schemes use Single Instruction, Multiple Data (SIMD) structures. A single ciphertext does not just hold one number; it contains a vector of thousands of independent "slots" (e.g., 16,384 slots). We can add or multiply two ciphertexts element-wise in parallel very quickly.
Ciphertext A: [ a1 , a2 , a3 , a4 ]
* * * * (Fast SIMD Multiplication)
Ciphertext B: [ b1 , b2 , b3 , b4 ]
However, matrix multiplication requires computing dot products, which means summing values within the same ciphertext vector. To add a1 to a2, you cannot simply look at the next index. Instead, you must physically shift the vector's slots. This operation is called a slot rotation.
Original: [ a1 , a2 , a3 , a4 ]
Rotated: [ a2 , a3 , a4 , a1 ] (Requires an expensive Key-Switching step)
As Seewoo Lee et al. observe in HETAL: Efficient Privacy-preserving Transfer Learning with Homomorphic Encryption, these slot rotations are frequently a far more significant computational bottleneck than multiplication or addition. Every rotation requires a costly cryptographic maintenance step known as key-switching. If a system naively rotates ciphertexts to calculate dot products, the computational overhead quickly becomes intractable.
Maximizing Density via Advanced Encoding
The second major issue is space utilization. If you place a small matrix row (e.g., size $512$) into a standard $16,384$-slot ciphertext, you leave over 96% of the slots empty. This sparsity means you are encrypting, processing, and transmitting mostly useless padding.
Compact ciphertext packing solves this by carefully arranging matrix elements to maximize data density and align elements for rotation-free operations.
Diagonal and Column-Wise Packing
Instead of encoding matrices row-by-row, researchers utilize alternative geometric layouts. In BOLT: Privacy-Preserving, Accurate and Efficient Inference for Transformers, Qi Pang et al. interpret matrix multiplication as linear combinations of columns, packing them tightly to eliminate empty slots entirely.
Similarly, Qipeng Xie et al. demonstrate in HARMONY: A Privacy-preserving and Sensor-agnostic Tele-monitoring system that diagonal encoding allows for rotation-based data reuse. By layout out matrix diagonals into ciphertext slots, the underlying algebraic structure naturally aligns during multiplication, drastically reducing the total number of required permutations.
Complexification and Coefficient Encoding
To squeeze even more performance out of each slot, researchers exploit the underlying mathematical properties of the encryption schemes:
- Complexification: Because schemes like CKKS natively support complex numbers, Seewoo Lee et al. utilize tiling strategies that pack distinct real data into both the real and imaginary components of a single ciphertext slot. This doubles the data density and cuts down the total number of required rotations.
- Coefficient Encoding: Moving away from slot-based SIMD entirely, Xiangning Wang et al. in LEAF map matrix-vector products directly to the coefficients of the underlying ring polynomials. While converting between formats adds a small overhead, it allows the raw polynomial multiplication mechanics of HE to handle the linear algebra natively.
Reducing Complexity from Cubic to Linear
By combining these packing strategies with clever algorithmic reformulations, the theoretical complexity of encrypted matrix operations can be fundamentally altered.
Naively evaluating an $h \times h$ matrix multiplication requires $O(h^3)$ operations. However, by treating the operation as a unified linear transformation and applying permutation-based adjustments, frameworks can evaluate entire layers simultaneously.
As shown by Guowen Xu et al. in Hercules: Boosting the Performance of Privacy-preserving Federated Learning, this structural shift can reduce the computational complexity of $h \times h$ matrix multiplication from $O(h^3)$ down to $O(h)$.
When combined with ciphertext packing, as explored by Shangyu Xie et al. in Privacy-preserving Cloud-based DNN Inference, these matrix permutations transform standard matrix operations into a clean sequence of simple, component-wise products.
Naive Matrix Mult: O(h³) complexity + massive slot rotations
Packed Linear Trans: O(h) complexity + minimized component-wise steps
Defeating the Communication Bottleneck
While compact packing optimizes computation on the server, large-scale models (like Transformers) often run in a secure two-party computation (2PC) or client-server setup. Here, intermediate matrix operations present a secondary crisis: they naturally generate sparse results filled with padding. Transmitting these sparse ciphertexts over the network creates a massive communication bottleneck.
In Iron: Private Inference on Transformers, Meng Hao et al. introduce compact packing protocols designed specifically for high-dimensional Transformer layers. Their approach preserves algebraic functionality while reducing communication overhead by a factor proportional to the square root of the matrix dimensions compared to traditional row-wise methods.
To handle the sparsity that dynamically emerges during runtime, Wen-jie Lu et al. introduce a technique called "InterLeave" within the BumbleBee framework. Instead of forcing the network to transmit mostly empty padding, the server performs homomorphic operations to compress and reorganize the sparse intermediate coefficients into dense ciphertexts before sending them back to the client.
[Data|Pad|Pad] \
[Data|Pad|Pad] --> Homomorphic Reorganization --> [Data|Data|Data] (Dense)
[Data|Pad|Pad] /
By stripping out the padding entirely in the encrypted domain, the authors demonstrate a reduction in communication bandwidth of over 90%.
Summary
Compact ciphertext packing shifts the focus of homomorphic encryption optimization from low-level cryptographic tuning to high-level data geometry. By aligning data with the native SIMD architecture of HE, avoiding slot rotations, and homomorphically compressing sparse results, these techniques turn the theoretical promise of secure matrix computation into a highly performant reality.
Key Foundational Work
Secure Outsourced Matrix Computation and Application to Neural Networks (2018) — contributed 1 concept elements to this direction.
Secure large-scale genome-wide association studies using homomorphic encryption (2020) — contributed 1 concept elements to this direction.