Implement a bootstrap component

The experimental bootstrap component interfaces expose polynomial approximation, polynomial evaluation, linear-transform compilation and evaluation, and periodic reduction. Each component defines its coordinate, polynomial basis, tensor axes, arithmetic state, depth/scale recurrence, mutation behavior, and numerical range.

Prerequisites

Begin with a working bootstrap composition and choose one component to replace. State its input/output coordinates, polynomial basis or tensor axes, mutation behavior, and required depth and scale transitions.

Polynomial approximation

An approximator chooses coefficients but not the homomorphic multiplication DAG. Use ascending-degree coefficients and record the physical design interval:

class MyApproximator:
    def approximate(self, function, *, domain=(-1.0, 1.0), name="polynomial"):
        coefficients = fit_with_my_method(function, domain)
        return bs.PolynomialApproximation(
            basis="power",
            coefficients=tuple(coefficients),
            domain=domain,
            name=name,
        )

The two built-in basis conventions are

$$p(x)=\sum _{n=0}^d{a}_n{x}^n$$

and

$$p(x)=\sum _{n=0}^d{a}_n{T}_n(x).$$

If domain=(a, b) is physical coordinate $t$, the coefficient coordinate is

$$x=\frac{2t-(a+b)}{b-a}\in [-1,1].$$

PolynomialApproximation.evaluate_plaintext() receives the normalized coordinate $x$. The caller performs the transformation from $t$. Its input may have any NumPy-broadcastable axes; its output preserves those axes.

Polynomial evaluation

Implement required_depths() and evaluate() to execute another multiplication DAG:

class MyEvaluator:
    def required_depths(self, polynomial):
        return my_depth(polynomial.coefficients)

    def evaluate(
        self,
        arithmetic,
        ciphertext,
        polynomial,
        *,
        relinearization_key=None,
    ):
        return my_homomorphic_dag(
            arithmetic,
            ciphertext,
            polynomial.coefficients,
            relinearization_key=relinearization_key,
        )

State the basis your evaluator accepts. The built-in evaluators consume a two-component coefficient-domain standard-RNS Q ciphertext with axes [component, *batch, limb, coefficient] and active prime_ids. Their ciphertext products require a relinearization key and perform

coefficient/standard/Q/two components
  -> NTT/Montgomery/Q/two components
  -> NTT/Montgomery/Q/three components
  -> coefficient/standard/Q/two components
  -> drop one complete Q group and retain the actual quotient scale

A custom evaluator must report its actual scale recurrence, such as ${\mathrm{\Delta }}_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{t}}/M_d$ for the dropped Q-group product $M_d$. It must not claim required_depths(polynomial) == d unless every execution path advances by exactly $d$ depths. An evaluator may accept relinearization_key=None only on an execution path whose polynomial DAG contains no ciphertext product, such as a constant or linear built-in polynomial.

Linear-transform compilation

A compiler returns immutable stages. A stage stores whatever numerical data the matching evaluator understands:

from dataclasses import dataclass

@dataclass(frozen=True)
class SparseStage:
    slots: int
    matrix: object

    def reference(self, values):
        return self.matrix @ values

class SparseCompiler:
    def compile(self, *, slots, direction, generator, scale=1.0):
        matrix = synthesize_sparse_map(slots, direction, generator, scale)
        return (SparseStage(slots, matrix),)

reference() is a plaintext oracle. Document its accepted axes and whether its input is a raw physical coordinate or a normalized coordinate. The built-in radix-2 reference uses shape [slot] and the convention

$$T(C(a))=Sa.$$

The compiler's scale argument multiplies numerical matrix values.

Linear-transform evaluation

class SparseEvaluator:
    def required_rotation_offsets(self, transform):
        return tuple(rotations_used_by(transform.matrix))

    def required_depths(self, transform):
        return 1

    def evaluate(
        self,
        arithmetic,
        ciphertext,
        transform,
        *,
        rotation_keys,
        rotate,
        encode_diagonal,
    ):
        return evaluate_sparse_map(
            arithmetic,
            ciphertext,
            transform.matrix,
            rotation_keys=rotation_keys,
            rotate=rotate,
            encode=encode_diagonal,
        )

The callbacks provide rotation-key decomposition and diagonal encoding/cache policy. A built-in diagonal stage encodes an unbatched [limb, ntt_index] Montgomery plaintext at the selected scale ${\mathrm{\Delta }}_{p,j}$. For input scale ${\mathrm{\Delta }}_j$ and dropped group product $M_j$, one stage returns

