Relinearization

In schemes like BFV and CKKS, a ciphertext is typically a pair of polynomials. A homomorphic multiplication of two ciphertexts produces a result with three polynomial components instead of two. Without intervention, subsequent multiplications cause the size to grow exponentially, making storage and further computation impractical. Relinearization reduces this triple back to a canonical two-component ciphertext.

Relinearization is a specific application of key-switching. It requires the public key holder to provide a special evaluation key (often called a relinearization key). This key is essentially an encryption of specific powers of the secret key under the secret key itself. The operation homomorphically evaluates a decryption-like circuit to transform the extended (degree-2) ciphertext back into a linear (degree-1) ciphertext without decrypting the data.

While essential for size control, relinearization is not computationally free. It consumes a portion of the noise budget because it involves multiplying the ciphertext components by the relinearization key and adding them together. The operation adds a fixed amount of noise, which must be accounted for in the total budget alongside the noise introduced by the multiplication itself.

To manage noise growth during the key-switching step, the ciphertext is often decomposed into a smaller base (a gadget decomposition). Instead of multiplying by a large integer directly, the operation breaks the integer into digits of a smaller radix. This trades off a slight increase in computational cost for a significant reduction in the noise added during relinearization, keeping the overall noise budget viable for deeper circuits.

In the CKKS scheme, which operates on approximate numbers, relinearization is tightly coupled with rescaling. After a multiplication, the ciphertext modulus is too large. The operation first reduces the three-component ciphertext to two components via key-switching, and then applies rescaling to truncate the least significant bits and manage the scale factor. This combined step ensures the ciphertext maintains a constant size and stable precision.

The size of the relinearization key is substantial, often dominating the public key material. The security of the operation relies on the Ring Learning With Errors (RLWE) assumption, ensuring the evaluation key hides the secret key. Optimized implementations often use Number Theoretic Transform (NTT) to accelerate the polynomial multiplications involved in the key-switching procedure.

The foundational cryptographic building block that relinearization is built upon. Key switching transforms a ciphertext decryptable under one secret key into a ciphertext decryptable under a different secret key. In the context of relinearization, the target key is the original secret key itself, but the input ciphertext is treated as if it were encrypted under a squared key (s^2). This is achieved by providing a public evaluation key (relinearization key), which is an encryption of the old key under the new key.

Every homomorphic operation, especially multiplication, injects cryptographic noise into the ciphertext. If the noise exceeds a critical threshold, decryption fails. Relinearization itself adds a small, controlled amount of noise. However, it is essential because it prevents the noise from growing quadratically in subsequent multiplications by keeping the ciphertext size small. Without it, the noise would compound much faster, exhausting the noise budget prematurely and forcing a costly bootstrapping operation sooner.

A primary performance bottleneck in homomorphic encryption. A fresh ciphertext in schemes like BGV or BFV is typically a pair of polynomials. After a multiplication, the result is a triple of polynomials. Without relinearization, another multiplication would produce a quintuple, leading to exponential growth. Relinearization reduces the size back to a pair, maintaining a constant ciphertext expansion factor. This is crucial for controlling both memory overhead and computational complexity in deep circuits.

A complementary noise management technique often used alongside relinearization. While relinearization reduces the ciphertext size, modulus switching reduces the ciphertext noise magnitude. It works by scaling down the ciphertext modulus q to a smaller modulus q', which proportionally scales down the absolute noise. In many leveled homomorphic encryption schemes, a multiplication is immediately followed by both relinearization (to reduce size) and modulus switching (to reset the noise scale), together enabling the next level of computation.

The process by which the data owner creates the auxiliary keys required for relinearization. The owner encrypts a representation of their own secret key s under a secondary key, often using a base decomposition to control noise growth. This produces the relinearization key, which is sent to the evaluating server as a public parameter. The security of the scheme relies on the fact that this key allows transformation of ciphertexts without revealing the underlying secret key s itself.

The maximum number of sequential multiplications a circuit can support before decryption becomes impossible. Relinearization is the mechanism that makes deep circuits practical. By resetting the ciphertext size after each multiplication, it ensures that the computational cost per multiplication remains linear rather than quadratic in the circuit depth. This directly increases the achievable multiplicative depth of a leveled homomorphic encryption scheme without requiring bootstrapping.