Multiplication, key switching, and rescale

Ciphertext multiplication forms a component convolution, key switching changes the secret-key relation, and rescale computes a rounded quotient over a complete Q depth group. Their implementations share RNS basis-conversion and NTT algorithms while preserving active rows, per-value scale, and residue representation.

Numerical implementation path

backend/ckks/arithmetic.py implements whole two-component convolution. backend/ckks/key_switch.py composes key-switch corrections, and backend/ckks/rotation/ owns Galois selection and hoisted execution. Numerical ModUp, key products, ModDown, and prime-group rescale live under backend/rns/; transform execution lives under backend/ntt/. Eager supplies direct operation metadata, while manual and callable Compile use represented Program state. Both consume these numerical implementations.

Plaintext multiplication

Conceptual data flow:

The output scale is multiplied, but depth is unchanged until a rescale. multiply_plaintext does not perform hidden forward or inverse NTTs; the caller places transitions around a multiplication region directly or through selected Compile passes. Compatible products may be added in NTT form and converted to coefficient-domain standard residues once before rescale. Prepared plaintext reuse must match depth, scale, basis, prime IDs, domain, and residue representation exactly.

Ciphertext multiplication

For two components $(c_{0}, c_{1})$ and $(d_{0}, d_{1})$ :

(e_{0}, e_{1}, e_{2}) = (c_{0} d_{0}, c_{0} d_{1} + c_{1} d_{0}, c_{1} d_{1}) .

Two-component multiplication requires compatible NTT/Montgomery inputs and returns a three-component NTT/Montgomery ciphertext. The result scale is the product $Δ_{c} Δ_{d}$ ; equal input scales give $Δ^{2}$ . Relinearization and rescale are separately represented transitions placed by the caller or selected scheduling passes.

Relinearization

The original first two components are combined with corrections that replace the $s^{2}$ dependency represented by e2. Coefficient output inverses all required terms. NTT output inverses only e2 for digit decomposition, retains the first two components as evaluations, and adds NTT-domain corrections.

Hybrid key-switch pipeline

Each stage has distinct row, basis, and representation requirements. Fusing stages may be useful, but a fused operator must preserve the same observable state and residue-range assumptions.

Hybrid digits across depths

All Q primes, including the terminal group, are partitioned into contiguous digits by their products. Each digit takes the longest next Q prefix whose product is below the special modulus P; a single prime at or above P occupies its own digit. At later depths, consumed Q groups shorten or remove digits.

RnsDigitSpec keeps both the active digit index and stable depth-zero key_digit_index used to select the correct evaluation-key axis. A local digit index is not necessarily the key tensor index.

The partition determines the evaluation key's digit axis. Key generation, Compile lowering, and execution derive that axis from the same decomposition. Changing the partition requires regenerating the key.

Rotation and hoisting

Rotation applies a Galois automorphism and then key-switches the transformed secret dependency. For several steps on the same input component, preparation can be shared:

Step-specific work and outputs remain. Hoist chunking must account for live prepared digits, accumulators, rotated outputs, and key residency.

The native product accumulator can gather the prepared digit's NTT indices while reading it. This combines the rotation-specific permutation with multiplication by the key, avoiding a separate permuted-digit tensor. It changes neither the key's row order nor the destination accumulator order.

Keeping key-switch outputs in NTT representation

Engine.rotate_with_key(..., output_domain="ntt"), Engine.rotate_many_with_keys(..., output_domain="ntt"), relinearize, switch_key, conjugate, and the corresponding CKKS operation attributes request NTT/Montgomery outputs. The default remains coefficient/standard. Both choices preserve Q rows, depth and actual scale.

The logical rns.ModDownNttQpToQOp removes P without inverting the Q rows. For QP NTT data $\hat{x}$ , let $r \in [0, P)$ be the coefficient representative reconstructed from the P residues. Then

{\hat{y}}_{q_{i}} = {\hat{x}}_{q_{i}} P^{- 1} + {NTT}_{q_{i}} (- r P^{- 1}) (\mod q_{i}) .

This is coefficient-domain ModDown followed by forward NTT. The implementation inverts only P rows, builds the correction in Q, and adds its forward transform to the retained Q evaluations multiplied by $P^{- 1}$ . Shared rotations also transform the input's $c_{0}$ once and permute those evaluations for each output. The consumer can multiply these results by NTT plaintexts without another coefficient-to-NTT transition. Output representation is a caller-selected part of the operation, independent of CPU or CUDA execution.

