Skip to main content

← HomOps Reference

HomExpand

Replicate an encrypted value k times along a new axis.

ExSlots
RunsServer
Changes shapeYes - inserts an axis of size k at k_axis
Changes scaleYes - managed per mod-switch group
Levels spentlen(stage_sizes) / stages_per_level
RotatesYes - stage plan via stage_sizes
KeysRotation key

What it does​

HomExpand takes an encrypted value and replicates it k times, creating a new axis of size k in the output shape. The copies are built across slots with a rotation-sum tree: each stage doubles up (or multiplies up) the number of copies until all k exist.
The usual reason to expand is a multiply that follows. A short encrypted query is broadcast across a plaintext database axis, then combined with HomConstMul or HomMul and summed. That is the pattern behind exact search and similar retrieval flows. When that query is encrypted in a sub-ring, HomRingSwitch must be the first server operator; expand runs after the lift.
HomExpand is often paired with Repeat on the client side: repeat fills the ciphertext slots before encryption, expand creates the k-wide axis on the server.
Because it rotates, HomExpand takes a stage plan. If stages, offsets, and rounds are new to you, read Slots, rotations & stages first; this page only states how the rules land on this operator.

Signature​

HomExpand(
    k,                      # required
    k_axis=0,
    stage_sizes=None,
    stages_per_level=None,
    rows_budget=None,
)
HomExpand takes no weights, so there is no set_data call. The masks it multiplies by are generated at compile time; rows_budget can constrain the internal mod-switches.

Parameters​

ParameterTypeDefaultDescription
kintrequiredReplication factor. Size of the new axis.
k_axisint0Where the new axis is inserted, as an index in the output shape.
stage_sizessequenceNoneThe stage plan: one entry per stage, each entry the stage's group size. Unset means (2,) × log₂(k), the smallest-key plan.
stages_per_levelintNoneHow many stages share one mod-switch. Unset means 1: a mod-switch after every stage.
rows_budgetSequence[int] | NoneNoneAbsolute rows allowed for the internal mod-switches, useful when reserved rows must be preserved.
Rules that depend on the value
SettingRuleIf you break it
stage_sizesThe entries must multiply out to k: prod(stage_sizes) == k.Compilation fails: Product of stage_sizes must be equal to k.
stage_sizes unsetThe default plan (2,) × log₂(k) only exists when k is a power of two.For any other k, write the plan yourself.
stages_per_levelMust divide the number of stages exactly: len(stage_sizes) % stages_per_level == 0.Compilation fails: stages_per_level must divide len(stage_sizes).

Requirements​

  • Rotation key entries. Every rotation offset in the stage plan must be present in the evaluation key. The compiler derives the exact set from k and stage_sizes and generates the key with those entries; you don't list them yourself.
  • Slot data in place. The value to replicate must fill the slots the tree reads from. When the input is shorter than the slot count, run Repeat in client_pre first.
  • Level headroom. The chain must have len(stage_sizes) / stages_per_level levels left when the expand runs. See Level budget.
These surface as compilation errors; see Compilation errors.

Shape effect: yes​

Rule: the output shape is the input shape with an axis of size k inserted at k_axis.
shape.pyPYTHON
# input shape:  (d0, d1, ..., dn)
# output shape: insert k at position k_axis
output = (*shape[:k_axis], k, *shape[k_axis:])
Input shapekk_axisOutput shape
(4096,)641(4096, 64)
(n_slots,)1281(n_slots, 128)
(d0, d1)80(8, d0, d1)
The n axis itself is not consumed; its position shifts by one when k_axis is inserted before it. Shape and the n axis are covered on Concepts.

Pipeline chain view​

Exact search pattern, query expanded across the database's record axis:
pt_shape: (n_slots,)after Repeat + encrypt
HomExpand(k=64, k_axis=1)
pt_shape: (n_slots, 64)ready for the database multiply

Scale effect: yes​

Rule: scale is managed per mod-switch group. A group is stages_per_level consecutive stages.
Inside each group:
  1. Each stage multiplies by a plaintext mask. The mask scales are chosen so the whole group's growth equals one prime's worth.
  2. At the end of the group, one mod-switch runs and divides the scale back down.
