Modulus Switching

The core mechanism of modulus switching relies on scaling invariance. By switching from a larger modulus ( q ) to a smaller modulus ( q' ), the absolute magnitude of the inherent cryptographic noise is reduced by approximately the factor ( q'/q ). This is mathematically equivalent to rounding the ciphertext to a lower precision, which truncates the least significant bits where the noise resides, thereby resetting the noise budget without decrypting the data.

Unlike bootstrapping, which homomorphically evaluates the decryption circuit to refresh noise, modulus switching is a purely algebraic operation. It is significantly less computationally intensive, often requiring only simple modular arithmetic. However, it comes with a strict limitation: it permanently reduces the ciphertext modulus, which decreases the total computational capacity remaining. It is typically used in leveled homomorphic encryption schemes to manage noise after every multiplication gate.

In Leveled Fully Homomorphic Encryption, the circuit depth must be known in advance. Modulus switching is the primary tool for navigating this depth. The scheme initializes with a chain of moduli ( q_0 > q_1 > ... > q_L ). After each multiplicative layer, a modulus switch moves the ciphertext down the chain, reducing the noise to a baseline level. This allows the evaluation of circuits with a predetermined multiplicative depth without the massive overhead of bootstrapping.

In the CKKS scheme, which handles approximate arithmetic, the modulus switching operation is called rescaling. It serves a dual purpose: it manages noise and divides the ciphertext by a scaling factor ( \Delta ) to maintain a stable scale. After a multiplication of two scaled ciphertexts (scale ( \Delta^2 )), rescaling divides by ( \Delta ) and reduces the modulus, effectively truncating the noisy lower bits and keeping the plaintext precision consistent throughout the computation.

Modulus switching is often paired with relinearization after a homomorphic multiplication. Multiplication increases both the noise and the ciphertext size (from 2 to 3 ring elements). Relinearization first reduces the size back to 2 elements using a key-switching procedure. Modulus switching then reduces the noise of this compact ciphertext. Performing modulus switching before relinearization is technically possible but generally avoided as it complicates the key-switching key generation.

The security of lattice-based schemes relies on the hardness of Ring-LWE at a specific modulus-to-noise ratio. As modulus switching reduces the modulus ( q ), the ratio changes. If the modulus becomes too small relative to the noise floor, the scheme becomes insecure. Therefore, the modulus chain must be carefully parameterized to ensure that even the smallest modulus ( q_L ) maintains the required security level, typically 128-bit or higher, against known lattice reduction attacks.