SIMD Packing

SIMD packing leverages the Chinese Remainder Theorem (CRT) to decompose the plaintext modulus into a product of smaller, coprime factors. Each plaintext slot corresponds to an independent computation modulo one of these factors. This allows a single ciphertext to hold thousands of distinct values, such as the pixels of an image or the rows of a database column, enabling true data-parallel execution.

Homomorphic addition and multiplication operate component-wise on the packed slots simultaneously.

• Addition: ctxt_1 + ctxt_2 adds the values in corresponding slots without cross-talk.
• Multiplication: ctxt_1 * ctxt_2 multiplies values in corresponding slots. This means a single homomorphic multiplication can perform thousands of scalar multiplications at once, drastically reducing the amortized cost per operation.

To compute functions that require data movement between slots (like summing all elements or performing a convolution), schemes support Galois automorphisms.

• Rotation: Cyclically shifts all slot values left or right by a fixed offset.
• Permutation: Applies a more complex rearrangement of slots using a key-switching operation. These operations are essential for implementing linear algebra routines like matrix-vector multiplication on packed ciphertexts.

Without packing, encrypting a single integer incurs a massive ciphertext expansion (often 10,000x or more). SIMD packing amortizes this overhead across thousands of plaintext slots.

• Throughput: A single operation on a packed ciphertext processes an entire vector.
• Efficiency: The amortized per-element computational cost and memory footprint drop by a factor equal to the number of slots, making complex private inference economically viable.

In the CKKS scheme, SIMD packing encodes a vector of complex or real numbers into a single polynomial. The rescaling operation, which manages scale after multiplication, applies uniformly to all slots. This makes CKKS the natural choice for privacy-preserving neural networks where layers operate on high-dimensional floating-point vectors, as the entire layer's computation can be vectorized.

Not all slots need to be active. By multiplying a packed ciphertext by a plaintext vector of zeros and ones, specific slots can be masked out or isolated.

• Zeroing: Multiply by a mask with 0 in unwanted slots.
• Extraction: Combine rotations and masking to extract a single slot. This allows conditional logic and branching to be simulated within the SIMD paradigm without decrypting.

The CKKS-specific noise management operation that maintains a stable scale factor after homomorphic multiplication. When two packed ciphertexts are multiplied, the scale factor squares. Rescaling divides the ciphertext by the original scale, truncating the least significant bits to control noise growth.

• Analogy: Analogous to truncating floating-point precision after a multiplication.
• Critical for SIMD: Without rescaling, the noise in packed ciphertexts would grow exponentially, corrupting all vector elements simultaneously.

The finite cryptographic resource consumed by every homomorphic operation. Each addition and multiplication on a packed ciphertext introduces a small amount of random noise into the underlying lattice structure. When the noise budget is exhausted, decryption fails.

• SIMD Impact: All values in a packed vector share the same noise budget. A single noisy element does not corrupt others, but the entire ciphertext becomes undecryptable when the budget is depleted.
• Management: Bootstrapping or modulus switching refreshes this budget.

A computationally intensive procedure that homomorphically evaluates the decryption circuit on a ciphertext to reset its noise budget. For SIMD-packed ciphertexts, bootstrapping refreshes the noise for all vector elements simultaneously.

• Programmable Bootstrapping: In the TFHE scheme, this operation can also evaluate an arbitrary lookup table, enabling non-polynomial functions like ReLU on packed data.
• Throughput Trade-off: While bootstrapping enables unlimited depth, it remains the dominant bottleneck in FHE latency.

A key-switching technique that reduces the size of a ciphertext after a homomorphic multiplication. Multiplying two ciphertexts produces a result with three polynomial components instead of two, causing quadratic growth in ciphertext dimensions.

• SIMD Relevance: Without relinearization, subsequent multiplications on packed vectors would cause ciphertext sizes to explode, making further operations computationally prohibitive.
• Mechanism: Uses a public evaluation key to transform the extended ciphertext back to a standard two-component form.

The mathematical technique of replacing non-linear activation functions with low-degree polynomials to enable their evaluation in FHE. Since homomorphic encryption natively supports only addition and multiplication, functions like sigmoid, tanh, or ReLU must be approximated.

• SIMD Application: A single polynomial is evaluated on all packed values simultaneously.
• Example: ReLU is often approximated by a degree-2 or degree-4 polynomial like 0.5x + 0.5x² over a bounded domain.