Homomorphic Encryption (HE) promises a world where cloud servers can compute on sensitive data without ever decrypting it. However, evaluating a single addition or multiplication on an encrypted scalar is notoriously slow.
The root of this inefficiency lies in a mismatch between the scalar data we want to process and the underlying mathematics of lattice-based cryptography. Modern HE schemes (such as BGV, BFV, and CKKS) do not encrypt numbers as individual scalars. Instead, they encrypt data into massive, high-degree polynomials—often containing $8,192$ to $16,384$ coefficients.
If you encrypt a single number into a polynomial of degree 16,384, you pay the full computational price of high-dimensional polynomial arithmetic while utilizing only a fraction of its capacity. The rest of the polynomial is effectively wasted. To make homomorphic encryption practical, we must treat these large cryptographic structures not as single values, but as parallel processing hardware.
The Mechanics of SIMD Slots
To eliminate this waste, researchers exploit a mathematical property of polynomial rings: the Chinese Remainder Theorem (CRT) or canonical embedding maps. These algebraic tools allow the massive plaintext polynomial space to be factored into thousands of independent, non-interfering "slots."
Unpacked: [ Scalar Value ] [ Empty ] [ Empty ] ... [ Empty ] --> Wasted Capacity
Packed: [ Value 1 ] [ Value 2 ] [ Value 3 ] ... [ Value N ] --> Full SIMD Utilization
When you pack a vector of plaintexts into these slots, any homomorphic addition or multiplication performed on the ciphertext acts on all slots simultaneously. This creates a native Single Instruction, Multiple Data (SIMD) architecture inside the encrypted domain.
As shown early on by Tingjian Ge et al., packing multiple smaller integers into a single cryptographic block allows a server to process multiple values using a single modular operation. The core intuition here is amortization: the cryptographic latency of a homomorphic operation remains identical whether you are processing 1 slot or 16,384 slots. By maximizing slot density, the high fixed cost of HE is divided across thousands of data points, bringing the per-operation overhead down to practical levels.
The Rotation Tax and Data Alignment
While SIMD packing provides massive parallel throughput, it introduces a fundamental constraint: slots are structurally isolated. You can add or multiply two packed ciphertexts element-wise, but you cannot natively perform cross-slot operations (such as summing all elements within a single vector or multiplying a row by a column).
To move data between slots, you must perform a ciphertext rotation (an algebraic automorphism). Rotations shift the values within the slots cyclically:
Initial: [ A ] [ B ] [ C ] [ D ]
Rotate(1): [ D ] [ A ] [ B ] [ C ]
The catch is that rotations are computationally expensive—often orders of magnitude slower than simple homomorphic additions. This reality shifts the core challenge of secure system design: the primary bottleneck is no longer minimizing arithmetic operations, but optimizing the spatial layout of data within the slots to minimize rotations.
Application-Specific Packing Layouts
Because data layout dictates performance, different computational domains require distinct packing strategies to keep the "rotation tax" as low as possible.
Batching Across Independent Inputs
The simplest way to avoid rotations is to pack data along an axis that never requires cross-slot interaction. In the landmark CryptoNets framework, Ran Gilad-Bachrach et al. demonstrated high-throughput neural network inference by packing independent image samples across the mini-batch dimension.
If you have 8,192 images, slot $i$ of every ciphertext corresponds to image $i$. Because a neural network applies the exact same operations to every independent image, the data never needs to cross slots. This layout completely avoids the rotation tax, making it ideal for high-volume cloud services or batch inference on edge servers, as explored by Kejie Huang et al..
Matrix and Tensor Layouts
For single-inference tasks or model training, data must interact across dimensions (e.g., matrix-vector multiplications in linear layers). In these scenarios, researchers must design explicit matrix-packing structures.
For instance, Andrey Kim et al. introduced a row-by-row matrix-packing technique to align datasets for efficient gradient computation in logistic regression, utilizing native rotations to handle vector alignments.
For deep convolutional neural networks, where sliding filters create complex data dependencies, Eunsang Lee et al. proposed multiplexed parallel convolutions. This strategy packs multiple image channels into a single ciphertext to enable simultaneous convolution and stride operations, drastically reducing the frequency of expensive outer-rotation operations.
Graph and 2D Structures
Irregular data structures like graphs present the steepest challenge because node connections vary wildly. To handle this, Ran Ran et al. developed Penguin, a framework for Graph Convolutional Network (GCN) inference.
Instead of treating the graph as a flat vector, the authors partitioned nodes into blocks and interleaved features using a balanced 2D ciphertext packing strategy. By optimizing the ratio of nodes to features within the slots, they ensured that adjacency matrix multiplications could be executed with minimal slot-to-slot data movement.
Summary
SIMD ciphertext packing transforms homomorphic encryption from a theoretical curiosity into a viable parallel processing engine. By mapping vectors into the native polynomial slots of lattice cryptography, the immense latency of HE operations is amortized across thousands of data points. The art of modern HE optimization lies in data alignment: structuring plaintexts so that the natural flow of computation matches the rigid boundaries of the cryptographic slots, minimizing the need for costly rotations.