Late relinearization and NTT reuse

Example source: examples/06_explicit_state_late_relinearization_ntt.py

This example accumulates three-component products before relinearization and reuses fixed multiplication operands in NTT form. The tutorial explains the exact state preconditions that make both optimizations valid.

Run the example

bash

python examples/06_explicit_state_late_relinearization_ntt.py \
  --preset slots8192-scale40-levels7-int64 \
  --pair-count 3

1. Prepare multiplication operands

python

multiplicand_ntt = engine.coefficient_domain_to_ntt_domain(engine.encrypt_message(multiplicand))
multiplier_ntt = engine.coefficient_domain_to_ntt_domain(engine.encrypt_message(multiplier))

CkksEngine.multiply has these fixed preconditions:

both inputs have two components;
both inputs are in the same NTT/Montgomery representation;
level, scale, basis, context, and active prime IDs are compatible;
the result is a three-component NTT ciphertext;
no implicit relinearization or rescale occurs.

2. Accumulate three-component products

python

product = engine.multiply(multiplicand_ntt, multiplier_ntt)
accumulator = (
    product
    if accumulator is None
    else engine.add(accumulator, product)
)

Compatible three-component products can be added before relinearization. This turns a sum of products from:

into:

The optimization is valid only while all terms share a matching exact layout and scale. An intervening operation that requires an ordinary two-component ciphertext creates a point at which relinearization becomes necessary.

3. Relinearize and rescale once

python

output = engine.rescale_to_next_level(engine.relinearize(accumulator))

Relinearization key-switches the c2 contribution back into two ciphertext components. It is usually much more expensive than an elementwise modular addition, so reducing its count is useful for dot products, matrix methods, and polynomial schedules. The accumulated product still carries scale $Δ^{2}$ ; the rescale consumes one level after relinearization.

4. Keep reusable operands in NTT form

python

fixed = engine.coefficient_domain_to_ntt_domain(engine.encrypt_message(fixed_values))
source = engine.coefficient_domain_to_ntt_domain(engine.encrypt_message(source_values))

product = engine.multiply(source, fixed)

The example isolates the preparation pattern. In a larger loop, a compatible fixed operand can remain in NTT/Montgomery form and be multiplied by several prepared sources without repeatedly entering and leaving the polynomial domain.

The application must still account for:

the memory cost of retaining the prepared operand;
its exact level and scale;
whether consumers mutate it;
whether later operations require coefficient-domain form.

5. Inspect state instead of assuming it

The example prints:

text

component count, polynomial domain, residue representation, and scale

Use those fields when debugging a schedule. A tensor with the expected shape but the wrong domain or Montgomery representation is not a compatible operand.

Late does not mean automatic

FHElium does not keep a hidden pending-relinearization flag and later materialize it implicitly. The three-component value is a normal Ciphertext, and the caller chooses the exact relinearization point.

Complete runnable source

#!/usr/bin/env python3

"""Explicit late-relinearization and NTT-reuse workflows."""

from __future__ import annotations

import argparse
from typing import cast

import torch
from common import (
    add_engine_args,
    error_stats,
    make_engine,
    print_table,
    small_complex_vector,
)

import fhelium as fh


def _state(ct: fh.Ciphertext) -> str:
    return (
        f"components={ct.component_count},polynomial_domain={ct.polynomial_domain},"
        f"residue_representation={ct.residue_representation},scale={ct.scale:.3e}"
    )


def late_relinearization(
    engine: fh.CkksEngine, pair_count: int
) -> tuple[fh.Ciphertext, torch.Tensor]:
    accumulator: fh.Ciphertext | None = None
    reference: torch.Tensor | None = None
    for index in range(pair_count):
        multiplicand = small_complex_vector(
            engine.num_slots, seed=100 + index, scale=0.005
        )
        multiplier = small_complex_vector(
            engine.num_slots, seed=200 + index, scale=0.005
        )
        multiplicand_ntt = cast(
            fh.Ciphertext,
            engine.coefficient_domain_to_ntt_domain(
                engine.encrypt_message(multiplicand)
            ),
        )
        multiplier_ntt = cast(
            fh.Ciphertext,
            engine.coefficient_domain_to_ntt_domain(
                engine.encrypt_message(multiplier)
            ),
        )
        product = engine.multiply(multiplicand_ntt, multiplier_ntt)
        accumulator = (
            product if accumulator is None else engine.add(accumulator, product)
        )
        reference = (
            multiplicand * multiplier
            if reference is None
            else reference + multiplicand * multiplier
        )

    if accumulator is None or reference is None:
        raise ValueError("pair_count must be positive")
    output = engine.rescale_to_next_level(engine.relinearize(accumulator))
    return output, reference


def ntt_reuse(
    engine: fh.CkksEngine,
) -> tuple[fh.Ciphertext, torch.Tensor]:
    fixed_values = small_complex_vector(engine.num_slots, seed=300, scale=0.005)
    source_values = small_complex_vector(
        engine.num_slots, seed=301, scale=0.005
    )
    fixed = cast(
        fh.Ciphertext,
        engine.coefficient_domain_to_ntt_domain(
            engine.encrypt_message(fixed_values)
        ),
    )
    source = cast(
        fh.Ciphertext,
        engine.coefficient_domain_to_ntt_domain(
            engine.encrypt_message(source_values)
        ),
    )

    product = engine.multiply(source, fixed)
    output = engine.rescale_to_next_level(engine.relinearize(product))
    return output, source_values * fixed_values


def main() -> None:
    parser = argparse.ArgumentParser(description=__doc__)
    add_engine_args(parser)
    parser.add_argument("--pair-count", type=int, default=3)
    args = parser.parse_args()
    engine = make_engine(args)

    late, late_reference = late_relinearization(engine, args.pair_count)
    reuse, reuse_reference = ntt_reuse(engine)
    rows = []
    for name, value, reference in [
        ("late relinearization", late, late_reference),
        ("NTT operand reuse", reuse, reuse_reference),
    ]:
        error = error_stats(
            engine.decrypt_message(value), reference, engine.num_slots
        )
        rows.append(
            [name, value.level, _state(value), f"{error['max_abs']:.3e}"]
        )
    print_table(["demo", "level", "state", "max abs error"], rows)


if __name__ == "__main__":
    main()

Late relinearization and NTT reuse ​

Run the example ​

1. Prepare multiplication operands ​

2. Accumulate three-component products ​

3. Relinearize and rescale once ​

4. Keep reusable operands in NTT form ​

5. Inspect state instead of assuming it ​

Related concepts and guides ​

Late relinearization and NTT reuse

Run the example

1. Prepare multiplication operands

2. Accumulate three-component products

3. Relinearize and rescale once

4. Keep reusable operands in NTT form

5. Inspect state instead of assuming it

Related concepts and guides