An independent rotate_with_key may also consume NTT/Montgomery input. The automorphism permutes both components in NTT representation; only the second component is inverted for hybrid decomposition and key switching. When NTT output is requested, the permuted first component remains in NTT and receives the NTT-domain correction directly. This form is useful when both the producer and consumer already use NTT values, but it is not assumed to be the fastest form on every CPU and GPU workload.

For independent rotations with coefficient input, the $c_{0}$ contribution is added to the coefficient correction before its forward NTT. Linearity gives $NTT (c_{0} + δ)$ instead of separate transforms of $c_{0}$ and $δ$ . The compact radix-2 implementation folds multiplication of the retained Q evaluations by $P^{- 1}$ and addition of the correction into the final NTT write.

The same NTT policy also supports streaming digit consumption: the last NTT stages directly multiply the digit by both evaluation-key components and add the products to QP accumulators. The digit scratch is disposable; its completed NTT values are not written back. Each scratch is released before the next digit is prepared. Other NTT policies retain their separate transform and product implementation, with the same CKKS operation semantics.

Rescale

For the leading active Q depth group $G_{l}$ , let $M_{l} = \prod_{q \in G_{l}} q$ :

c^{'} \approx round (c / M_{l}) (\mod Q_{l + 1}) .

The implementation must select constants using configured prime identities, not an ambiguous compact row position. Output metadata must increase depth, remove all IDs in the dropped group, reduce row count by that group's size, and update scale by $M_{l}$ .

NTT/Montgomery input can remain in that representation. The implementation inverts only the dropped row to obtain the rounding value, forms the quotient correction on surviving Q rows, transforms that correction, and adds it to the surviving evaluations multiplied by $M_{l}^{- 1}$ . This is congruent to coefficient rescale followed by a forward NTT without inverting the surviving input rows.

Correctness hazards

High-risk errors include:

using local row count to infer the wrong configured modulus;
selecting the wrong key digit after earlier primes are dropped;
mixing Q and QP parameter rows;
applying NTT tables for another active slice/device;
treating singleton digits as a normal full group;
violating lazy/standard residue-range assumptions across fused operators;
copying or overwriting staged data before another stream/device is done;
reconstructing correct tensor values with wrong public metadata.

Validation matrix

For a change in these paths, cover:

text

fresh single operation
chained operation across several depths
depth 0 / middle / maximum depth
single-row digit and shortened digit
Q / QP
2 / 3 components
functional / in-place
multiple NTT backends
logN = 14 smoke and target logN = 15 or logN = 16
source build and installed wheel
world size 1 and 2+ if transport/partition is involved

Decrypt after every legal materialization step to localize the first incorrect stage.

Continue

Source map

Path	Source owner
Public multiplication, relinearization, rotation, and plaintext calls	`fhelium/eager/_engine.py`
Hybrid decomposition, ModUp, key products, and ModDown	`fhelium/backend/rns/`, `fhelium/backend/ckks/rotation/`
Whole-operation streaming implementations	`fhelium/backend/ckks/arithmetic.py`, `fhelium/backend/ckks/key_switch.py`
Rescale resources and quotient construction	`fhelium/backend/rns/tables.py`, `fhelium/backend/rns/rescale.py`
RNS/NTT arithmetic and active parameters	`fhelium/backend/rns/context.py`, `fhelium/backend/ntt/`
CKKS-local operator schemas	`csrc/ops/ckks/ckks.cpp`
CPU CKKS tensor primitives	`csrc/ops/ckks/cpu/ckks_cpu.cpp`
CUDA Galois, key-switch, plaintext, and rescale kernels	`csrc/ops/ckks/cuda/`

Multiplication, key switching, and rescale ​

Numerical implementation path ​

Plaintext multiplication ​

Ciphertext multiplication ​

Relinearization ​

Hybrid key-switch pipeline ​

Hybrid digits across depths ​

Rotation and hoisting ​

Keeping key-switch outputs in NTT representation ​

Rescale ​

Correctness hazards ​

Validation matrix ​

Continue ​

Source map ​