“Supported” is absolutely not the same as “cheap”
Fully homomorphic encryption delightfully allows arithmetic without decryption, but each operation violently expands into modular arithmetic on massive polynomial objects. A line of source code is therefore a terrible cost unit. Two expressions that look equally short can require entirely different keys, different memory passes, and wildly different latency.
Usually the lightest operation; noise still reliably grows.
Consumes precious scale and noise headroom and may increase component count.
Needs an evaluation key, massive memory traffic, and a substantial datapath.
The obvious dot-product circuit contains an expensive reduction
Pack coordinates into lanes and multiply the matching lanes. At that exact moment, we have D separate products, not one final score. A reduction is the step that combines many values into one single scalar. In ordinary software, it might just be a loop or a tree of additions. In a packed ciphertext, values cannot be casually indexed and moved around as if they were a Python list.
A common encrypted reduction rotates the packed result by 1, 2, 4, and so on, adding after every single rotation. Each stage doubles how many original lanes have been successfully accumulated. For D=8, three stages combine groups of 2, then 4, then 8; for D=128, a painful seven stages are required.
Worked example
Why logarithms appear here
Start with 128 independent lane products. After one rotate-and-add stage, each accumulation covers 2 products; then 4, 8, 16, 32, 64, and finally 128. The count is exactly seven because 2⁷=128. The logarithm is simply the natural result of repeatedly doubling coverage, not a magical formula dropped from nowhere.
Worked example
The software analogy
A database may support a query that performs a massive remote shuffle, but a good engineer still restructures the data to avoid the shuffle. Here, rotation is that expensive data rearrangement. We're going to change the coefficient layout so ordinary multiplication naturally performs the reduction for us.
Check your understanding
Why does circuit shape matter so much under FHE?
Reduction check
Immediately after matching-lane multiplication of two length-8 vectors, what do we actually have?
Section summary
- FHE operations have radically unequal implementation costs.
- A standard lane reduction usually needs logarithmically many expensive rotations.
- A clever data layout can replace expensive movement with a much cheaper invariant.
Repository layer · second pass
Why can two mathematically equivalent circuits have radically different cost?
FHE cost depends on circuit shape, not only the final formula. Additions are comparatively cheap; ciphertext multiplications consume depth and precision; rotations require special keys, data movement, and automorphisms. A textbook dot-product reduction that repeatedly rotates and adds can dominate a design even though its plaintext code looks simple.
Count operations by kind, level, and data volume. Also count key bytes, transform traffic, memory passes, and synchronization. An “allowed” operation is not automatically an affordable hot-path operation.
Reasoning chain
- 1
Write a baseline circuit.
- 2
Count additions, multiplications, rotations, and multiplicative depth.
- 3
Estimate keys and bytes moved.
- 4
Locate repeated work across corpus batches.
- 5
Change representation before micro-optimizing gates.
Worked trace
Reduction tree cost
- D=512 packed coordinate products occupy slots.
- A rotate-and-add tree has log₂512=9 stages.
- Each stage rotates a ciphertext and adds it.
- The rotations repeat for every scored batch.
Result. Nine is small as a loop count but expensive when each step is a ciphertext permutation.
Executable lens · Python
Make the hidden state visible
from math import log2
def reduction_stages(d):
assert d > 0 and d & (d - 1) == 0
return int(log2(d))
assert reduction_stages(512) == 9Retype this example, predict each intermediate value, and then change one input that touches a boundary.
Misconception clinic
Tempting mistakes
- Counting source-code operators rather than cryptographic primitives.
- Ignoring rotation-key storage and transfer.
Retrieval and transfer
Close the book first
- Build an operation table for D=768 without assuming a power of two.
- Separate latency from throughput costs.
- List work the rotation-free layout does not eliminate.