So the scale climbs within a group and is brought back at the group boundary, once per group instead of once per stage. The net effect over the whole operator is one mod-switch worth of scale movement per group. How scale moves through a pipeline is on Ciphertext state → Scale.

Stages & rotations​

The general rules live on Slots, rotations & stages; here is how they apply to HomExpand:
QuestionAnswer for HomExpand
Where does k come fromYou pass it. k is a required parameter: the size of the axis you're creating.
Default planstage_sizes unset gives (2,) × log₂(k). Requires k to be a power of two.
Plan constraintprod(stage_sizes) == k
Distinct rotation offsetsΣ (entry − 1) over the plan. Sets the rotation key size.
Roundslen(stage_sizes). Sets how many passes the server makes; fewer rounds means a faster query.
Levels spentlen(stage_sizes) / stages_per_level, controlled by stages_per_level.
The three plans from the concepts page, on this operator:
plans.pyPYTHON
# Default: log-depth tree (smallest key)
HomExpand(k=128)                                          # 7 stages, 7 offsets, 7 levels

# Collapsed: one wide stage (bigger key, fastest)
HomExpand(k=128, stage_sizes=(128,))                      # 1 stage, 127 offsets, 1 level

# Small key, grouped mod-switches (fewest levels for this tree)
HomExpand(k=128, stage_sizes=(2,)*7, stages_per_level=7)    # 7 stages, 7 offsets, 1 level

Level budget​

ConfigurationLevels spent
Defaults (stage_sizes and stages_per_level unset)log₂(k) - one per stage
Explicit planlen(stage_sizes) / stages_per_level
Each mod-switch drops one prime from the chain, at the end of each group of stages_per_level stages. The rotations and mask multiplies themselves spend nothing; only the mod-switches do.
Use rows_budget (the same mechanism as on HomMul) when you need to restrict which levels these mod-switches may touch. How primes are organized in the chain, and what exactly gets dropped, is explained on Level budget → The chain.

Keys​

Rotation key. Every offset in the stage plan needs an entry in the rotation key. The set is derived at compile time from k and stage_sizes, and the key is generated for you during key generation with exactly those entries. Wider stages mean more offsets and a bigger key; that trade is on Slots, rotations & stages.
No square key: HomExpand never multiplies two ciphertexts.

Example​

The exact-search pattern: repeat the query to fill the slots, expand it 64 ways, multiply against the database, and reduce. When the query is encrypted in a sub-ring, put HomRingSwitch first on the server, then this expand.
pipeline.pyPYTHON
from lattica_build.client_ops import Repeat
from lattica_build.operators import (
    HomExpand, HomConstMul, HomAxisSum, HomSquare,
)
from lattica_build.base_classes.hom_pipeline import HomomorphicPipeline
from lattica_build.operators.composite.sequential import SequentialHomOp

pipeline = HomomorphicPipeline(
    client_pre=[Repeat()],
    hom=SequentialHomOp(
        HomExpand(
            k=64,
            k_axis=1,
            stage_sizes=[4, 4, 4],   # 4 * 4 * 4 = 64
            stages_per_level=3,        # one mod-switch for all three stages
        ),
        HomConstMul(dims=db.shape, with_modswitch=True),
        HomAxisSum(dim=2, keep_dim=True),
        *(HomSquare(with_modswitch=True) for _ in range(2)),
        HomAxisSum(dim=0, keep_dim=False),
    ),
    input_shape=(N_SLOTS,),
)
pipeline.set_data(1, db)
The plan [4, 4, 4] costs 3 + 3 + 3 = 9 rotation offsets over three rounds, and with stages_per_level=3 spends one level.

Minimal expand​

pipeline.pyPYTHON
K = 128
pipeline = HomomorphicPipeline(
    client_pre=[Repeat()],
    hom=SequentialHomOp(
        HomExpand(K, k_axis=1, stage_sizes=[8, 16], stages_per_level=2),
    ),
    input_shape=(K,),
)
[8, 16] covers 128 in two stages: 7 + 15 = 22 offsets, two rounds, one level.

See also​