Relinearization

Homomorphic multiplication of two ciphertexts (each with 2 polynomials) naturally produces a result with 3 polynomials. Without intervention, subsequent multiplications cause the ciphertext size to grow to 4, then 5, then more polynomials, making storage and further computation exponentially more expensive. Relinearization eliminates this quadratic growth in ciphertext dimension by reducing the product back to a standard 2-element ciphertext.

Relinearization is a specific application of the key-switching primitive. It transforms a degree-2 ciphertext (encrypted under a 'squared' secret key s²) back into a degree-1 ciphertext (encrypted under the original secret key s). This is achieved using a public relinearization key (relin key), which is a masked version of s² encrypted under s, allowing the evaluator to homomorphically convert the ciphertext without accessing the secret key.

Relinearization is not free. The key-switching operation introduces additional noise into the ciphertext, consuming a portion of the finite noise budget. The magnitude of this added noise is proportional to the decomposition base used in the key-switching algorithm. A larger decomposition base reduces computational cost but adds more noise, creating a direct security-efficiency trade-off that must be managed for deep circuits.

In schemes like CKKS and BFV that support ciphertext packing, relinearization is essential for maintaining SIMD parallelism. After multiplying two packed ciphertexts, the 3-element result cannot be used for further packed operations until it is relinearized. Without it, the slot structure becomes corrupted, and subsequent rotations or multiplications would produce meaningless results.

These are distinct but complementary operations in CKKS:

• Relinearization: Reduces ciphertext size (number of polynomials) after multiplication
• Rescaling: Reduces ciphertext scale and modulus to manage precision and noise Both are typically applied after each multiplication: first relinearization to restore size, then rescaling to manage the scale factor. Skipping relinearization while rescaling is possible but leaves a larger ciphertext that costs more to store and operate on.

Relinearization is one of the most expensive operations in HE, often dominating multiplication latency. It requires:

• NTT (Number Theoretic Transform) conversions on the extended ciphertext
• Modular polynomial multiplications with the relin key components
• Digit decomposition of the ciphertext polynomials Hardware acceleration via GPU or FPGA implementations often focuses on optimizing this specific operation to reduce end-to-end encrypted inference time.

A fundamental cryptographic operation that transforms a ciphertext encrypted under one secret key into a ciphertext encrypting the same plaintext under a different secret key. Relinearization is a specific application of key switching that reduces ciphertext size after multiplication.

• Uses public switching keys generated from the original and target secret keys
• Enables rotation of packed ciphertext slots when combined with Galois keys
• Adds a small additive noise term during transformation
• Essential for multi-key HE schemes and threshold decryption

The finite capacity for error accumulation within a lattice-based ciphertext. Each homomorphic operation—especially multiplication—consumes this budget by increasing the embedded noise. Once the noise exceeds a critical threshold, decryption returns corrupted plaintext.

• Fresh ciphertexts start with a noise budget determined by encryption parameters
• Addition consumes negligible noise; multiplication causes quadratic growth
• Bootstrapping refreshes the budget to enable unlimited computation depth
• Monitoring noise budget is critical for circuit design in leveled FHE

A noise management technique that scales down a ciphertext to a smaller modulus, proportionally reducing the absolute noise magnitude. This operation is performed without access to the secret key, making it a lightweight alternative to bootstrapping.

• Reduces both the ciphertext modulus and embedded noise by a scaling factor
• Preserves the encrypted message with some precision loss in approximate schemes
• Used iteratively in leveled FHE to manage noise after each multiplication
• In CKKS, the analogous operation is called rescaling

A technique that encodes multiple plaintext values into a single ciphertext using SIMD (Single Instruction Multiple Data) parallelism. A single homomorphic operation on the packed ciphertext simultaneously applies to all encoded slots.

• Dramatically improves amortized throughput for vector and matrix operations
• Requires Galois keys to rotate slots for cross-slot interactions
• Packing density depends on the ring dimension of the RLWE instance
• Critical for efficient encrypted neural network inference where layers operate on vectors

A cryptographic technique that refreshes a ciphertext by homomorphically evaluating its own decryption circuit. This resets the noise budget to near-fresh levels, enabling unlimited computation depth in fully homomorphic encryption.

• The most computationally expensive operation in FHE
• Programmable bootstrapping (TFHE) also evaluates a lookup table simultaneously
• Eliminates the need to pre-determine circuit depth in leveled FHE
• Modern implementations achieve sub-second latency for single-bit bootstrapping

Public evaluation keys that enable homomorphic rotation of the slots within a packed ciphertext. These keys are essential for implementing operations that require data movement between slots, such as convolution and matrix multiplication.

• Generated from the secret key for specific rotation amounts
• Enable cyclic shifts of the SIMD-packed plaintext vector
• Required for summing across slots or broadcasting values
• A form of key switching specialized for automorphism operations