$${\ell }_{j+1}={\ell }_j+1,{\mathrm{\Delta }}_{j+1}=\frac{{\mathrm{\Delta }}_j{\mathrm{\Delta }}_{p,j}}{M_j}.$$

The output remains two-component coefficient-domain standard RNS over Q, with unchanged batch axes and the complete leading prime_ids group removed. If a custom evaluator uses another recurrence or state transition, report the differing recurrence or transition.

For a cyclic-diagonal map

$$L(x)=\sum _k{d}_k\odot {\mathrm{Rot}}_k(x),$$

direct and BSGS evaluation are two schedules for the same linear map. A BSGS implementation should test the identity

$${\mathrm{Rot}}_g({\mathrm{Rot}}_b(x)\odot {\mathrm{Rot}}_{-g}(d_{g+b}))={\mathrm{Rot}}_{g+b}(x)\odot d_{g+b}.$$

Periodic reduction (modular_reduction)

A reduction component must distinguish raw and normalized coordinates. Let input_bound be $B$, raw input be $r$ with $|r|\le B$, and normalized input be $x=r/B$. The built-in output target is

$${\rho }_B(x)=\frac{\sin (\pi Bx)}{\pi }.$$

A custom component protocol can be as small as:

class MyReduction:
    input_bound = 1024
    fuse_input_normalization = True
    requires_relinearization = False

    @property
    def required_depths(self):
        return 6

    @property
    def fused_input_divisor(self):
        return float(self.input_bound) if self.fuse_input_normalization else 1.0

    def reference(self, normalized_values):
        return my_plaintext_periodic_oracle(normalized_values)

    def evaluate(
        self,
        arithmetic,
        ciphertext,
        *,
        relinearization_key=None,
        conjugation_key=None,
    ):
        del relinearization_key, conjugation_key
        # With fusion, ciphertext already represents x = r / input_bound.
        return my_periodic_reduction_without_ciphertext_products(
            arithmetic, ciphertext
        )

The component interface specification must state:

• whether reference() accepts $r$ or $x$;
• whether evaluate() accepts $r$ or $x$ under each fusion setting;
• the raw admissible interval and output target;
• the polynomial basis and design interval;
• required_depths and output actual scale;
• whether requires_relinearization is true because evaluation performs a ciphertext-ciphertext product;
• whether ciphertext products or conjugation consume the supplied primitive keys;
• output depth, component count, domain, basis, residue representation, and prime_ids;
• whether execution mutates or aliases an input.

FullSlotBootstrap expects fused_input_divisor to be the numerical factor folded into CoeffsToSlots. Returning $B$ asserts that the reducer will receive $x$ and must not divide by $B$ again. The reducer is a slotwise stage and does not receive rotation keys. Its evaluate() method receives keyword-only relinearization_key and conjugation_key values. A custom reduction that does not multiply ciphertexts supports relinearization_key=None; built-in reductions reject None. The full-slot topology always has a conjugation key for branch splitting, so reducers may use that same primitive without a second key declaration.

Full-slot integration requirements

A component that is inserted into FullSlotBootstrap participates in this state sequence:

Expanded diagram

100%

The callable calculates

$${\ell }_{\mathrm{o}\mathrm{u}\mathrm{t}}={\ell }_{\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{s}\mathrm{e}}+m_C+1+m_{\rho }+m_T.$$

Its final scale follows the actual SlotsToCoeffs recurrence and may differ from default_scale. A component must not hide a depth, scale reinterpretation, basis extension, NTT transition, or range normalization from its declared state-transition specification.

Test the behavior that matters

Test components independently before inserting them into a full bootstrap:

• compare reference() with the intended map on the documented coordinate;
• test raw-to-normalized equivalence using $x=r/B$;
• compare encrypted component output with the plaintext oracle;
• assert output depth advancement and actual scale recurrence;
• assert component, batch, limb, and coefficient/NTT axes;
• assert domain, basis, residue representation, and prime_ids;
• compare direct and BSGS decoded outputs for the same mathematical map;
• run full-slot end-to-end refresh across several seeds and admissible ranges;
• measure the application's actual raw branch range and error distribution.

Investigate a numerical failure using the implemented equations, coordinate convention, scale schedule, and observed error distribution.

Verify the outcome

Substitute the component into the same topology, validate its clear mathematical result first, and then measure encrypted error across its stated range. Preserve the component’s state and coordinate contract when comparing it with another implementation.