Rescaling

Rescaling divides the ciphertext by a scaling factor (Δ) after multiplication to restore the scale to its original level. In CKKS, a ciphertext encrypts a message m as m · Δ + e, where e is noise. Multiplying two ciphertexts yields a product with scale Δ² and quadratic noise growth. Rescaling divides by Δ, reducing the scale back to Δ and proportionally reducing the absolute noise. This operation consumes one level from the modulus chain, making it a limited resource that must be budgeted during circuit design.

CKKS operates on a modulus chain—a hierarchy of decreasing moduli q₀ > q₁ > ... > qₗ. Each rescaling operation drops the ciphertext to the next smaller modulus, consuming one level. The initial modulus q₀ determines the multiplicative depth of the computation. A circuit requiring L sequential multiplications needs a modulus chain of at least L levels. Exhausting all levels leaves the ciphertext at the lowest modulus, where no further operations are possible without bootstrapping to refresh the chain.

Rescaling is the encrypted equivalent of fixed-point truncation. In plaintext fixed-point arithmetic, multiplying two k-bit numbers produces a 2k-bit result that must be truncated back to k bits to prevent unbounded growth. Similarly, CKKS multiplication doubles the effective precision, and rescaling truncates it back. This introduces a small approximation error—acceptable because CKKS is designed for approximate arithmetic on real numbers, making it ideal for machine learning workloads where exact integer precision is unnecessary.

After multiplication, two operations are typically required: relinearization to reduce ciphertext size, and rescaling to manage scale and noise. The order matters. Rescaling is performed first to bring the scale back to Δ, followed by relinearization to collapse the three-component ciphertext back to two components. Performing relinearization before rescaling would operate on a ciphertext with scale Δ², requiring different key-switching parameters. The standard sequence is:

• Multiply → Rescale → Relinearize

When implementing encrypted inference for neural networks, each homomorphic multiplication (e.g., fully-connected layer, convolution) consumes one level via rescaling. A network with 10 linear layers requires at least 10 levels in the modulus chain. Activation functions like ReLU must be approximated by low-degree polynomials, each multiplication within the polynomial also consuming levels. This forces a trade-off between network depth, polynomial accuracy, and computational cost. Typical CKKS parameters for deep networks use a modulus chain of 16–30 levels.

While both operations reduce the ciphertext modulus, they serve distinct purposes:

• Rescaling: Divides by the scaling factor Δ after multiplication, maintaining a consistent scale. It is an integral part of CKKS arithmetic.
• Modulus Switching: A general noise management technique that scales down the modulus to reduce absolute noise without a corresponding multiplication. It can be used between operations to extend the noise budget. Rescaling is a specialized form of modulus switching that simultaneously normalizes the scale, making it essential for CKKS's approximate arithmetic model.

The finite amount of cryptographic noise a ciphertext can tolerate before decryption becomes corrupted. Each homomorphic operation, especially multiplication, consumes this budget.

• Consumption: Addition consumes noise linearly; multiplication causes it to grow quadratically.
• Management: Rescaling is the primary tool for cutting down noise after multiplication to prevent it from exceeding the total modulus.
• Analogy: Think of the noise budget as the remaining depth capacity of a circuit before the signal is lost.

A variant of HE that supports circuits of a pre-determined multiplicative depth without bootstrapping. Rescaling is the mechanism that enforces this depth limit.

• Parameterization: The initial modulus chain length defines the maximum number of rescalings (and thus multiplications).
• Constraint: The circuit depth must be known at encryption time.
• Advantage: Avoids the massive computational overhead of bootstrapping for shallow circuits, making it the standard mode for many ML inference tasks.

The technique of replacing non-linear activation functions (ReLU, sigmoid) with low-degree polynomials to enable their evaluation in CKKS. Rescaling is critical here to manage the scale growth from repeated polynomial multiplications.

• Example: Approximating ReLU with a degree-3 polynomial requires 2 multiplications, consuming 2 rescalings.
• Trade-off: Higher-degree approximations improve accuracy but consume more depth.
• Interaction: The choice of polynomial directly impacts the rescaling budget required for a neural network layer.