Composable CKKS bootstrapping
FHElium composes bootstrapping from replaceable mathematical components executed through the ordinary fhelium.eager.Engine, Ciphertext, NTT, and native operator stack. The built-in FullSlotBootstrap makes its linear maps, periodic reduction, depth budget, primitive-key requirements, and arithmetic scale schedule visible.
The mathematical map
Let:
be the ring dimension and the complex slot count; bebootstrap.input_scale, which defaults toconfig.default_scale; be the product of the source Q suffix selected bysource_depth; and be the unscaled CoeffsToSlots and SlotsToCoeffs maps, with in FHElium's cyclotomic slot order; be a periodic reducer'sinput_bound.
Entry accepts the source Q basis directly or rescales its preceding group into that basis. The default source is the terminal Q group. Centered ModRaise extends the components into the Q basis at modulus_raise_target_depth; encapsulated raising first changes the secret relation, extends the centered components and returns to the original relation. After the compensated entry-coordinate conversion described below, let
The values
The built-in periodic reduction approximates
For
The polynomial fit, CKKS rounding, and key switching perturb this idealized expression. input_bound states the mathematical precondition that applications must establish:
Modulus raising and secret relations
Centered raising
A coefficient/standard Q ciphertext defines a residue class for each component coefficient. Centered raising selects its signed representative modulo the source product
Sparse-secret encapsulation
An encapsulated construction first switches from main secret
The centered components are then extended into a larger basis. A return hint encrypted under
The lifted second component multiplies this hint, and a common quotient by
A fixed-weight intermediate secret has a selected number of nonzero coefficients and independent signs. Its coefficient convolution changes the distribution and extent of the integer phase
The low and return bases, secret distributions and jointly published key relations are construction parameters. A bit-security claim requires their associated assumptions and attack assessment; the main QP size alone does not describe this joint transcript.
Full-slot state flow
The built-in callable executes:
All public pipeline ciphertexts have axes [component, *batch, limb, coefficient], two components, Q basis, and prime_ids. They remain in coefficient domain with standard residues between operations. NTT-domain Montgomery values may span a complete polynomial or double-angle chain before returning to the coefficient-domain pipeline. Each linear stage removes one Q group, whose product is BootstrapArithmetic uses supplied depth targets or derives its default schedule backward from the terminal target
Ciphertext multiplication at
For preceding-group entry, preparation multiplies residues and scale by integer
Independent polynomial components derive basis scales from their input's actual scale rather than assuming it matches a full-slot stage. Coefficient products and accumulators connect the resulting basis values to the requested output scale. Available precision and integer-encoding range still limit which input scales, degrees, and modulus groups can be evaluated accurately.
Key-switch basis extension defaults to the exact Garner lift. For a digit product normalized_crt or crt requires a noise budget consistent with the digit partition, auxiliary product P, actual scales and complete refresh precision.
Raw and normalized reducer coordinates
CosineDoubleAngleReduction distinguishes raw and normalized input coordinates:
reference(values)always consumes normalized and never divides byinput_bound;evaluate(...)consumes raw whenfuse_input_normalization=Falseand spends one depth computing ;- with
fuse_input_normalization=True, the caller must already provide .FullSlotBootstrapdoes so by folding into CoeffsToSlots.
Both routes target
Replaceable decisions
A polynomial evaluator chooses a homomorphic multiplication directed acyclic graph (DAG) for the stored approximation.
| Component | Replaceable decision |
|---|---|
| polynomial approximator | How a function becomes basis-tagged coefficients |
| polynomial evaluator | Which homomorphic multiplication DAG evaluates them |
| linear-transform compiler | How a basis map becomes executable stages |
| linear-transform evaluator | Direct, BSGS, or another stage schedule |
periodic reduction (modular_reduction) | Cosine recurrence or a caller-supplied periodic approximation |
| ordinary Python | Complete algorithm topology and control flow |
A PolynomialApproximation stores coefficients in ascending degree. Power basis means
Direct and BSGS linear evaluation
A cyclic-diagonal stage represents
The direct evaluator computes every term independently. The baby-step/giant-step (BSGS) evaluator writes
They therefore implement the same mathematical map, output depth, actual-scale recurrence, domain, basis, and prime_ids. Their operation grouping and CKKS rounding can differ, so residue tensors need not be bit-identical.
Within one BSGS giant group, the built-in evaluator dispatches the represented sum
as one RNS operation. Its CPU implementation reuses the ordinary Montgomery product and standard-add primitives. Its CUDA implementation keeps one modular accumulator per output coefficient and reads existing ciphertext/plaintext Tensors through a bounded pointer set; it does not stack all term products or encode BSGS policy into the native operation.
BSGS creates two reusable sets: the distinct baby rotations and the partial sums for giant groups. Group-major traversal retains the baby rotations and completes a bounded block of groups at a time; each rotation's final block consumer ends its lifetime. Baby-major traversal retains group partial sums and consumes one baby rotation at a time. The default traversal retains the smaller set by cardinality, choosing group-major on a tie. A caller may choose either traversal for a stage.
Within one linear stage, both sets contain two-component ciphertexts with the same batch, Q-row and ring extents. If
The current block of group sums, hybrid-digit preparation, key-product scratch and diagonal materials are additional live storage. With direct baby keys, one prepared QP digit set can serve successive rotations without requiring all rotation outputs to coexist. Composed inventories perform their keyed rotation paths. Both traversals preserve each group's term order and process giant offsets in increasing order. The quotient schedule is selected independently of traversal.
Binary-decomposition Chebyshev evaluation shares a basis node until its final recurrence or coefficient consumer. Coefficient products at a common depth can be accumulated before all other basis nodes have been produced; their group rescale remains a depth transition of the summed product. This separates the arithmetic dependencies from retaining every intermediate through the end of the polynomial. Block-factorized evaluation instead builds its shared binary basis, then retains the aligned baby values and pending giants while consuming coefficient blocks.
The aggregate giant-step schedule sums unrounded key products in QP, including the ordinary ciphertext components multiplied by P, before dividing once by
The available output depth is determined jointly by the modulus chain and the component depth costs. If the input depth is
Shared key inventory and consumer requirements
EvaluationKeySet is an application-owned collection of ordinary rotation, relinearization and conjugation key values. A bootstrap consumes it through evaluation_keys=. The inventory can retain several physical layouts and device copies for one operation, allowing different compositions and stages to share available material. Its membership is independent of consumer depth: active Q rows, digit supports, P rows, ring dimension, dtype and device determine suitability. Key lifecycle defines inventory ownership and key relations.
required_rotations and key_steps() describe the transform rotation schedule. Relinearization is required when the reduction performs ciphertext products, and conjugation is required by branch handling and reconstruction. Provisioning generates missing capabilities before material discovery; create_evaluation_keys reuses compatible inventory groups and accounts for their additional storage across the composition. One key shared by several stages can cost less than separate compact keys for each stage.
Hoisted baby rotations share prepared source digits. The selected keys must form a compatible group with the same effective digit supports and physical interpretation. A collection of individually usable step keys can fail that shared-preparation requirement. Direct keys and composed rotation paths also differ in online operations, scratch storage and key-switch error.
Rotation, relinearization and conjugation keys use the main secret relation. An encapsulated raising component additionally retains low and return switch keys, whose intermediate secret and auxiliary moduli are independent construction parameters. The application maintains these relations and the parameter context; structural key selection does not prove them.
Profile choices
A profile selects transform stage counts, polynomial degree, periodic-reduction bound and branch schedule. key_steps("signed_power_of_two") describes the compact composed-rotation inventory; key_steps("all_required") describes direct transform rotations. key_steps("signed_power_of_two_with_baby_steps") augments signed-power coverage with direct baby steps from the selected BSGS partitions. A caller may also supply a mixed inventory, which the evaluator resolves per requested rotation.
The Engine supplies the Q chain and arithmetic contexts. Source and entry depths, input scale and per-depth coefficient-product targets complete the scale schedule. Accuracy, resident storage and latency depend on this composition, the key inventory and the represented input class.
The profiles specify component parameters and depth costs. The output-depth column assumes modulus_raise_target_depth=0; construction still rejects an Engine whose max_depth is too small for the selected composition.
| Profile | Raw bound | Polynomial degree | Double-angle iterations | CTS stages | STC stages | Output depth |
|---|---|---|---|---|---|---|
7/44 | 1024 | 44 | 7 | 2 | 2 | 19 |
8/28 | 1024 | 28 | 8 | 2 | 2 | 19 |
8/28-s2c3 | 1024 | 28 | 8 | 2 | 3 | 20 |
3/30 | 32 | 30 | 3 | 4 | 3 | 17 |
The bound column describes the raw reduction coordinate. The degree-30 profile uses the even-polynomial identity
Evaluation schedules and numerical materials
A polynomial approximation specifies coefficients and a basis coordinate. Its evaluation schedule specifies dependencies, depth transitions and the placement of relinearization and rescale. Binary decomposition shares individual Chebyshev nodes; block factorization forms coefficient-weighted baby polynomials and multiplies them by shared giant nodes. The represented polynomial is unchanged, while rounding and key-switch noise depend on the chosen schedule. Complex polynomial evaluation retains the imaginary component.
Constant slot messages admit compact period-one encoding. Cached scalar plaintexts retain an encoded stochastic-rounding sample at a particular actual scale, prime-row set, representation and device. Reusing that material does not consume further rounding randomness. Rotation-key inventories similarly reflect an execution choice: signed-power keys permit compositions, while direct baby keys permit shared decomposition within suitable BSGS groups. The key inventory and its resident storage are distinct from the mathematical rotation offsets.
Normalized core and prepared execution
For preceding-group entry, preparation multiplies residues and scale by an integer
A prepared core binds component objects, an input state and device, and the selected key references and encoded materials. During material discovery, the executing consumer selects keys from the shared inventory and records the actual choices in ordinary dictionaries. Preparation consumes the normal first-encoding rounding samples; subsequent execution uses those samples and bound keys. The prototype ciphertext and preparation output are temporary.
Each prepared core owns its material dictionaries. Appending to or clearing the inventory leaves existing prepared bindings unchanged because those dictionaries retain their selected references. The key Tensor contents remain live. PreparedBootstrap combines this core with entry and finish, supplying one computation body to ordinary Eager execution and Compile capture. Backend execution consumes the represented key and table Tensor operands.
Encoded NTT diagonals can use contiguous repeated-block storage. If a row changes value at position
Real-valued slot composition
FullSlotBootstrap(message_domain="real") refreshes ciphertexts whose decoded CKKS slots are real-valued. The default "complex" composition retains both periodic-reduction branches. A real-valued source model does not establish the real-slot precondition when its packing uses imaginary slot coordinates. The precondition belongs to the caller; encrypted data is not inspected to select a composition.
For the radix-2 SlotsToCoeffs map
The corrected transform is a new plan with its own encoded material entries. Its diagonal repetition can differ from the complex plan, so real-slot execution may retain more plaintext storage even though it evaluates one reduction branch. Both compositions use the same entry, preparation, core execution, finish and release lifecycle.
Represented weighted sums
A weighted-sum row computes
The native implementation uses grouped execution for dense rows and primitive products for mixed representations. The CUDA Triton implementation fuses each row's products and additions using the existing RNS expression generator. A term chunk limits each generated expression; partial sums are combined modulo the same primes. Chunking does not cross a key switch or rescale and does not change CKKS rounding.