Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts Anis Bkakria1 , Madicke-Diadji MBODJ1,2 , Mawloud Omar2 , and Reda Yaich1
arXiv:2607.03631v1 [cs.CR] 3 Jul 2026
1
IRT SystemX, France 2 UBS, France
Abstract. Packed homomorphic encryption evaluates slotwise operations in parallel, but nonlocal communication is realized by cyclic rotations whose cost depends on the physical slot layout. We study ordered prefix computation on n = 2m elements of an associative, possibly noncommutative monoid stored in bit-reversed order. A direct transported-predecessor scan uses m·(m+1)/2 rotations because one logical shift decomposes into several cyclic displacement classes. We introduce a replicated-aggregate invariant in which every slot of an aligned logical block stores the same complete block aggregate. Semantic replication makes the copies interchangeable: at each level, one global cyclic rotation supplies every slot with a valid aggregate of its sibling block, even though it need not reach the exact logical partner. The resulting inclusive or exclusive scan uses m rotations, monoid depth m, two live state vectors, and at most 2 · m − 1 packed monoid compositions. In a model where all non-routing operations are slotwise and every cyclic rotation invocation is counted, both bounds are exact: D⋆ (m) = R⋆ (m) = m. Equality is rigid—the m rotation offsets contain exactly one representative of every 2-adic valuation 0, . . . , m − 1. With at most K directly keyed offsets, we prove a product lower bound on online rotation calls and an exact frontier K · (2m/K − 1) whenever K divides m. We instantiate the exclusive scan for radix carry and borrow in bit-reversed CKKS slots, avoiding both layout restoration and a final logical-predecessor shift. In our Lattigo implementation at m = 7, the replicated scan reduces the direct bit-reversed baseline from 28 to 7 rotations, lowers evaluation-key storage by 70.0%, lowers peak heap usage by 63.9%, and improves isolated scan latency by 19.9%. In a depth-5 downstream pipeline, retaining six additional modulus levels avoids one bootstrap and yields a mean paired speedup of 4.31× with a 95% confidence interval of [3.69, 4.92].
Keywords: homomorphic encryption · parallel prefix · cyclic rotations · bit reversal · CKKS · carry propagation
1
Introduction
Packed computation and layout-sensitive communication. Modern lattice-based homomorphicencryption schemes expose a SIMD abstraction: a ciphertext encrypts a vector of slots, and additions and multiplications act slotwise on the entire vector. In CKKS, this abstraction supports approximate arithmetic over packed complex values and has become a standard foundation for encrypted numerical computation [Che+17]. Slotwise parallelism, however, does not make communication free. Moving encrypted values between slots requires Galois automorphisms, commonly exposed as cyclic rotations followed by key switching. The number of logical dependencies in an algorithm and the number of encrypted rotations needed to realize them are therefore different resources. The distinction becomes particularly sharp when data is kept in a public structured layout. Fast transforms, packing conversions, and transposed representations may leave logical indices in bit-reversed or related orders. A classical prefix network is normally analyzed by its gate count, depth, and fanout [LF80; Har03]. Those measures do not determine the encrypted routing cost: one rotation realizes the same cyclic displacement at all slots, so many logical edges can share a rotation, while a single logical predecessor relation may split into several displacement classes after conjugation by the layout. The relevant question is consequently not only how many prefix gates are needed, but how many global cyclic translations are needed when the layout must be preserved.
Motivating application: exact carry in radix CKKS. Approximate arithmetic does not directly provide a canonical representation of large integers. Radix-based approaches store an integer as encrypted digits and periodically propagate carry or borrow to return the digit vector to a unique range. Recent work of Cha, Park, and Lee gives a logarithmic-round exact-carry mechanism for radix CKKS and uses it to support large-integer comparison and modular arithmetic [CPL26]. Carry propagation is an ordered prefix computation: every digit defines a transition on the incoming carry, and the carry entering position i is obtained by composing the transitions of all less significant digits. When the digits are already stored in bit-reversed order, two natural realizations incur additional routing. One may restore natural order, run a standard scan, and possibly restore the original layout. Alternatively, one may transport the usual recursive-doubling predecessor scan through bit reversal. For n = 2m digits, the latter has m composition levels, but its logical shift by 2t decomposes into m − t cyclic displacement classes. Its rotation count is therefore Rdirect (m) =
m−1 X
(m − t) =
t=0
m · (m + 1) . 2
(1)
This count is exact for that transported-predecessor topology. It is not, as we show, an inherent cost of prefix computation in a bit-reversed layout. The key idea: route semantic copies, not exact partners. The obstacle in the direct scan is overly specific routing. At a level that combines two adjacent logical blocks, each destination requests the value held by one precise logical predecessor. Under bit reversal, these requests occupy several cyclic diagonals. Our construction changes the invariant rather than searching for a better sequence of predecessor shifts. For every aligned logical block, we maintain its complete monoid aggregate replicated at every slot belonging to the block. We also maintain, in a second state vector, the ordered prefix local to that block. At level d, the two children of every length-2d+1 parent occupy the two physical cosets separated by sd = 2m−d−1 . (2) A rotation by sd does not necessarily map a slot to its exact XOR partner. It does something sufficient and cheaper: it maps the slot to some position in the sibling child. Because the child aggregate is replicated, every such position contains the same semantic value. One rotation consequently exchanges valid sibling aggregates for all blocks and both child orientations at once. Public masks select the operand order, which preserves correctness for noncommutative monoids. This semantic-copy observation reduces the routing cost from the triangular count in (1) to one rotation per level. The price is explicit: the construction keeps two live monoid states and performs one aggregate update and one prefix update at each nonfinal level. The result is thus a multi-resource trade-off rather than a claim that rotations are the only meaningful cost. Main theorem. Let n = 2m , and place logical input xi at physical slot revm (i). We consider acyclic, data-independent packed circuits in which masks, copying, and all other local operations are slotwise, while each invocation of a cyclic rotation is counted. Helper ciphertexts and recomputation are unrestricted, but an uncounted dense linear transform, arbitrary slot permutation, or bootstrapping transform is not available as hidden routing. In this model, the replicated scan computes every inclusive or exclusive ordered prefix using D = m,
R = m,
T ≤ 2 · m − 1,
(3)
where D is binary monoid depth, R is the number of cyclic-rotation invocations, and T is the number of packed monoid compositions. Both D and R are globally optimal: D⋆ (m) = R⋆ (m) = m.
(4)
The depth lower bound follows from binary fan-in. For rotations, fix one output depending on all 2m inputs. Along a dependency path, every one of the R rotation calls is either traversed or not, so the source displacement is a subset sum of the invoked offsets. At most 2R displacements can reach the output; hence 2R ≥ 2m and R ≥ m. This argument permits arbitrary helper width, branching, copying, masks, local nonlinear operations, and recomputation.
2
Structure at equality. Rotation optimality is rigid. Suppose exactly m rotations with offsets δ0 , . . . , δm−1 ∈ Z2m suffice for one output to depend on every slot. The 2m subset sums of these offsets must then be distinct. A roots-of-unity argument applied to m−1 Y
m
(1 + X δj ) = 1 + X + · · · + X 2 −1
m
(mod X 2 − 1)
(5)
j=0
shows that, after reordering, for 0 ≤ j < m.
ν2 (δj ) = j
(6)
Thus every optimal offset family forms a complete 2-adic basis: one offset appears at each valuation scale. This characterizes the rotation profile of every equality case, but it does not claim that the complete circuit topology is unique. Rotation keys versus online calls. A rotation invocation also requires evaluation-key material for its offset, unless the rotation is synthesized from other directly supported offsets. This creates a time–memory trade-off studied in generic key-management work [Lee+23]. Our result gives a program-specific lower bound. If at most K directly keyed offsets are invoked c1 , . . . , cK times, then one dependency path can realize at most K Y
(cj + 1)
(7)
j=1
coefficient vectors. Reaching all 2m source displacements therefore requires K Y
(cj + 1) ≥ 2m .
(8)
j=1
When K divides m, this lower bound is attained by grouping consecutive 2-adic scales and directly keying the smallest offset of each group. The exact frontier is R⋆ (m, K) = K · 2m/K − 1
(K | m).
(9)
For general K, we give an exact integer counting lower bound and a balanced dyadic upper bound; they coincide for all divisible cases and for additional nondivisible parameter pairs. We do not claim a closed formula when the two bounds differ. Exclusive carry and borrow without a final shift. For radix carry, an inclusive prefix at digit i naturally returns the outgoing carry ci+1 . The incoming carry ci would then have to be transported from logical position i − 1, which is itself layout sensitive. We instead compute exclusive prefixes. Let Si be the local carry-transition state and let Ei be the composition of S0 , . . . , Si−1 . Then ci = FEi (0),
ci+1 = FSi (ci ),
di = zi + ci − B · ci+1 .
(10)
The exclusive scan outputs the prefix transition Ei ; the carry-in, carry-out, and corrected digit are then evaluated slotwise. No final logical-predecessor shift or other cross-slot communication is required. The same exclusive-prefix mechanism gives borrow propagation and thereby supports comparison and conditional subtraction. With the fully occupied digit-major interleaving Φ(r, i) = r + g · revm (i),
(11)
all g packed integers execute level d with one physical rotation by g · 2m−d−1 , so batching does not multiply the number of scan rotations.
3
Contributions. The paper makes five contributions. 1. A packed-rotation model and exact lower bounds. We formalize ordered, possibly noncommutative prefix computation with counted cyclic rotations and prove the global bounds D, R ≥ m. 2. A rotation-optimal replicated scan. We give an inclusive and exclusive bit-reversed scan attaining D = R = m with two live states and at most 2 · m − 1 packed monoid compositions. The central sibling-copy lemma explains why one directed cyclic rotation realizes both sides of a hypercube exchange. 3. 2-adic rigidity and a rotation-key frontier. We characterize the valuation profile of every m-rotation equality case, prove the direct-key product lower bound in (8), and obtain the exact frontier in (9) when K | m. 4. Layout-native radix carry and borrow. We instantiate the exclusive scan with ordered carry transitions, avoid both natural-order restoration and the final predecessor shift, and prove the corresponding segmented digit-major packing rule. 5. Implementation and end-to-end evaluation. At m = 7, the replicated implementation reduces direct bit-reversed routing from 28 to 7 rotations, lowers evaluation-key storage by 70.0%, lowers peak heap usage by 63.9%, and improves isolated scan latency by 19.9%. In a depth-5 downstream pipeline, preserving six additional modulus levels avoids one bootstrap and yields a mean paired speedup of 4.31× with a 95% confidence interval of [3.69, 4.92]. Comparison with the closest lines of work. Classical prefix networks establish logarithmic-depth constructions and size–depth trade-offs for associative operators [LF80; Har03]. Our scan uses the same broad parallel-prefix principle, but studies a different cost model: a charged operation is a global cyclic translation shared across slots, not an individual network edge. The new ingredient is the semantic-replication invariant that makes an inexact physical partner sufficient under bit reversal, together with a matching lower bound in the packed-rotation model. Cha, Park, and Lee already establish that radix-CKKS carry can be evaluated in logarithmic rounds and provide an optimized symbolic carry algebra [CPL26]. We do not claim the first logarithmic carry circuit. Our contribution is orthogonal: we preserve a bit-reversed layout, attain the exact minimum number of scan rotations in that layout, characterize all equality profiles, and formulate carry exclusively so that no final logical shift is needed. Generic rotation-key work seeks to reduce transmitted or stored evaluation keys across broad workloads [Lee+23]; our key frontier instead lower-bounds the online calls required by this specific dependency pattern. Scope and limitations. The exact rotation theorem applies to one complete cyclic domain of 2m active positions and to fully occupied equal-length interleavings for which each scan rotation preserves the object residue. Contiguous object-major segments and partially filled ciphertexts may require padding or additional masked routing. The lower bound counts online rotation invocations; it does not equate them with wall-clock latency, distinct Galois keys, hoisted key-switch decompositions, or total memory traffic. It also excludes uncounted dense transforms and treats the prefix/correction layer separately from the upstream encrypted digit-state classifier. The implementation therefore evaluates the layout-preserving scan and correction layer once encrypted carry-state symbols are available. Organization. The remainder of the paper develops the packed-rotation model, proves the depth and rotation lower bounds and equality rigidity, presents and verifies the replicated exclusive scan, derives the rotation-key frontier, and then specializes the construction to radix-CKKS carry, borrow, and segmented packing. The implementation and evaluation section then accounts for ciphertext products, levels, key material, precision, memory, and end-to-end performance against the direct and layout-restoring baselines, before the paper closes with related work and conclusions.
2
Technical Overview
This section gives the construction and proof strategy before introducing the full circuit model. The central point is that a packed rotation need not reproduce every logical edge of a classical prefix
4
network. It is sufficient to route a semantically interchangeable copy of the information required at each destination. 2.1
Why transporting the predecessor scan is expensive
Consider eight logical inputs. Three-bit reversal places them in physical slot order 0, 4, 2, 6, 1, 5, 3, 7.
(12)
A natural recursive-doubling scan combines logical predecessors at distances 1, 2, and 4. After conjugation by bit reversal, however, one logical distance need not correspond to one cyclic displacement. Under the rotation convention used in the formal model, the three rounds of the eight-slot instance require displacement sets ∆0 = {3, 4, 6},
∆1 = {2, 7},
∆2 = {1}
(mod 8).
(13)
Masks remove wraparound terms and select the destinations belonging to each class. The direct topology therefore costs 3 + 2 + 1 = 6 rotations. For n = 2m , the same borrow-chain structure produces m − t displacement classes in round t and the triangular count in (1). This cost does not follow from the prefix function itself. It follows from a stronger routing requirement imposed by the direct topology: every destination asks for the value at one exact logical predecessor. The new scan replaces that requirement with a block invariant under which many physical copies are interchangeable. 2.2
Replicate complete block aggregates
Let ⋄ denote ordered concatenation: A ⋄ X aggregates a lower logical interval represented by A followed by its adjacent upper interval represented by X. Only associativity is assumed; in particular, ⋄ need not be commutative. At level d, the scan maintains two packed states. – A(d) stores the complete aggregate of the aligned logical block of length 2d containing the current position. The same aggregate is replicated at every slot belonging to that block. – E (d) stores the exclusive ordered prefix from the beginning of that block to, but not including, the current logical position. Initially, A(0) contains the input states and E (0) contains the monoid identity. At level d, rotate only the replicated aggregate state: B (d) = Rotsd A(d) , sd = 2m−d−1 . (14) For a position in the lower child, B (d) supplies the upper-child aggregate; for a position in the upper child, it supplies the lower-child aggregate. Public masks select the two cases. Informally, the updates are lower child:
A(d+1) = A(d) ⋄ B (d) ,
E (d+1) = E (d) ,
(15)
upper child:
A(d+1) = B (d) ⋄ A(d) ,
E (d+1) = B (d) ⋄ E (d) .
(16)
The operand order always follows the logical order “lower interval, then upper interval.” The same update therefore works for arbitrary noncommutative monoids. Figure 1 shows the aggregate invariant for the physical order in (12). The rotations are 4, 2, 1. After the first level, each logical pair aggregate has two physical copies; after the second, each four-element aggregate has four copies; after the third, the complete aggregate fills the domain. In parallel, the exclusive state accumulates the complete lower child exactly when the current (m) position belongs to the upper child. After the final level, Ei is the ordered aggregate of all inputs preceding logical position i. The aggregate update is unnecessary after the final level. The scan thus uses one aggregate composition and one exclusive-prefix composition at each of the first m − 1 levels, followed by one final prefix composition: T ≤ 2 · (m − 1) + 1 = 2 · m − 1. (17) This is a count of packed monoid evaluations, not of ciphertext multiplications. A concrete carry encoding may require several encrypted products inside one monoid evaluation.
5
physical slot logical index
0 0
1 4
2 2
3 6
4 1
5 5
6 3
7 7
A(0) [0] [4] [2] [6] [1] [5] [3] [7] (1) A after Rot4 [0:1] [4:5] [2:3] [6:7] [0:1] [4:5] [2:3] [6:7] A(2) after Rot2 [0:3] [4:7] [0:3] [4:7] [0:3] [4:7] [0:3] [4:7] A(3) after Rot1 [0:7] [0:7] [0:7] [0:7] [0:7] [0:7] [0:7] [0:7] Fig. 1. Replication of complete aggregates in the eight-slot example. The notation [a:b] denotes the ordered aggregate of logical inputs a, . . . , b. Each level uses one rotation. The exclusive-prefix state, omitted from the table, is updated in parallel only for positions in the upper child.
2.3
Why one rotation supplies both siblings
The geometric reason for (14) is especially simple under bit reversal. Write a logical index at level d as i = u · 2d+1 + b · 2d + r, b ∈ {0, 1}, 0 ≤ r < 2d , (18) and set sd = 2m−d−1 . For a fixed parent block, its two children occupy physical cosets of the form C0 = {c + 2 · sd · k : 0 ≤ k < 2d },
(19) d
C1 = {c + sd + 2 · sd · k : 0 ≤ k < 2 }.
(20)
Translation by sd swaps these cosets modulo 2m . It need not map a position to the physical image of its exact XOR partner: wraparound may select a different position in the sibling coset. Exact partners are unnecessary because A(d) is constant over each child. Any source in the sibling coset carries the same complete aggregate. This is the decisive distinction between the two scans. The direct topology routes syntactically designated predecessors. The replicated topology routes semantic block values. Public replication turns one directed cyclic translation into the effect of a bidirectional hypercube exchange. 2.4
Optimality and the structure of equality
The lower-bound intuition is independent of the construction. Fix an output slot and suppose the circuit invokes rotations with offsets δ1 , . . . , δR . A dependency path either traverses or avoids each invocation, so its source displacement is a subset sum X δj (mod 2m ) for some J ⊆ {1, . . . , R}. (21) j∈J
At most 2R source displacements can reach the fixed output. The complete prefix depends on all 2m inputs, which forces R ≥ m. Binary monoid fan-in independently gives depth D ≥ m. The replicated scan meets both bounds simultaneously. Equality leaves no slack. When R = m, every subset in (21) must produce a different residue modulo 2m . The offsets consequently form a complete 2-adic basis: after reordering, there is exactly one offset of each valuation 0, 1, . . . , m − 1. (22) The formal proof evaluates the associated group-ring factorization at 2-power roots of unity. This characterizes the rotation profile of every optimal circuit, but not its entire topology; distinct circuits may realize the same valuation basis. 2.5
Trading direct keys for online rotations
The m optimal calls may use m directly supported offsets. Reducing this key set forces some scale rotations to be synthesized by repeated calls to a smaller set. If key gj is invoked cj times, a
6
Table 1. Exact online-call frontier for m = 8 and direct-key budgets dividing m. Fewer directly supported rotations reduce key material but require sequential synthesis of the omitted scales. direct keys K
8
4
2
1
minimum calls R⋆ (8, K)
8
12
30
255
dependency path may use it between zero and cj times. The resulting coefficient box contains at most K Y (cj + 1) (23) j=1 m
possible displacements. Coverage of all 2 inputs therefore requires the product in (23) to be at least 2m . When K divides m, the lower bound is attained by dividing the valuation range into K equal consecutive blocks and directly keying the first scale of each block. For example, the exact calls for m = 8 are shown in Table 1. For nondivisible K, the paper gives a sharp coefficient-counting lower bound and a balanced dyadic construction. We state exactness only when the bounds coincide; the remaining gaps are not needed for the scan or carry results. 2.6
Exclusive prefixes for carry and borrow
A radix digit induces a transition FSi : {0, 1} → {0, 1} on its incoming carry. Ordered composition is noncommutative because the lower-digit transition must act before the upper-digit transition. The exclusive scan returns the transition Ei = S0 ⋄ · · · ⋄ Si−1 .
(24)
The carry entering digit i is FEi (0). Applying the local transition Si then gives the outgoing carry, so both values required for digit correction are available without communication. An inclusive scan would give the outgoing carry directly but would leave the incoming carry at the preceding logical digit, reintroducing a layout-sensitive shift. The scan theorem concerns the prefix-and-correction layer. A concrete CKKS realization must still choose a carry-state encoding and account for ciphertext products, conjugations, rescaling, key-switch error, and level alignment. The practical comparison is therefore not “m rotations versus m · (m + 1)/2 rotations” in isolation. It is the exchange fewer rotations
←→
two live states and additional monoid work.
(25)
The evaluation will determine where this exchange improves latency, memory, and precision in a concrete backend.
3
Model and Preliminaries
This section fixes the ordered-prefix problem, the packed circuit model, and our layout conventions. The abstraction deliberately separates three resources that are often conflated in homomorphic implementations: binary monoid depth, packed monoid evaluations, and cyclic-rotation invocations. Concrete ciphertext multiplications, rescaling, and key switching refine these abstract costs in the later CKKS realization. 3.1
Ordered monoid prefixes
Let M = (M, ⋄, e) be a monoid. We assume associativity but not commutativity. The notation A⋄X always means that the logical interval represented by A precedes the adjacent interval represented by X. This operand convention remains fixed even when a concrete state representation writes function composition in the opposite syntactic order.
7
For an input sequence x0 , . . . , xn−1 ∈ M , the inclusive and exclusive ordered prefixes are Πi := x0 ⋄ x1 ⋄ · · · ⋄ xi , ( e, ◦ Πi := x0 ⋄ x1 ⋄ · · · ⋄ xi−1 ,
(26) i = 0, i > 0.
(27)
Parenthesization is immaterial by associativity, whereas the left-to-right order is part of the required output. Unless stated otherwise, the active length is n = 2m m−d
For 0 ≤ d ≤ m and 0 ≤ u < 2
for an integer m ≥ 2.
(28)
, define the aligned logical block
Bu,d := {u · 2d , . . . , (u + 1) · 2d − 1}.
(29)
We write [a:b] for the ordered aggregate xa ⋄ · · · ⋄ xb and take [a:a − 1] = e. This interval notation is semantic: a circuit value may be stored in any physical slot and may have several identical copies. 3.2
Packed cyclic-rotation circuits
Physical slots are indexed by the cyclic group Zn . A packed monoid state is a vector V ∈ M n . The circuit is an acyclic, data-independent directed graph built from the following operations. Definition 1 (Packed prefix circuit). A packed prefix circuit may use: (i) input vectors and public constant vectors, including the all-identity vector; (ii) free fanout, copying, and public slotwise selection between already available states; (iii) a packed monoid gate Comp(U, V )[p] := U [p] ⋄ V [p]
for every p ∈ Zn ;
(30)
(iv) a cyclic rotation by offset δ ∈ Zn , ρδ (V )[p] := V [p − δ mod n].
(31)
The output must contain the requested logical prefixes in the prescribed physical layout. Public selection captures the effect of plaintext masks without assigning a monoid meaning to multiplication by zero. It does not combine two independent monoid words. The only gate that merges monoid-bearing values is the binary gate in (30). Representation-level arithmetic used to implement one such gate is accounted for separately. We use the following cost measures. – The monoid depth D is the maximum number of packed monoid gates on a directed input–output path. – The packed monoid work T is the total number of invocations of Comp. – The rotation count R is the total number of rotation-gate invocations. Rotating one state once costs one call, independently of the number of slots whose values are subsequently selected. A rotated result may be fanned out and reused without another rotation call. – The direct-key count K is the number of distinct nonzero offsets for which the evaluator holds a directly usable rotation key. If the directly keyed offsets are g1 , . . . , gK and offset gj is invoked cj times, then K X R= cj . (32) j=1
An effective rotation synthesized by several directly keyed calls is charged once for every call in that sequence. This model counts online cyclic translations, not wall-clock latency. It does not identify distinct rotations that share a hoisted decomposition, and it does not charge the internal ciphertext products of a monoid gate. It also excludes hidden data movement: a dense linear transform, arbitrary slot permutation, coefficient-to-slot transform, or bootstrapping transform may be used by a larger application, but it is not a free operation inside the prefix circuit. Any automorphism that changes slot positions must be represented by counted routing calls.
8
3.3
Bit reversal and aligned physical cosets
Bit reversal does not keep an aligned logical block contiguous in physical memory. Instead, it turns the block into a regular strided set. The reason is easiest to see at the bit level. Inside a logical block of length 2d , the lower d bits of the logical index vary, whereas the upper m − d bits are fixed. Bit reversal exchanges these roles: the varying lower logical bits become the upper d physical bits, and the fixed upper logical bits become the lower m − d physical bits. Consequently, all physical slots of the block have the same residue modulo 2m−d and differ only by multiples of 2m−d . This regularity is the geometric property used by the scan. To make the observation precise, write the m-bit expansion of i ∈ {0, . . . , 2m − 1} as i=
m−1 X
ij · 2 j ,
ij ∈ {0, 1}.
(33)
ij · 2m−1−j ,
(34)
j=0
The m-bit reversal permutation is revm (i) :=
m−1 X j=0
and logical position i is stored at physical slot L(i) = revm (i).
(35)
Hd := {2m−d · k : 0 ≤ k < 2d } ⊆ Z2m .
(36)
For each d, define
The set Hd is the subgroup of physical addresses whose lower m − d bits are zero. A coset c + Hd therefore fixes those lower bits to the residue c and lets the upper d bits vary. The preceding bit-level observation now becomes the exact identity L(Bu,d ) = revm−d (u) + Hd .
(37)
Indeed, if i = u · 2d + r with 0 ≤ r < 2d , then revm (u · 2d + r) = revm−d (u) + 2m−d · revd (r).
(38)
Thus an aligned logical block is not physically contiguous, but all of its slots lie in one explicitly known coset. The same bit view explains the sibling displacement. Consider a parent block of length 2d+1 . Its two children differ only in logical bit d. After reversal, this bit becomes physical bit m − d − 1, so changing the child orientation changes the physical address by sd = 2m−d−1 .
(39)
The lower d logical bits still vary inside each child and become steps of size 2m−d = 2 · sd . Hence, for a parent-dependent residue c, the two child supports have the form C0 = {c + 2 · sd · k : 0 ≤ k < 2d },
(40) d
C1 = {c + sd + 2 · sd · k : 0 ≤ k < 2 }.
(41)
Under the convention in (31), subtracting sd from an address in either child yields an address in the other child, modulo 2m . Therefore ρsd exchanges the two physical supports. It may permute positions within the sibling support rather than select the exact XOR partner. This distinction is harmless once the complete child aggregate is replicated across that support: every source copy represents the same monoid element.
9
Eight-slot example. For m = 3, the physical order is 0, 4, 2, 6, 1, 5, 3, 7. At the first level, logical pairs occupy supports such as {0, 4} and are exchanged with offset 4. At the next level, the two pair supports inside logical block [0:3] are {0, 4} and {2, 6}, separated by offset 2. At the last level, logical halves [0:3] and [4:7] occupy the even and odd physical slots, separated by offset 1. The scan rotations are therefore 4, 2, 1: each level changes exactly the physical bit that records the current logical child orientation. For public masks, define the level-d orientation bit by µd [L(i)] := id .
(42)
Thus µd = 0 selects the logically lower child and µd = 1 selects the logically upper child, even though their slots are interleaved in physical order. Fully occupied digit-major interleaving. The same geometry executes g independent scans in one cyclic domain. Let 0 ≤ r < g identify an object and let 0 ≤ i < n identify a digit. The layout Φ(r, i) := r + g · revm (i)
(mod g · n)
(43)
fills all g · n slots. A level-d sibling exchange uses offset g · sd = g · 2m−d−1 .
(44)
This offset preserves the residue modulo g, so every object executes the same scan level independently. The statement requires a complete cyclic domain, or equivalent identity padding. It does not automatically cover partially filled or object-major contiguous layouts, where wraparound can cross object boundaries. 3.4
A representation boundary for coordinatewise products
The prefix theorem concerns public layouts, not arbitrary encrypted linear representations. The following elementary proposition records why permutations and public coordinate scalings form the natural boundary for a generic coordinatewise product. Let F be a field and define cmul(x, y)j := xj · yj . (45) Proposition 1 (Monomial representation boundary). Let E ∈ GLn (F). Suppose there exists an invertible diagonal matrix Λ such that, for all x, y ∈ Fn , E · cmul(x, y) = Λ · cmul(E · x, E · y).
(46)
Then E is monomial: E = D · P for an invertible diagonal matrix D and a permutation matrix P . Conversely, every such E satisfies (46) with Λ = D−1 . Proof. Fix a row a = (a0 , . . . , an−1 ) of E, and let λ ̸= 0 be the corresponding diagonal entry of Λ. Comparing the coefficient of xj · yk for j = ̸ k in (46) gives λ · aj · ak = 0. Hence every row of E contains at most one nonzero entry. Invertibility forces exactly one nonzero entry in every row and every column, so E = D · P . For the converse, D−1 · cmul(D · P · x, D · P · y) = D · P · cmul(x, y) = E · cmul(x, y), which proves the claim. The proposition does not rule out useful mixing transforms. It says that an arbitrary invertible mixing transform cannot preserve a generic coordinatewise product through only coordinatewise arithmetic and public scale correction. This paper therefore analyzes layout permutations explicitly and treats additional linear transforms as separately counted operations.
10
3.5
Carry transitions as an ordered monoid
We recall the transition semantics used by radix carry constructions [CPL26]. Fix a radix B ≥ 2. Consider a provisional digit zi ∈ {0, . . . , 2 · B − 2} (47) and an incoming carry c ∈ {0, 1}. The digit induces the transition zi + c Fzi (c) := . B
(48)
It is one of the three monotone Boolean maps K(c) = 0
if 0 ≤ zi ≤ B − 2,
(49)
P(c) = c
if zi = B − 1,
(50)
G(c) = 1
if B ≤ zi ≤ 2 · B − 2.
(51)
For a lower interval state A followed by an adjacent upper interval state X, ordered concatenation represents function composition in the order FA⋄X = FX ◦ FA .
(52)
Associativity of ⋄ follows immediately from associativity of function composition. The identity is the propagate map e(c) = c. For algebraic reasoning, a transition may be represented by a homogeneous affine state γ+p·c S = (p, γ, h), FS (c) = . (53) h The three Boolean transitions have representatives K = (0, 0, 1),
P = (1, 0, 1),
G = (0, 1, 1).
(54)
If A = (pA , γA , hA ) is lower and X = (pX , γX , hX ) is upper, then A ⋄ X = pX · pA , γX · hA + pX · γA , hX · hA .
(55)
Equation (55) is associative because it represents (52). Multiplying all three coordinates by a common nonzero scalar does not change the represented transition. Let Si be the state of digit i, and let the exclusive state be ( e, i = 0, Ei := (56) S0 ⋄ · · · ⋄ Si−1 , i > 0. Then the incoming carry, outgoing carry, and corrected digit are evaluated slotwise as ci = FEi (0),
ci+1 = FSi (ci ),
di = zi + ci − B · ci+1 .
(57)
The scan is responsible for producing Ei ; the three evaluations in (57) require no further cross-slot routing. A borrow transition is obtained analogously by mapping an incoming borrow to the outgoing borrow. The same ordered-prefix circuit therefore applies to borrow propagation, comparison through the final borrow, and conditional subtraction. The later radix-CKKS instantiation distinguishes this abstract transition monoid from the ciphertext operations used by a concrete encoding.
4
Lower Bounds and Rigidity
This section establishes the optimality statements used throughout the paper. The argument has three layers. First, binary monoid gates limit how rapidly one value can acquire new dependencies. Second, after expanding a packed circuit into slot-labelled nodes, every input–output dependency path acquires a physical displacement equal to a subset sum of the invoked rotation offsets. Third, equality in this counting argument forces those offsets to form a complete 2-adic basis. We then return to the direct transported-predecessor topology and determine its larger triangular cost. The global results use only the circuit model of Definition 1. They permit arbitrary helper vectors, fanout, public masks, branching, recomputation, and reuse of rotated states. They count online cyclic-rotation invocations, not wall-clock time or the number of distinct rotation keys.
11
4.1
Dependency growth and monoid depth
For a circuit node and a fixed physical slot, its dependency set is the set of input monoid elements whose values can affect that slot. A public constant has the empty dependency set. Copying and rotation preserve its cardinality, while public slotwise selection chooses one already available value at the considered slot. The only operation that merges two monoid-bearing dependency sets is the binary packed monoid gate. Lemma 1 (Binary dependency growth). A value at monoid depth at most d depends on at most 2d input monoid elements. Proof. We prove the claim by induction over the circuit in topological order. At monoid depth zero, a slot contains either one input value or a public constant, and therefore depends on at most one input, which equals 20 . Copying, rotation, and public selection do not merge two dependency sets, so they preserve the claimed bound. Consider now a packed monoid gate with input depths d0 and d1 . At a fixed slot, let the two input dependency sets be S0 and S1 . By the induction hypothesis, |S0 | ≤ 2d0
and
|S1 | ≤ 2d1 .
The output dependency set is contained in S0 ∪ S1 , so |S0 ∪ S1 | ≤ |S0 | + |S1 | ≤ 2d0 + 2d1 ≤ 2 · 2max{d0 ,d1 } = 21+max{d0 ,d1 } . The output depth is 1 + max{d0 , d1 }, which proves the induction step. Theorem 1 (Depth lower bound). Let n = 2m with m ≥ 2. Every packed circuit computing all inclusive or all exclusive ordered prefixes has monoid depth D ≥ m. The same bound holds for any circuit producing one value that depends on all n inputs. Proof. For an inclusive scan, the output at logical position n − 1 is x0 ⋄ · · · ⋄ xn−1 and therefore depends on all n = 2m inputs. By Lemma 1, a depth-D output can depend on at most 2D inputs. Hence 2D ≥ 2m , which implies D ≥ m. For an exclusive scan, the output at logical position n − 1 is x0 ⋄ · · · ⋄ xn−2 and depends on 2m − 1 inputs. If D ≤ m − 1, then Lemma 1 would give at most 2m−1 dependencies. Since m ≥ 2 implies 2m−1 < 2m − 1, this is impossible. Thus D ≥ m also for the exclusive scan. The final statement follows from the inclusive argument whenever the specified output depends on all n inputs. 4.2
A global rotation lower bound
The next argument tracks physical displacement rather than monoid depth. Let the circuit contain R rotation gates, listed in a topological order, with offsets δ1 , . . . , δR ∈ Zn . Repeated offsets are listed repeatedly because the cost measure counts gate invocations. Lemma 2 (Subset-displacement bound). Fix an output slot p ∈ Zn . If the input at slot q ∈ Zn can affect that output, then X p−q ≡ δj (mod n) (58) j∈J
for some subset J ⊆ {1, . . . , R}. Consequently, at most 2R distinct input slots can affect one fixed output slot.
12
Proof. Expand every packed circuit node into n slot-labelled nodes. A local gate has edges only between nodes carrying the same slot label. Under the rotation convention of (31), the slot-r input of a gate ρδj is connected to its slot-(r + δj ) output. Thus crossing that gate increases the slot label by δj modulo n. If input slot q affects output slot p, the expanded dependency graph contains a directed path from q to p. Let J be the set of rotation-gate invocations crossed by this path. The circuit is acyclic, so a path cannot cross the same gate invocation twice. All local edges preserve the slot label, while each crossed rotation gate contributes its offset. Telescoping the successive slot labels along the path therefore gives X p≡q+ δj (mod n), j∈J
which is (58). There are 2R subsets of the R gate invocations. Different subsets may produce the same residue, but no additional displacement can arise. Therefore at most 2R input-slot displacements, and hence at most 2R input slots, can reach a fixed output slot. Theorem 2 (Global rotation lower bound). Let n = 2m with m ≥ 2. Every packed circuit computing all inclusive or all exclusive ordered prefixes requires R≥m cyclic-rotation invocations. The same bound holds whenever one output depends on all n inputs. Proof. For an inclusive scan, the output at logical position n − 1 depends on all 2m input slots. By Lemma 2, one fixed output can have at most 2R input-slot dependencies, and hence 2R ≥ 2m . Taking binary logarithms gives R ≥ m. For an exclusive scan, the output at logical position n − 1 depends on 2m − 1 distinct input slots. If R ≤ m − 1, then 2R ≤ 2m−1 < 2m − 1, contradicting Lemma 2. Therefore R ≥ m. If a specified output depends on all n inputs, the first counting argument applies directly. The proof does not assume an interval normal form, fixed predecessor shifts, one live state, or any particular placement of intermediate aggregates. It also remains valid when one rotated state is reused by several later gates. It would cease to apply only if additional uncounted operations were allowed to move dependencies between slots. 4.3
Equality rigidity and complete two-adic bases
The counting argument leaves no slack when an output depending on all slots is obtained with exactly m rotations. For a nonzero residue δ ∈ Z2m , let ν2 (δ) denote the 2-adic valuation of its least nonnegative integer representative. Lemma 3 (Complete two-adic basis). Let δ0 , . . . , δm−1 ∈ Z2m . The subset-sum map φ : {0, 1}m −→ Z2m ,
φ(b0 , . . . , bm−1 ) =
m−1 X
bj · δ j
(59)
j=0
is bijective if and only if, after reordering the offsets, ν2 (δj ) = j
for every 0 ≤ j < m.
(60)
Proof. Choose the representatives of the δj in {0, . . . , 2m − 1}. Q Necessity. Assume that φ is bijective. Expanding the product j (1 + X δj ) produces one m monomial for each subset of the offsets. In the quotient by X 2 − 1, exponents are reduced modulo 2m . Bijectivity says that every residue occurs as a subset sum exactly once, and therefore m−1 Y
m 1 + X δj = 1 + X + · · · + X 2 −1
j=0
13
m
in Z[X]/(X 2 − 1).
(61)
Fix k ∈ {0, . . . , m − 1} and let ζ be a primitive 2k+1 -st root of unity. Since 2k+1 divides 2m , m one has ζ 2 = 1; moreover ζ ̸= 1. Evaluation at ζ is well-defined on the quotient ring, and the geometric series on the right-hand side satisfies m
ζ2 − 1 = 0. ζ −1
m
1 + ζ + · · · + ζ 2 −1 =
Hence the product on the left vanishes in C, so at least one factor vanishes. For some j, 1 + ζ δj = 0,
that is,
ζ δj = −1. k
In the cyclic group generated by ζ, the unique element of order two is ζ 2 = −1. Consequently δj ≡ 2k
(mod 2k+1 ),
which is equivalent to ν2 (δj ) = k. Thus every valuation k ∈ {0, . . . , m − 1} occurs among the m offsets. There are exactly m offsets, so each valuation occurs exactly once. In particular, no offset is zero. Sufficiency. Conversely, reorder the offsets and choose integer representatives δj = 2j · uj ,
uj odd.
Suppose two binary vectors have the same image under φ. Subtracting the corresponding subset sums yields m−1 X εj · δj ≡ 0 (mod 2m ), εj ∈ {−1, 0, 1}. (62) j=0
If the vectors differ, let t be the least index for which εt = ̸ 0. Every term in (62) is divisible by 2t , t m−t so division by 2 gives a congruence modulo 2 . Reducing that congruence modulo 2 leaves εt · u t ≡ 0
(mod 2),
because every term with index greater than t contains an additional factor of two. But εt ∈ {−1, 1} and ut is odd, so the left-hand side is odd, a contradiction. The two binary vectors are therefore equal. Thus φ is injective. Its domain and codomain both contain 2m elements, so it is bijective. Corollary 1 (Rigidity of rotation-optimal equality). Suppose a packed circuit uses exactly R = m rotation invocations and produces one output depending on all 2m input slots. If the invoked offsets are δ0 , . . . , δm−1 , then, after reordering, ν2 (δj ) = j
for 0 ≤ j < m.
In particular, every offset is nonzero, the offsets are pairwise distinct, and their subset sums cover every residue exactly once. Proof. Fix the physical output slot p. As the source slot q ranges over Z2m , the displacement p − q ranges over every residue of Z2m exactly once. By hypothesis, every source affects the output, so Lemma 2 associates each of these residues with a subset of the m invoked offsets. Therefore the subset-sum map in (59) is surjective. Its domain and codomain both have cardinality 2m , so it is bijective. The valuation statement follows from Lemma 3. Distinct valuations imply that the offsets are nonzero and pairwise distinct, while bijectivity gives the final subset-sum claim. Corollary 1 characterizes the offset profile, not the complete topology of an optimal circuit. The canonical powers of two are only one representative: every family δj = 2j · uj with odd uj has the same subset-sum property. Whether such a family is embedded into a correct ordered-prefix topology is a separate constructive question.
14
4.4
Exact cost of transported predecessors
The global lower bound is linear, but the natural recursive-doubling scan is more expensive when each logical predecessor is transported directly in the bit-reversed layout. At stage t ∈ {0, . . . , m−1}, that topology asks logical position i ≥ 2t to read the current state at i − 2t . Under the layout L(i) = revm (i), define the required physical displacement ∆t (i) := L(i) − L(i − 2t )
(mod 2m ).
(63)
One masked rotation can serve every destination having the same displacement, but destinations with different displacements require different rotated copies of the stage-input vector. Proposition 2 (Cyclic diagonals of one predecessor stage). For fixed t, the set {∆t (i) : 2t ≤ i < 2m } contains exactly m − t distinct residues. Their 2-adic valuations are 0, 1, . . . , m − t − 1. Proof. Write ir ∈ {0, 1} for bit r of i, with bit zero least significant. Because i ≥ 2t , at least one bit at position t or above is one. Let q = q(i, t) := min{r ≥ t : ir = 1}. The bits it , . . . , iq−1 are zero and iq = 1. Subtracting 2t therefore changes bit q from one to zero, changes bits t, . . . , q − 1 from zero to one, and leaves every other bit unchanged. Bit reversal sends logical bit r to physical bit m−1−r. Hence the physical difference L(i)−L(i−2t ) receives a positive contribution 2m−1−q from bit q and a negative contribution 2m−1−ℓ from each bit ℓ ∈ {t, . . . , q − 1}. Thus q−1 X
∆t (i) ≡ 2m−1−q −
2m−1−ℓ
(mod 2m )
ℓ=t
≡ 2m−1−q − 2m−t − 2m−q
(mod 2m )
≡ 3 · 2m−1−q − 2m−t
(mod 2m ) ≡ 2m−1−q · 3 − 2q−t+1 (mod 2m ).
(64)
The displayed geometric-sum identity also covers q = t, where the sum is empty. Since q − t + 1 ≥ 1, the factor 3 − 2q−t+1 is odd. Moreover m − 1 − q < m, so reduction modulo 2m does not change the exact 2-adic valuation. Therefore ν2 ∆t (i) = m − 1 − q. The formula depends on i only through q. Conversely, every q ∈ {t, . . . , m − 1} occurs, for example by choosing i = 2q . The corresponding valuations are m − t − 1, m − t − 2, . . . , 0, which are pairwise distinct. Hence there is exactly one displacement class for each such q, and the total number of classes is m − t. Corollary 2 (Triangular cost of the direct topology). The direct transported-predecessor realization of recursive doubling uses exactly Rdirect =
m−1 X
(m − t) =
t=0
m · (m + 1) 2
(65)
rotation invocations. Proof. Fix a stage t and its common stage-input vector. A rotation by offset δ presents at destination slot p the value from slot p − δ. Public masks may discard destinations, but they cannot change this source displacement. Therefore one rotated copy of the stage-input vector can serve only the
15
destinations belonging to one displacement class. By Proposition 2, the m − t nonempty classes require at least m − t rotated copies. This lower bound is attained within the direct topology: for each displacement class δ, rotate the stage-input vector by δ, retain exactly the destinations of that class with its public mask, and select the resulting masked copies slotwise. Thus stage t uses exactly m − t rotations. Summing over t = 0, . . . , m − 1 yields m−1 X
(m − t) = m + (m − 1) + · · · + 1 =
t=0
m · (m + 1) . 2
This is an exact cost for the stated direct topology, not a global lower bound. The replicated scan developed in the next section changes the invariant: it routes an interchangeable copy of a sibling aggregate instead of the syntactically designated predecessor. 4.5
Why changing the fixed shifts is insufficient
For completeness, we isolate a restricted rigidity statement explaining why a better fixed-predecessor schedule cannot remove the triangular cost. Consider a one-state scan in which stage j uses one positive logical predecessor distance sj , uniformly across all active destinations, with public masks suppressing out-of-range predecessors. Logical indices do not wrap around in this restricted model. Proposition 3 (Rigidity of minimum-depth fixed shifts). Let n = 2m . If m fixed-predecessor stages make the final position depend on all n inputs, then the multiset of logical shifts is {s0 , . . . , sm−1 } = {1, 2, 4, . . . , 2m−1 }. Consequently, every such bit-reversed direct schedule incurs the triangular rotation count in (65). Proof. Along a dependency path ending at the final logical position, stage j either keeps the current logical position or follows the predecessor edge of length sj . Since each stage is encountered at most once, the total backward logical distance of the path is a subset sum of s0 , . . . , sm−1 . To make the final position depend on every input, each distance in {0, 1, . . . , 2m − 1} must occur. There are exactly 2m subsets and exactly 2m required distances. Hence all subset sums are distinct and, as ordinary nonnegative integers, are precisely 0, 1, . . . , 2m − 1. Sort the shifts as a0 ≤ · · · ≤ am−1 . Since the smallest positive subset sum is one, a0 = 1. Assume inductively that aj = 2j for 0 ≤ j < r. The subset sums of these first r shifts are then exactly the interval {0, 1, . . . , 2r − 1}. If ar > 2r , no subset using the remaining shifts can sum to 2r , because every remaining shift is at least ar ; this would create a gap. If ar < 2r , then the singleton subset {ar } duplicates the already existing subset sum ar formed from the first r shifts; this contradicts uniqueness. Therefore ar = 2r . Induction gives the claimed multiset. The order of the stages does not affect the sum of their individual direct routing costs. A stage using logical shift 2t has exactly m − t physical displacement classes by Proposition 2. Summing these costs over t = 0, . . . , m − 1 gives the triangular count in (65). The proposition is deliberately restricted to one-state fixed-predecessor scans. It does not constrain circuits that maintain replicated aggregates, change layouts internally, or use more general helper states. The distinction between this restricted triangular cost and the global lower bound R ≥ m is precisely what motivates the construction of the next section.
5
Rotation-Optimal Replicated Scan
The lower bounds of Section 4 show that an ordered scan on n = 2m inputs cannot use fewer than m monoid levels or fewer than m cyclic rotations. This section gives a construction attaining both bounds simultaneously. Its central invariant differs from a transported-predecessor scan: each aligned
16
block stores its complete aggregate at every physical slot of the block. A destination therefore does not need the copy held by one designated logical partner. Any copy from the sibling block is semantically interchangeable, and the bit-reversed coset geometry supplies such a copy with one rotation per level. We present the exclusive form because it gives each radix digit its carry-in without a final predecessor shift. The inclusive variant follows from the same recurrence with a different initialization. 5.1
Replicated aggregate and local-prefix states
For 0 ≤ d ≤ m and logical position i, let βd (i) := 2d ·
i 2d
(66)
be the first index of the aligned length-2d block containing i. At the beginning of level d, the scan maintains two logical views of packed state vectors: (d)
Ai
:= [βd (i):βd (i) + 2d − 1],
(d) Ei := [βd (i):i − 1].
(67) (68)
(d)
The state Ai is the aggregate of the complete aligned block, and the same monoid element is (d) replicated at every position of that block. The state Ei is the exclusive prefix from the beginning of that block to position i. In particular, it equals the identity at the first position of each block. (d) (d) The corresponding physical vectors store Ai and Ei at slot L(i) = revm (i). To keep the notation readable, all recurrence equations below are written in logical coordinates; every selection is implemented by the public physical mask µd from (42). For a bit-valued public mask µ and packed states U, V , write ( U [p], µ[p] = 0, Selµ (U, V )[p] := (69) V [p], µ[p] = 1. This operation performs no monoid composition; it only chooses between two already available values at each slot. 5.2
One rotation supplies every sibling aggregate
At level d, the two length-2d children of a length-2d+1 parent occupy the physical cosets in (40) and (41). Their separation is sd = 2m−d−1 . (70) The following lemma formalizes the semantic-copy property used by the scan. Lemma 4 (Sibling-copy lemma). Fix d ∈ {0, . . . , m − 1}. Suppose that a packed vector A(d) stores, at every logical position i, the complete aggregate of the aligned length-2d block containing i. Let B (d) := ρsd (A(d) ). (71) (d)
Then, at every logical position i, the value Bi child in the same length-2d+1 parent block.
is the complete aggregate of the sibling length-2d
Proof. Fix a parent block and let c be the residue appearing in (40) and (41). Its lower and upper child supports are C0 = {c + 2 · sd · k : 0 ≤ k < 2d }, C1 = {c + sd + 2 · sd · k : 0 ≤ k < 2d }. Under the rotation convention ρsd (A)[p] = A[p − sd mod 2m ], it suffices to prove that subtracting sd exchanges these supports.
17
Let p = c + 2 · sd · k ∈ C0 . Then p − sd = c + sd + 2 · sd · (k − 1). If k > 0, this is visibly in C1 . If k = 0, replace k − 1 by 2d − 1: the two expressions differ by 2 · sd · 2d = 2m , so they represent the same slot modulo 2m . Hence every destination in C0 reads a source in C1 . Conversely, for p = c + sd + 2 · sd · k ∈ C1 , p − sd = c + 2 · sd · k ∈ C0 . Thus the rotation exchanges the two child supports. It may permute the positions within the sibling support, but the hypothesis states that A(d) is constant on each child support and equals that child’s complete aggregate. Therefore every destination receives the required sibling aggregate. The lemma is stronger than an exact-partner statement in the way needed here: the rotated source may be a different logical position in the sibling block, but all such positions carry the same aggregate. This is what allows one directed cyclic rotation to realize the two directions of the logical sibling exchange simultaneously. 5.3
Construction
At level d, first rotate the replicated aggregate vector as in (71). For a lower-child position (id = 0), the current aggregate precedes the rotated sibling aggregate. For an upper-child position (id = 1), the rotated lower-child aggregate precedes the current aggregate. Public selection arranges these operands before one packed monoid gate: (d) UA := Selµd (A(d) , B (d) ),
(72)
(d) VA := Selµd (B (d) , A(d) ),
(73)
:= Comp(UA(d) , VA(d) ).
(74)
e(d+1)
A
For the exclusive prefix, lower-child positions keep their existing value, whereas upper-child positions prepend the complete lower-child aggregate:
E
(d) CE := Comp(B (d) , E (d) ),
(75)
(d) , CE ).
(76)
(d+1)
:= Selµd (E
(d)
The aggregate update and prefix candidate use only level-d values and can therefore be evaluated in parallel. At the last level, the complete length-2m aggregate is not needed after the prefixes are produced, so (74) is omitted. The order of Steps 2 and 3 in Fig. 2 is only presentational: both must read the old level-d states. An implementation must not overwrite A or E before all level-d operands have been formed. 5.4
Correctness
Theorem 3 (Replicated exclusive-prefix invariant). For every d ∈ {0, . . . , m} and logical position i, the conceptual recurrence in (74) and (76) satisfies (d)
= [βd (i):βd (i) + 2d − 1],
(77)
(d)
= [βd (i):i − 1].
(78)
Ai Ei In particular, after level m, (m)
Ei
= [0:i − 1] = Πi◦
for every 0 ≤ i < n.
(79)
The aggregate equation is required only through d = m − 1 by the optimized algorithm, because the final aggregate update is omitted.
18
Input: a packed vector X with X[L(i)] = xi ; the public masks µ0 , . . . , µm−1 ; and the all-identity vector e. Initialization: A ← X and E ← e. 1. For d = 0, . . . , m − 1, set sd ← 2m−d−1 and B ← ρsd (A). 2. Compute CE ← Comp(B, E) and set E ← Selµd (E, CE ). 3. If d < m − 1, set UA ← Selµd (A, B), VA ← Selµd (B, A), and update A ← Comp(UA , VA ). Output: E, where E[L(i)] = Πi◦ for every logical position i. Fig. 2. Rotation-optimal exclusive scan in bit-reversed layout. The prefix and aggregate compositions at a nonfinal level depend only on the previous level and may be evaluated in parallel.
Proof. We prove the two equations simultaneously by induction on d. For d = 0, the aligned block containing i is the singleton {i}. The initialization gives (0)
Ai
= xi = [i:i]
(0)
= e = [i:i − 1].
and Ei
Since β0 (i) = i, both invariants hold. Assume they hold at some level d < m. Fix a parent block of length 2d+1 and write its first index as b. Its lower child is [b, b + 2d − 1] and its upper child is [b + 2d , b + 2d+1 − 1]. By the induction hypothesis, A(d) stores the complete aggregate of each child at every position of that child. By Lemma 4, B (d) stores the complete sibling aggregate at every position. First suppose that i lies in the lower child, so id = 0. The induction hypothesis and the sibling-copy lemma give (d)
= [b:b + 2d − 1],
(d)
= [b + 2d :b + 2d+1 − 1].
Ai Bi
The public operand selections in (72) and (73) therefore place the lower-child aggregate first and the upper-child aggregate second. Associativity and the interval convention imply e(d+1) = [b:b + 2d − 1] ⋄ [b + 2d :b + 2d+1 − 1] = [b:b + 2d+1 − 1]. A i For the prefix update, µd [L(i)] = 0, so (d+1)
Ei
(d)
= Ei
= [b:i − 1].
Because the parent and lower child have the same first index b, these are exactly the two level-(d + 1) invariants. Now suppose that i lies in the upper child, so id = 1. Then (d)
= [b:b + 2d − 1],
(d)
= [b + 2d :b + 2d+1 − 1],
(d)
= [b + 2d :i − 1].
Bi
Ai Ei
The selected aggregate operands again appear in logical order, and hence e(d+1) = [b:b + 2d − 1] ⋄ [b + 2d :b + 2d+1 − 1] = [b:b + 2d+1 − 1]. A i (d)
(d)
Since µd [L(i)] = 1, the prefix update selects CE,i = Bi (d+1)
Ei
(d)
⋄ Ei . Therefore
= [b:b + 2d − 1] ⋄ [b + 2d :i − 1] = [b:i − 1].
19
This is the exclusive prefix from the beginning of the parent block to i. Thus both invariants hold at level d + 1 for both child orientations. At d = m, the unique aligned block begins at βm (i) = 0. Substituting this value into (78) gives (m) Ei = [0:i − 1] = Πi◦ , as claimed. Inclusive variant. Initialize a prefix state P (0) ← X instead of E (0) ← e, and apply the same update P (d+1) = Selµd P (d) , Comp(B (d) , P (d) ) . (m)
The identical induction, with local interval [βd (i):i] in place of [βd (i):i − 1], gives Pi operation counts are unchanged. 5.5
= Πi . The
Complexity and exact optimality
Theorem 4 (Cost of the replicated scan). For n = 2m with m ≥ 2, the exclusive or inclusive replicated scan uses D = m, R = m, T = 2 · m − 1. (80) It maintains two persistent monoid-state vectors, together with transient rotated and composition results. Proof. There is exactly one invocation of ρsd at each of the m levels, so R = m. e(d+1) and one forms At every nonfinal level d ∈ {0, . . . , m − 2}, one packed monoid gate forms A (d) CE . These two gates use only level-d inputs and may be evaluated in parallel. At the final level, (m−1) only CE is needed. Hence T = 2 · (m − 1) + 1 = 2 · m − 1. Along every input–output path, at most one monoid gate is crossed per level, because the aggregate and prefix gates of the same level are parallel rather than sequential. Thus D ≤ m. For the final logical position i = n − 1, every bit id equals one, so its prefix state is updated by a monoid gate at every level. The resulting path has depth m, and therefore D = m. The algorithm carries the current aggregate vector A and prefix vector E (or P ) from one level to the next. The rotated sibling vector and the two composition outputs need only be transient, although an implementation may retain additional buffers to avoid destructive updates. Corollary 3 (Simultaneous depth and rotation optimality). In the packed circuit model of Definition 1, for n = 2m and m ≥ 2, the minimum monoid depth and minimum rotation count for all ordered inclusive or exclusive prefixes satisfy D⋆ (m) = R⋆ (m) = m.
(81)
Proof. The construction in Theorem 4 attains D = R = m. The matching lower bounds are Theorems 1 and 2. Therefore neither resource can be reduced in the stated model. The result is an exact statement about monoid depth and counted online rotations, not a claim that the replicated scan is faster for every homomorphic backend. Relative to the direct transported-predecessor scan, it reduces rotations from m · (m + 1)/2 to m, but increases packed monoid work from m to 2 · m − 1 and requires a second persistent state. The concrete crossover depends on the ciphertext cost of one monoid composition, key switching, scale management, and available memory; these quantities are evaluated only after the carry representation is fixed.
6
Rotation-Key Frontier
The optimal scan of Section 5 uses one effective rotation at each of the m two-adic scales. If the evaluator stores a direct rotation key for every required offset, these effective rotations cost exactly m online calls. Reducing the directly supported key set saves evaluation-key material, but an omitted
20
scale must then be synthesized by a sequence of directly keyed rotations. This section determines the resulting lower and upper bounds and proves an exact frontier whenever they coincide. The distinction between directly keyed offsets and online calls is essential. A key budget K limits the number of distinct offsets that can be invoked directly; it does not limit how often those offsets may be used. The theorem below counts every invocation, including each call in a sequence synthesizing a larger effective rotation. It is therefore a program-specific online-call bound, rather than a byte-level estimate of backend key storage. Generic systems may further trade transmitted, stored, or derived evaluation keys against runtime [Lee+23]; any offset that is directly available to the online evaluator belongs to the effective key set counted here. ⋆ Throughout this section, let 1 ≤ K ≤ m. We write Rpref (m, K) for the minimum number of online cyclic-rotation invocations among packed circuits that compute all ordered prefixes on n = 2m slots while using at most K distinct directly keyed nonzero offsets. The lower bounds below do not assume minimum monoid depth; the matching constructions retain the optimal depth m. 6.1
Coefficient-box lower bound
Suppose the directly keyed offsets are g1 , . . . , gK ∈ Z2m , and offset gj is invoked cj times. We may pad a smaller key set with zero invocation counts, so the notation also covers circuits using fewer than K keys. Theorem 5 (Direct-key product bound). If one output depends on all 2m input slots, then K Y
(cj + 1) ≥ 2m .
(82)
j=1
Consequently, every circuit computing all inclusive or all exclusive prefixes satisfies (82). Proof. Fix an output slot p. Expand the packed circuit into the slot-labelled acyclic graph used in the proof of Lemma 2. Along a dependency path ending at p, let aj be the number of crossed rotation-gate invocations whose directly keyed offset is gj . Since the complete circuit contains exactly cj such invocations, 0 ≤ aj ≤ cj
for every 1 ≤ j ≤ K.
(83)
Local edges preserve the physical slot label, while every crossed invocation of key gj adds gj . Therefore the source displacement of the path is of the form K X
aj · gj
(mod 2m ).
(84)
j=1
The coefficient vector (a1 , . . . , aK ) belongs to the box K Y
{0, . . . , cj },
(85)
j=1
which has cardinality
QK
j=1 (cj + 1). Distinct coefficient vectors may yield the same residue in (84), QK but no path can yield a displacement outside this image. Hence at most j=1 (cj + 1) distinct input m
slots can affect the fixed output. If that output depends on all 2 inputs, the image must contain every residue, proving (82). For an inclusive scan, the last logical prefix depends on all inputs. For an exclusive scan with m ≥ 2, the last prefix depends on 2m − 1 inputs. If the product in (82) were smaller than 2m , then, because it is an integer product of positive integers, the strongest possible conclusion for the exclusive output would only be a bound by 2m − 1. However, the complete carry-out or the inclusive aggregate obtained locally from the final exclusive state and the last input depends on all 2m inputs and uses no additional rotation. Applying the first part to this locally derived output proves the same product bound for the exclusive scan.
21
The product bound can be converted into the strongest lower bound depending only on m and K. The required optimization is discrete: for a fixed number of calls, the coefficient box is largest when the invocation counts are as balanced as possible. Lemma 5 (Balanced coefficient box). Let c1 , . . . , cK ∈ Z≥0 satisfy K X
cj = R.
(86)
j=1
Write R = a · K + b,
0 ≤ b < K.
(87)
Then K Y
(cj + 1) ≤ (a + 1)K−b · (a + 2)b .
(88)
j=1
Equality holds if and only if, up to reordering, K − b counts equal a and b counts equal a + 1. Proof. Suppose two counts satisfy cu ≥ cv + 2. Move one invocation from the larger count to the smaller one. The factors involving these two counts change from (cu + 1) · (cv + 1)
(89)
cu · (cv + 2).
(90)
cu · (cv + 2) − (cu + 1) · (cv + 1) = cu − cv − 1
(91)
to Their difference is
> 0.
(92)
Thus any pair of counts differing by at least two can be balanced while strictly increasing the product and preserving the sum. Repeating this operation terminates only when all counts differ by at most one. Under (87), the unique multiset with that property contains K − b copies of a and b copies of a + 1. Substituting these values yields (88). Strict increase at every nontrivial balancing step also proves the equality characterization. Theorem 6 (Exact integer counting lower bound). Every packed prefix circuit using at most K directly keyed offsets satisfies ⋆ Rpref (m, K) ≥ L(m, K), (93) where L(m, K) :=
min
a∈Z≥0 , 0≤b<K
a · K + b : (a + 1)K−b · (a + 2)b ≥ 2m .
(94)
In particular, l m ⋆ Rpref (m, K) ≥ K · 2m/K − 1 .
(95)
Proof. Let a circuit use R calls and write R = a · K + b as in (87). By Theorem 5, its invocation counts satisfy K Y 2m ≤ (cj + 1). (96) j=1
By Lemma 5, K Y
(cj + 1) ≤ (a + 1)K−b · (a + 2)b .
j=1
Hence the pair (a, b) associated with R is feasible in (94), and therefore R ≥ L(m, K).
22
(97)
For (95), apply the arithmetic–geometric mean inequality to the K positive integers cj + 1:
K Y
1/K ≤
(cj + 1)
j=1
K 1 X R · (cj + 1) = 1 + . K j=1 K
(98)
Combining (82) and (98) gives 2m/K ≤ 1 + R/K, and therefore R ≥ K · (2m/K − 1). Since R is an integer, taking the ceiling gives (95). 6.2
Balanced dyadic construction
The lower bound is matched in many parameter regimes by grouping consecutive two-adic scales. Write m = q · K + s, 0 ≤ s < K. (99) Choose K − s group lengths equal to q and s group lengths equal to q + 1. Arrange these groups consecutively so that they partition the valuation set {0, . . . , m−1}. If one group begins at valuation v and has length α, store a direct key only for offset 2v . The scan level at valuation v +r, where 0 ≤ r < α, requires the effective rotation 2v+r . Repeating the directly keyed rotation 2v exactly 2r times synthesizes this offset, because cyclic rotations compose additively: ρ2v ◦ · · · ◦ ρ2v = ρ2r ·2v = ρ2v+r . (100) | {z } 2r calls
The total number of calls contributed by this group is therefore α−1 X
2r = 2α − 1.
(101)
r=0
Proposition 4 (Balanced dyadic upper bound). For m = q · K + s with 0 ≤ s < K, the replicated scan can be evaluated with K directly keyed offsets, monoid depth m, and U (m, K) := (K − s) · (2q − 1) + s · (2q+1 − 1)
(102)
online rotation calls. Consequently, ⋆ Rpref (m, K) ≤ U (m, K).
(103)
Proof. Partition the m scan valuations into the consecutive groups described above and directly key the first offset of each group. By (100), every effective scale rotation required by the scan can be synthesized using only its group’s direct key. A group of length q costs 2q − 1 calls by (101), and a group of length q + 1 costs 2q+1 − 1 calls. Summing over K − s short groups and s long groups gives (102). Replacing one effective rotation by a sequence of rotations changes only the routing performed before that scan level. It does not add a monoid gate to any dependency path. Therefore the construction retains monoid depth m and the correctness invariant of Theorem 3. It uses exactly one directly keyed offset per group, hence at most K direct keys. Combining the lower and upper bounds gives the general proved frontier sandwich ⋆ L(m, K) ≤ Rpref (m, K) ≤ U (m, K).
(104)
Corollary 4 (Exact coincidence cases). If L(m, K) = U (m, K), then ⋆ Rpref (m, K) = L(m, K) = U (m, K).
Proof. The result follows immediately by substituting the assumed equality into (104).
23
(105)
Table 2. Representative direct-key parameter pairs. Equality of L and U proves the exact prefix frontier. A strict gap records only the current proved interval, not evidence of suboptimality of the dyadic construction.
6.3
m
K
L(m, K)
U (m, K)
5 8 8 7 10
3 3 5 2 3
7 17 11 21 28
7 17 11 22 29
proved status exact exact exact ⋆ 21 ≤ Rpref ≤ 22 ⋆ 28 ≤ Rpref ≤ 29
Exact divisible frontier and equality rigidity
When K divides m, the smooth lower bound in (95) is integral and exactly matches the dyadic construction. Theorem 7 (Exact frontier for K | m). Assume K | m and set α :=
m . K
(106)
Then ⋆ Rpref (m, K) = K · 2α − 1 = K · 2m/K − 1 .
(107)
The value is attained at monoid depth m by directly keying the offsets 20·α , 21·α , . . . , 2(K−1)·α .
(108)
⋆ Rpref (m, K) ≥ K · 2m/K − 1 = K · 2α − 1 .
(109)
Proof. The lower bound (95) gives
In (99), divisibility means q = α and s = 0. The upper bound of Proposition 4 therefore becomes U (m, K) = K · (2α − 1).
(110)
The construction partitions the valuation range into K consecutive groups of length α and uses exactly the key set in (108). The matching lower and upper bounds prove (107). The equality case determines not only the number of calls, but also the valuation profile of every optimal direct-key set. Theorem 8 (Mixed-radix two-adic rigidity). Let K | m, let α = m/K, and suppose a packed circuit uses at most K directly keyed offsets and exactly R = K · (2α − 1)
(111)
rotation calls to produce one output depending on all 2m inputs. Then: 1. exactly K direct keys are used, and each is invoked cj = 2α − 1
(112)
times; 2. after reordering the directly keyed offsets, ν2 (gj ) = j · α
for 0 ≤ j < K.
Thus every optimal key set begins one complete block of α consecutive two-adic scales.
24
(113)
Proof. Pad the circuit’s key set to K offsets by assigning zero invocation counts to any unused positions. By Theorem 5, K Y 2m ≤ (cj + 1). (114) j=1
On the other hand, the arithmetic–geometric mean inequality and (111) give K K K Y X 1 (cj + 1) ≤ · (cj + 1) K j=1 j=1 =
K · (2α − 1) 1+ K
(115)
K
= 2α·K = 2m .
(116) (117)
Hence equality holds throughout. Equality in arithmetic–geometric mean forces all cj + 1 to be equal to 2α , proving (112). In particular, no padded count is zero, so exactly K keys are used. Fix an output slot depending on all inputs. A dependency path determines a coefficient vector (a0 , . . . , aK−1 ) ∈ {0, . . . , 2α − 1}K , (118) P m and the associated source displacement is j aj · gj modulo 2 . Every residue must occur because the output depends on all input slots. More precisely, the coefficient vectors realized by dependency paths form a subset of the box in (118), and their image already contains all 2m residues. The complete box has cardinality (2α )K = 2α·K = 2m , (119) which equals the codomain size. The path-realized subset must therefore be the entire box, and the m coefficient map from the box to Z2m is bijective. Equivalently, in the quotient ring Z[X]/(X 2 − 1), ! 2m −1 α K−1 −1 Y 2X X a·gj X = Xr. (120) j=0
a=0
r=0
r
Indeed, the coefficient of X on the left counts coefficient vectors mapping to residue r, and bijectivity makes every such coefficient equal to one. For 0 ≤ k < m, let ζk be a primitive 2k+1 -st root of unity. It is also a 2m -th root of unity, and evaluating the right-hand side of (120) gives zero. Hence, for every k, at least one geometric factor on the left vanishes. Let vj = ν2 (gj ). We claim that α 2X −1
a·gj
ζk
=0
⇐⇒
vj ≤ k < vj + α.
(121)
a=0 g
To prove the claim, set z = ζk j . If vj > k, then z = 1 and the sum equals 2α , so it does not vanish. α If vj ≤ k, then z = ̸ 1 and z has order 2k+1−vj . The geometric sum vanishes exactly when z 2 = 1, which is equivalent to 2k+1−vj | 2α , or k < vj + α. This proves (121). Thus the K integer intervals Ij := {vj , vj + 1, . . . , vj + α − 1}
(122)
cover every valuation k ∈ {0, . . . , m − 1}. Each interval has exactly α elements, so the total number of interval positions counted with multiplicity is K · α = m.
(123)
Covering a set of m valuations with total multiplicity m leaves no room for overlap or for positions outside {0, . . . , m − 1}. Consequently, the Ij are pairwise disjoint and partition the complete valuation range. After ordering them by their first elements, the only partition into consecutive intervals of common length α is {0, . . . , α − 1}, {α, . . . , 2 · α − 1}, . . . , {(K − 1) · α, . . . , K · α − 1}. Their starting valuations are therefore 0, α, . . . , (K − 1) · α, proving (113).
25
(124)
6.4
Nondivisible residual and scope
For K ∤ m, the proved statement is exactly the sandwich in (104). The bounds coincide for many nondivisible pairs, as illustrated in Table 2, but not for all of them. For example, ⋆ 21 ≤ Rpref (7, 2) ≤ 22,
⋆ 28 ≤ Rpref (10, 3) ≤ 29.
(125)
The lower endpoint certifies only that enough coefficient combinations are available to reach every displacement. It does not by itself enforce the causal order, all-output semantics, or the m successive sibling exchanges of an ordered prefix scan. Conversely, the upper endpoint is an explicit minimum-depth scan, not a claim of optimality when L(m, K) < U (m, K). The remaining nondivisible gaps are therefore left open. Computational searches may support the balanced dyadic construction for selected parameters, but such evidence is not used in any theorem of this paper. The radix carry and borrow instantiations in the next section may select a budget dividing m, where the direct-key frontier and its equality structure are fully determined by Theorems 7 and 8.
7
Radix-CKKS Instantiation
This section specializes the abstract exclusive scan to radix carry and borrow. The algebraic statements are exact: they assume that every provisional digit is classified into the correct transition state and that the resulting state arithmetic is decoded without error. A concrete CKKS ciphertext carries approximate values, so the numerical conditions under which classification and rounding recover these exact states are deferred to the implementation and precision analysis. This separation is useful because the scan topology is independent of the selected bootstrapping and state-classification backend. 7.1
A one-ciphertext carry-state encoding
The transition monoid from Section 3.5 has only three elements: kill, propagate, and generate. Following the compressed symbolic realization used for logarithmic radix carry [CPL26], encode them by 1 σ(K) = 0, σ(P) = , σ(G) = i, (126) 2 where i2 = −1. If x encodes a lower interval and y encodes an adjacent upper interval, define x ⊛ y := y + (y + y) · (x − y).
(127)
The operand order matches the convention of (52): the lower transition acts first. Proposition 5 (Symbolic transition isomorphism). For all transition states A, X ∈ {K, P, G}, σ(A ⋄ X) = σ(A) ⊛ σ(X).
(128)
The identity symbol is 1/2. One packed evaluation of (127) uses one ciphertext–ciphertext multiplication, additions, and one complex conjugation when the state is stored in one CKKS ciphertext. Proof. Let x = σ(A) and y = σ(X). The result is determined by the upper state X. If X = K, then y = 0 and x ⊛ y = 0 = σ(K); an upper kill state discards the lower transition. If X = P, then y = 1/2 = y, and therefore 1 1 = x; (129) x⊛y = +1· x− 2 2 this is exactly the identity action of an upper propagate state. Finally, if X = G, then y = i and y + y = 0, so x ⊛ y = i = σ(G); an upper generate state also discards the lower transition. These three cases are precisely the composition table of the transition monoid. The propagate symbol 1/2 is therefore its identity. Equation (127) contains one product of the two ciphertext-dependent quantities y + y and x − y. All remaining operations are linear, apart from the conjugation automorphism.
26
For a provisional digit z ∈ {0, . . . , 2 · B − 2}, define the exact state classifier 0, 0 ≤ z ≤ B − 2, χB (z) := 12 , z = B − 1, i, B ≤ z ≤ 2 · B − 2.
(130)
Thus χB (z) = σ(Fz ). In a concrete discrete-CKKS realization, χB is evaluated slotwise by a functional bootstrap or another encrypted classifier. The prefix circuit starts after this classification step. Two linear functions recover the generate and propagate indicators of a symbol x ∈ {0, 1/2, i}: gen(x) :=
x−x , 2·i
prop(x) := x + x.
(131)
They take values in {0, 1} and satisfy Fx (c) = gen(x) + prop(x) · c
for c ∈ {0, 1}.
(132)
Here Fx denotes the transition represented by x. In particular, Fx (0) = gen(x). 7.2
Exclusive carry and canonical digits
Let z0 , . . . , zn−1 be provisional radix-B digits satisfying 0 ≤ zi ≤ 2 · B − 2,
n = 2m ,
and set c0 = 0. Sequential carry propagation is zi + ci ci+1 := , di := zi + ci − B · ci+1 . B
(133)
(134)
The range in (133) ensures that every carry is binary. Let Si be the transition state classified from zi , and let Ei = S0 ⋄ · · · ⋄ Si−1 be its exclusive prefix, with E0 = e. The replicated scan of Section 5 returns all Ei directly in bit-reversed order. Theorem 9 (Exact exclusive carry). Assume that the state classifier in (130) is correct. For every i ∈ {0, . . . , n − 1}, define ci = FEi (0),
ci+1 = FSi (ci ),
di = zi + ci − B · ci+1 .
(135)
Then: 1. the values ci equal the sequential carries of (134) and lie in {0, 1}; 2. every corrected digit satisfies 0 ≤ di ≤ B − 1; 3. the corrected representation preserves the integer value: n−1 X
zi · B i =
i=0
n−1 X
di · B i + cn · B n ;
(136)
i=0
4. in one complete bit-reversed cyclic domain, all carry-in states are obtained with m rotations, monoid depth m, and 2 · m − 1 packed symbolic compositions. No final logical-predecessor shift is required. Proof. By definition, E0 = e, so FE0 (0) = 0 = c0 . Assume inductively that FEi (0) equals the sequential carry entering digit i. Ordered composition gives Ei+1 = Ei ⋄ Si , Hence
FEi+1 = FSi ◦ FEi .
zi + ci FEi+1 (0) = FSi FEi (0) = FSi (ci ) = = ci+1 . B
27
(137)
(138)
This proves equality with sequential propagation for every i. Because 0 ≤ zi ≤ 2 · B − 2 and ci ∈ {0, 1}, 0 ≤ zi + ci ≤ 2 · B − 1 < 2 · B.
(139)
Therefore its quotient by B is either zero or one, proving ci+1 ∈ {0, 1}. The value di in (135) is the Euclidean remainder of zi + ci modulo B, and thus lies in {0, . . . , B − 1}. Multiplying the digit equation by B i and summing gives n−1 X
di · B i =
i=0
n−1 X
zi · B i +
i=0
=
n−1 X
n−1 X
ci · B i −
i=0
n−1 X
ci+1 · B i+1
(140)
i=0
zi · B i + c0 − cn · B n .
(141)
i=0
Since c0 = 0, rearrangement yields (136). Finally, Theorem 4 gives the scan costs. The scan places Ei at the same physical slot as digit i. Both FEi (0) and FSi (ci ) are therefore slotwise evaluations, so no post-scan routing is needed. In the one-ciphertext symbol representation, one abstract state rotation is one ciphertext rotation. If ei = σ(Ei ) and si = σ(Si ), the local evaluation can be written explicitly as ci = gen(ei ),
ci+1 = gen(si ) + prop(si ) · ci .
(142)
The first expression is linear in ei and ei . The second uses one additional slotwise ciphertext multiplication after the scan. It replaces the final predecessor rotation required by an inclusive-only formulation. Thus, after state classification, the exclusive symbolic realization has scan multiplicative depth m and carry-correction depth at most m + 1; exact scale and level accounting is backend dependent. 7.3
Borrow, comparison, and conditional subtraction
Let xi , yi ∈ {0, . . . , B − 1} be canonical digits. The outgoing borrow from digit i is the Boolean transition ( 1, xi − yi − b < 0, b ∈ {0, 1}. (143) Gxi ,yi (b) := 0, xi − yi − b ≥ 0, It is a kill state when xi > yi , a propagate state when xi = yi , and a generate state when xi < yi . Hence it is represented by the same monoid and the same complex symbols as carry. Theorem 10 (Borrow and comparison). Let X :=
n−1 X
xi · B i ,
Y :=
i=0
n−1 X
yi · B i ,
(144)
i=0
set b0 = 0, and let Ei− be the exclusive prefix of the borrow transitions in (143). Define bi = FE − (0), i
bi+1 = Gxi ,yi (bi ),
qi = xi − yi − bi + B · bi+1 .
(145)
Then qi ∈ {0, . . . , B − 1} and n−1 X
qi · B i = X − Y + b n · B n .
(146)
i=0
Moreover, bn = 1
⇐⇒
The borrow scan uses the same m rotations as carry.
28
X < Y.
(147)
Proof. The proof that bi = FE − (0) equals sequential borrow propagation is identical to the induction i in (137) and (138), with Gxi ,yi in place of FSi . If bi+1 = 0, then xi − yi − bi ≥ 0, and this quantity is at most B − 1; hence qi = xi − yi − bi ∈ {0, . . . , B − 1}. If bi+1 = 1, then −B ≤ xi − yi − bi ≤ −1,
(148)
so adding B again yields qi ∈ {0, . . . , B − 1}. Multiplying (145) by B i and summing telescopes: n−1 X
qi · B i = X − Y −
i=0
n−1 X
bi · B i +
i=0
n−1 X
bi+1 · B i+1
(149)
i=0
= X − Y − b 0 + bn · B n ,
(150)
which gives (146) because b0 = 0. The left-hand side lies in [0, B n − 1]. If bn = 0, then X − Y ≥ 0. If bn = 1, then n−1 X X −Y = qi · B i − B n ≤ −1. (151) i=0
This proves (147). The routing cost is the same because the transition monoid and scan topology are unchanged. Comparison needs only the final borrow at the most significant digit. A conditional operation on every digit instead needs a replicated copy of this bit. The scan can provide it without another rotation by retaining the final aggregate update that was omitted from the 2 · m − 1 work count. Proposition 6 (Conditional subtraction without additional routing). Let M be an n-digit positive integer, let 0 ≤ X < 2 · M , and compute the borrow digits qi of X − M as in Theorem 10. If the final complete aggregate A(m) is retained, its transition is replicated at every slot and therefore yields the final borrow bn at every digit. The slotwise selection ri := bn · xi + (1 − bn ) · qi encodes
( X, R= X − M,
X < M, X ≥ M,
(152)
0 ≤ R < M.
(153)
It uses m rotations, monoid depth m, and 2 · m packed monoid compositions. Proof. By (147), bn = 1 exactly when X < M . In that case (152) selects the original digit xi . Otherwise it selects qi , and (146) with bn = 0 shows that these digits encode X −M . The assumption X < 2 · M places either selected value in [0, M − 1]. At every nonfinal level, the exclusive scan already computes both the next aggregate and the next prefix. At the final level, computing the aggregate as well as the prefix adds one packed monoid composition in parallel. It therefore changes T from 2 · m − 1 to 2 · m without changing monoid depth or rotation count. By the aggregate invariant, A(m) is the complete transition replicated throughout the cyclic domain, so FA(m) (0) = bn is available at every digit without a broadcast rotation. 7.4
Fully occupied digit-major batching
A CKKS ciphertext normally carries several independent integers. Let each integer have n = 2m digit positions and suppose that the ciphertext’s active cyclic domain contains exactly g · n slots. Recall the digit-major layout Φ(r, i) = r + g · revm (i)
(mod g · n),
0 ≤ r < g,
0 ≤ i < n.
The object index is the residue modulo g, while bit reversal is applied to the digit index.
29
(154)
Theorem 11 (Segmented replicated carry). Under the layout in (154), all g independent carry or borrow scans execute level d with the single physical rotation g · 2m−d−1 .
(155)
Consequently, batching g integers requires exactly m scan rotations in total, not g · m. This rotation count is optimal for any circuit that produces an output depending on all n digits of one packed integer. Proof. Let sd = 2m−d−1 and consider physical slot p = Φ(r, i). Under the rotation convention in (31), a rotation by g · sd reads from p − g · sd ≡ r + g · revm (i) − sd (mod g · n). (156) This source address has the same residue r modulo g and therefore belongs to the same packed integer. After division of the non-residue part by g, the source digit address is exactly the unsegmented rotation by sd in Zn . The sibling-copy lemma Lemma 4 consequently supplies a valid aggregate of the sibling child for object r. Since the same argument holds for every r, one physical rotation executes the level for all objects at once. There are m levels, which gives the upper bound. For the lower bound, fix one output of one object that depends on all its n = 2m input digits. With R rotation invocations, dependency paths expose at most 2R source displacements, independently of the larger ambient cyclic domain. Thus 2R ≥ n and R ≥ m. The theorem requires a complete cyclic domain, or equivalent padding by dummy objects. For an object-major layout or a partially filled domain, a global rotation can wrap into another object or an inactive region; the single-rotation sibling argument then does not apply without an additional packing theorem. 7.5
Non-power-of-two digit lengths
The power-of-two assumption is removed by padding the transition vector, not by changing the scan recurrence. Let ℓ ≥ 1 be the number of active digits and set mℓ := ⌈log2 ℓ⌉ ,
nℓ := 2mℓ .
(157)
For positions i ∈ {ℓ, . . . , nℓ − 1}, place the transition identity e = P, represented by the symbol 1/2. Corollary 5 (Optimal identity padding). The exclusive prefixes of the first ℓ states are unchanged by identity padding to nℓ . They can be computed with ⌈log2 ℓ⌉
(158)
rotations, and no circuit producing one output depending on all ℓ active states can use fewer rotations in the packed-rotation model. Moreover, ℓ ≤ nℓ < 2 · ℓ,
(159)
and equality on the left holds exactly when ℓ is a power of two. Proof. Appending identity states does not change any ordered prefix whose endpoint is below ℓ. The length-nℓ scan therefore gives the required outputs with mℓ rotations. Conversely, if one output depends on all ℓ active inputs, the subset-displacement argument yields 2R ≥ ℓ, and hence R ≥ ⌈log2 ℓ⌉ = mℓ . Finally, nℓ is by definition not smaller than ℓ. If ℓ is a power of two, then nℓ = ℓ. Otherwise, 2mℓ −1 < ℓ < 2mℓ = nℓ , and therefore nℓ < 2 · ℓ. Identity padding is a state-level operation. Padding provisional digits by zero instead would create kill states rather than transition identities. It would not affect prefixes ending before the padding, but it would destroy a final aggregate intended to propagate the true carry or borrow through the padded suffix. The implementation must therefore overwrite padded state slots with the public identity symbol after classification.
30
7.6
Concrete-operation boundary
The preceding results fix the exact routing and discrete arithmetic semantics. For the one-ciphertext symbol encoding, the scan itself requires: – m ciphertext rotations of the aggregate state; – 2 · m − 1 evaluations of (127), each containing one ciphertext multiplication and one conjugation; – two persistent state ciphertexts, for the replicated aggregate and the exclusive prefix; – one local state-on-bit multiplication to obtain all outgoing carries or borrows from the exclusive states. Functional bootstrapping for state classification, scale alignment between updated and unchanged branches, rescaling, modulus consumption, key-switch noise, and the final decoding margin are not abstract monoid costs. They are accounted for separately in the next section. In particular, the exact statement proved here is that, whenever these approximate operations decode to the prescribed symbols and bits, the resulting radix digits and comparison bits are mathematically exact.
8
CKKS Realization and Evaluation
We evaluate whether the exact reduction in cyclic rotations translates into practical advantages for CKKS carry circuits. The experiments answer four questions: when the replicated construction overtakes direct transported-predecessor routing; which resources it exchanges for lower routing cost; whether the same savings survive interleaved carry and borrow; and whether the retained modulus levels change the outcome of an end-to-end encrypted pipeline. 8.1
Implementation and methodology
The implementation is written in Go using Lattigo v6.1.1 and executed inside a pinned Docker image on a machine with an Intel(R) Xeon(R) CPU E5-2695 v3 at 2.30 GHz, 128 GB of memory, and Ubuntu 24.04. Public masks are prepared outside timed regions. Online timing excludes parameter construction, key generation, encryption, decryption, correctness checking, and report serialization. Each kernel generates exactly the direct rotation keys used by that implementation. The reports record rotations, encrypted symbol compositions, ciphertext and plaintext products, relinearizations, conjugations, rescales, consumed levels, serialized evaluation-key bytes, peak live ciphertexts, heap usage, and numerical precision. We distinguish two layout contracts. Natural recursive doubling is an unconstrained naturallayout reference: it accepts and returns natural order. The primary comparison concerns three kernels that accept and return bit-reversed data: direct bit-reversed predecessor routing, the rotation-optimal replicated scan, and normalize–scan–restore. The latter is an author-constructed conversion baseline rather than a single prior-work algorithm. Comparisons among these three methods therefore solve the same layout-preserving problem. For scan scaling, we use active lengths n = 2m with m ∈ {5, 6, 7}. For the end-to-end experiment, we evaluate a base-8 carry pipeline at m = 7, followed by an encrypted multiplicative tail of depth five. The campaign uses three deterministic seeds and two process-isolated repetitions per seed, for six paired samples. Each pair evaluates the same canonical digits and downstream function. Artifact availability. The implementation, raw JSON reports, CSV summaries, and the commands allowing the evaluation results to be reproduced are available at https://github.com/nserser/ optimal_rotation_fhe. 8.2
Kernel scaling and crossover
Table 3 reports online latency for the three bit-reversed-layout strategies. At m = 5, the replicated construction becomes faster than direct transported-predecessor routing: 1.301 s versus 1.399 s. Its
31
Table 3. Online scan latency under the common bit-reversed input/output contract. The replicated construction crosses direct predecessor routing at m = 5 and remains faster through m = 7. m
Replicated (s)
Direct predecessor (s)
Normalize–restore (s)
5 6 7
1.301 1.298 1.394
1.399 1.603 1.741
1.036 1.146 1.140
Table 4. Bit-reversed-layout resource comparison at m = 7. Normalize–scan–restore minimizes isolated latency; the replicated construction minimizes rotations, key storage, working memory, and consumed levels. Kernel
Latency (s)
Rot.
Eval. keys (MB)
Peak heap (MB)
Levels
1.394 1.741 1.140
7 28 19
272.6 908.6 454.3
830.5 2300.0 1272.0
14 14 20
Replicated Direct predecessor Normalize–restore
advantage grows to 19.1% at m = 6 and 19.9% at m = 7. This crossover matches the structural costs: direct routing performs m · (m + 1) Rdirect = 2 rotations, whereas the replicated construction performs exactly Rrep = m. The replicated scan performs more encrypted monoid compositions, but the triangular routing cost eventually dominates. At m = 7, direct routing uses 28 rotations, while the replicated construction uses 7. The reduction also lowers evaluation-key storage from 908.6 MB to 272.6 MB and peak heap from approximately 2.30 GB to 830.5 MB. Thus the routing theorem predicts not only fewer online automorphisms, but also substantially smaller key and working-memory footprints. 8.3
Resource trade-off at m = 7
Normalize–scan–restore remains faster as an isolated scan kernel. At m = 7, it takes 1.140 s, compared with 1.394 s for the replicated construction. This latency advantage is purchased with 19 rather than 7 rotations, 454.3 MB rather than 272.6 MB of evaluation keys, approximately 1.272 GB rather than 830.5 MB peak heap, and 20 rather than 14 consumed backend levels. The complete comparison appears in Table 4. The result is therefore multi-objective rather than a universal latency claim. The replicated scan minimizes routing, key storage, working memory, and modulus consumption; normalize–scan–restore minimizes isolated scan latency. The end-to-end experiment below shows why the level difference can dominate the isolated-kernel difference. 8.4
Rotation-key budget
We also evaluate the time–key-memory frontier obtained by synthesizing required dyadic rotations from fewer directly keyed offsets. For (m, K) = (7, 2), reducing the direct key set from seven keys to two lowers evaluation-key storage by 55.6% and increases online latency by 53.4%. The additional key-switch approximation error is negligible relative to the symbol decision margin. The balanced construction executes 22 online rotation calls, within one call of the counting lower bound L(7, 2) = 21. Since this is a nondivisible instance, we report the implemented upper bound rather than claiming exact optimality. 8.5
Packed carry and borrow
To verify that the routing savings survive batching and complete digit correction, we pack four independent objects with m = 5 into 128 slots using slot(r, i) = r + 4 · rev5 (i).
32
Table 5. Measured reduced-key trade-off at m = 7, normalized to the full seven-key replicated implementation. Configuration
K
Rot. calls
Key storage
Latency
Full-key replicated Balanced synthesis
7 2
7 22
1.000 0.444
1.000 1.534
Table 6. Four-object, base-8, fully interleaved carry and borrow at m = 5. Both executions use five scan rotations and zero post-scan rotations. Operation Carry Borrow
Digit max. error
Wrong-int. margin
Incoming error
Outgoing error
1.8012 · 10−4 1.7961 · 10−4
0.4998199 0.4998204
2.5978 · 10−5 2.5905 · 10−5
2.5762 · 10−5 2.5690 · 10−5
The objects use distinct adversarial patterns, including all-propagate, a generate–propagate chain, alternating kill/generate, and maximal carry or borrow digits. The packed scan still uses exactly five rotations and nine symbol compositions, independent of the number of interleaved objects. All stage invariants and cross-object isolation checks pass, and carry/borrow correction requires zero post-scan rotations. The maximum imaginary leakage is below 1.44 · 10−8 . These measurements support the claim that interleaving preserves both the routing count and cross-object isolation. 8.6
End-to-end level-value experiment
The principal systems experiment connects the scan to a depth-5 encrypted multiplicative tail. We compare the replicated layout-preserving carry pipeline with normalize–scan–restore. In all six process-isolated paired executions, both pipelines produce the same canonical base-8 digits and the same downstream function. The replicated pipeline always completes without refreshing. Normalize–scan–restore always reaches restoration without sufficient remaining levels and therefore performs exactly one bootstrap. The bootstrap component accounts for approximately 4.809 ≈ 69.1% 6.957 of the normalize pipeline’s online latency. Even after subtracting bootstrap time, the remaining normalize path takes approximately 2.148 s, or about 1.31× the complete replicated pipeline. Hence the end-to-end advantage is not solely an accounting consequence of including the bootstrap. Bootstrap avoidance also improves numerical precision, as summarized in Table 8. The worst canonical-digit error is 3.12·10−9 for the replicated pipeline and 2.11·10−6 for normalize–scan–restore with bootstrapping. The worst downstream errors are 3.29 · 10−10 and 5.39 · 10−8 , respectively. 8.7
Evaluation summary and limitations
The experiments support three conclusions. First, the exact reduction from m · (m + 1)/2 to m rotations becomes an online-latency advantage over direct transported-predecessor routing from m = 5 onward, while also reducing key material and working memory. Second, normalize–scan– restore and replicated scanning occupy distinct Pareto points: the former minimizes isolated scan latency, whereas the latter minimizes routing, key storage, memory, and consumed levels. Third, the level advantage changes the end-to-end outcome. In the depth-5 carry pipeline, it removes one bootstrap and yields a mean paired speedup of 4.31× with a 95% confidence interval of [3.69, 4.92]. The carry and borrow experiments take encrypted carry-state symbols as their inputs and evaluate the layout-preserving scan-and-correction layer. This experimental contract matches the algorithmic interface analyzed in this paper and leaves the exact routing and correctness theorems unchanged.
33
Table 7. End-to-end latency over six process-isolated paired samples. The bootstrap component is part of the normalize–scan–restore pipeline. Measurement
Mean (s)
95% CI (s)
Median (s)
p95 (s)
1.634 6.957 4.809 4.306
[1.459, 1.808] [6.669, 7.245] [4.493, 5.126] [3.695, 4.918]
1.630 6.938 4.808 4.060
1.793 7.294 5.219 5.073
Replicated online Normalize + bootstrap Bootstrap component Paired latency ratio
Table 8. Worst precision observed over the end-to-end campaign. Output Canonical digits Depth-5 downstream output
9
Replicated
Normalize + bootstrap
−9
2.1064 · 10−6 5.3872 · 10−8
3.1184 · 10 3.2893 · 10−10
Related Work
Our results sit at the intersection of parallel-prefix computation, packed homomorphic routing, rotation-key management, and radix arithmetic over CKKS. The closest works typically optimize one of these dimensions in isolation. We instead ask how an ordered, possibly noncommutative prefix can be evaluated while preserving a public bit-reversed SIMD representation, and we characterize the exact number and valuation structure of the required cyclic translations. 9.1
Parallel-prefix circuits
Parallel prefix computation has a long history in circuit and parallel-algorithm design. Ladner and Fischer gave logarithmic-depth constructions for associative operators, and subsequent work classified prefix networks according to depth, size, and fanout [LF80; Har03]. Snir established the classical size–depth inequality and studied the structure of depth-efficient prefix circuits [Sni86]. These results charge individual operator nodes or communication edges. That model is deliberately different from ours: one homomorphic rotation applies one common cyclic displacement to every packed slot, so many logical edges may share one charged routing operation, while a single logical predecessor relation may decompose into several cyclic diagonals after a public permutation. The replicated construction uses the broad hypercube-prefix principle of maintaining an aggregate together with a local prefix. Its homomorphic contribution is the physical realization: under bit reversal, semantic replication makes every copy of a sibling aggregate interchangeable, allowing one directed cyclic rotation to serve both child supports at a level. The matching lower bound and the two-adic equality characterization concern this packed-rotation cost and do not follow from classical size–depth optimality. Conversely, our result does not improve the gate count or fanout bounds of classical prefix networks. 9.2
Packed homomorphic routing and linear transformations
Packed lattice-based HE evaluates additions and multiplications slotwise, whereas slot movement is implemented by automorphisms and key switching. CKKS introduced approximate SIMD arithmetic over complex slots [Che+17]; modern bootstrapping and representation-conversion procedures devote substantial work to structured linear transformations and their rotation schedules [Bos+21; Gee24]. These transformations are commonly optimized through diagonal decompositions, staged FFT-like factorizations, hoisting, or baby-step/giant-step scheduling. Our target is narrower but nonlinear: the values being routed evolve through an ordered monoid operation, and the required output is every ordered prefix rather than a fixed linear permutation. Normalize–scan–restore is therefore a valid conversion baseline, but it is not equivalent to the layoutpreserving construction. The latter keeps the bit-reversed representation throughout and proves
34
that the representation itself imposes no unavoidable rotation overhead beyond the global lower bound of m. The theorem excludes uncounted arbitrary linear maps or bootstrapping transforms; allowing such operations would change the routing model. Recent work on CKKS bootstrapping also makes modulus consumption and rotation-key storage explicit optimization targets. Bossuat et al. optimize full-RNS CKKS bootstrapping with non-sparse keys [Bos+21], while Yan et al. study a time–memory trade-off in which additional rotation-key material can increase throughput and reduce modulus consumption [Yan+26]. These results reinforce that rotations, key storage, and levels are distinct resources. Our contribution is complementary: we derive program-specific lower bounds and exact cases for the number of online rotation calls available from at most K directly keyed offsets. 9.3
Rotation-key selection and synthesis
A CKKS evaluator can either store a key for each required automorphism or synthesize unsupported rotations from a smaller directly supported set. Lee et al. reduce client-to-server rotation-key material through hierarchical key generation and distinguish transmitted, stored, and derived keys [Lee+23]. Other workload-oriented approaches select rotation keys according to the rotations exercised by an application. Such methods address generic key distribution or empirical workload optimization. Section 6 instead studies the dependency pattern of bit-reversed ordered prefixes. The coefficientbox argument lower-bounds online calls for every circuit in the stated model, even with arbitrary helper ciphertexts and local computation. When K | m, the lower bound is attained by balanced blocks of consecutive two-adic scales, and equality fixes the valuation profile of the directly keyed offsets. For nondivisible parameter pairs, we report the rigorous lower/upper sandwich and identify exactly the cases in which the two bounds coincide; we do not claim a closed form when they differ. 9.4
Radix CKKS and encrypted integer arithmetic
Cha, Park, and Lee develop radix-based approximate HE for large integers and give a lightweight logarithmic carry procedure based on three transition symbols and a complex-valued composition law [CPL26]. Their construction establishes that exact carry can support unique radix representations, comparison, and modular arithmetic in CKKS. We reuse this optimized state algebra and do not claim the first logarithmic-depth encrypted carry circuit. The distinction is the representation and routing contract. We compute the exclusive carry prefix directly in bit-reversed slots, preserve that layout at the output, and avoid a final logical-predecessor shift. The generic theorem applies to arbitrary associative, possibly noncommutative monoids; carry and borrow are the principal cryptographic instantiations. Our evaluation takes encrypted transition symbols as input and measures the layout-preserving scan-and-correction layer defined by the paper’s algorithmic interface. Alternative FHE representations may change which operations are native. For example, matrixoriented FHE makes matrix arithmetic a first-class encrypted operation rather than realizing it through ordinary SIMD slot rotations [GL25]. Such schemes illustrate a broader design principle: changing the plaintext representation can eliminate one class of routing costs while introducing a different algebra and implementation stack. They solve a different problem from preserving ordered prefixes in the standard cyclic SIMD interface considered here.
10
Conclusion
This work establishes that preserving a bit-reversed SIMD representation does not impose an unavoidable rotation overhead for ordered prefix computation. For n = 2m inputs from an associative, possibly noncommutative monoid, the replicated construction computes all inclusive or exclusive prefixes in the same bit-reversed layout using D = m,
R = m,
35
T ≤ 2 · m − 1.
(160)
The depth and rotation counts are exact in the stated packed-rotation model: D⋆ (m) = R⋆ (m) = m.
(161)
The constructive reason is semantic replication. Every slot of an aligned logical block stores the same complete block aggregate, so a destination need not receive the copy held by one exact logical partner. Under bit reversal, one cyclic rotation per level supplies every destination with an interchangeable copy from the sibling block while public masks preserve the required noncommutative operand order. Optimality has additional structure. Every m-rotation equality case uses one offset at each 2-adic valuation, and limiting the evaluator to K directly keyed offsets yields a coefficient-box lower bound on online rotation calls. When K | m, the resulting frontier is exact: R⋆ (m, K) = K · 2m/K − 1 , (162) with equality fixing the valuation profile of the directly keyed offsets. For nondivisible parameters, the paper gives rigorous lower and upper bounds and identifies the cases in which they coincide, without claiming a closed formula for the remaining gaps. The radix-CKKS instantiation shows why the exclusive formulation matters. Once encrypted kill, propagate, and generate symbols are available, the scan returns the transition preceding each digit. Carry-in, carry-out, and digit correction are then evaluated slotwise, avoiding both natural-order restoration and a final logical-predecessor shift. The same mechanism gives borrow propagation, comparison, conditional subtraction, and fully occupied digit-major batching without multiplying the number of scan rotations. The measurements confirm that rotation optimality represents a genuine multi-resource trade-off rather than a universal isolated-latency optimum. Among bit-reversed-layout-preserving kernels, the replicated scan reduces the triangular direct-routing cost to m rotations and, from the tested medium depths onward, improves latency, evaluation-key storage, and working memory over direct predecessor routing. Normalize–scan–restore remains faster for the isolated scan in the tested range, but consumes more rotations, evaluation-key material, memory, and modulus levels. In the evaluated downstream pipeline, retaining those levels avoids the bootstrap required by normalization and yields the stronger end-to-end result. Natural recursive doubling remains the appropriate unconstrained reference when the surrounding computation is free to use natural-order input and output; it does not satisfy the same layout-preservation contract. The evaluation targets the layout-preserving scan-and-correction layer and takes encrypted carry-state symbols as inputs. This contract is the same interface used by the radix instantiation and preserves the exact scope of the combinatorial rotation and correctness results. Natural extensions of the theory concern three directions. First, nondivisible direct-key budgets for which the coefficient-box lower bound is strictly below the balanced dyadic construction define a narrower exact-frontier problem. Second, the semantic sibling argument suggests a broader class of public hierarchical layouts beyond bit reversal. Third, after rotation count is minimized, the remaining abstract trade-off involves packed monoid work, live encrypted state, key memory, and approximation error. These directions build on the exact bit-reversed results established here. LLM usage. Large language models were used only to polish the writing, improve presentation quality, and assist with the implementation of the proposed construction. They were not used to generate any scientific contribution of this paper, including the definitions, constructions, theorems, proofs, experimental claims, or interpretation of the results.
A
Additional Evaluation Details
A.1
Measurement contract and reproducibility
The implementation uses Go and Lattigo v6.1.1 in a pinned Docker image on an Intel(R) Xeon(R) CPU E5-2695 v3 at 2.30 GHz with 128 GB of memory and Ubuntu 24.04. A warm-up execution precedes timed kernel samples. Online measurements exclude key generation, public-mask preparation, encryption, decryption, correctness checking, and JSON serialization. Evaluation-key sizes are obtained from serialized key material and cross-checked against the corresponding files.
36
Table 9. Small-instance comparison at m = 4. Natural recursive doubling uses a different input/output layout and is included only as an unconstrained reference. Kernel
Latency (s)
Rot.
Comp.
Eval. keys (MB)
Peak heap (MB)
0.289 0.450 0.559 0.385
4 10 4 12
4 4 7 4
82.6 165.2 82.6 123.9
246.7 449.1 265.8 376.1
Natural recursive doubling Direct bit-reversed predecessor Rotation-optimal replicated Normalize–scan–restore
Table 10. Detailed bit-reversed-layout scaling. Dashes denote values absent from the consolidated campaign summary. m Kernel
Latency (s) Rot. Levels Keys (MB) Heap (MB)
5 5 5
Replicated Direct predecessor Normalize–restore
1.301 1.399 1.036
5 15 13
10 10 14
212.0 514.9 333.1
653 1330 937
6 6 6
Replicated Direct predecessor Normalize–restore
1.298 1.603 1.146
6 21 18
12 12 18
242.3 696.6 –
749 1850 –
7 7 7
Replicated Direct predecessor Normalize–restore
1.394 1.741 1.140
7 28 19
14 14 20
272.6 908.6 454.3
830.5 2300 1272
All kernels use the same CKKS parameter literal, default scale, K/P/G symbol encoding, ordered composition primitive, and deterministic logical inputs. Natural recursive doubling starts and ends in natural order. The other kernels start and end in bit-reversed order. Precision is computed against an exact sequential ordered-prefix reference. The end-to-end campaign reports sample means, standard deviations, medians, minima, p95 values, and two-sided 95% confidence intervals. The latency-ratio interval is computed from the six paired per-sample ratios. Each report records its seed and explicit operation counters. The artifact includes deterministic input generators, schema-validated JSON reports, exact-reference tests, stage-invariant checks, counter-conservation checks, fuzz targets, race tests, repeated key-generation tests, memory-growth checks, and soak scripts. A.2
Detailed kernel results
The replicated scan performs m rotations and 2 · m − 1 symbol compositions. Direct predecessor routing performs m · (m + 1)/2 rotations and m compositions. Normalize–scan–restore performs m scan rotations plus the layout-conversion network. The crossover therefore depends on the relative backend costs of rotations and encrypted compositions. A.3
End-to-end campaign details
The level-value campaign uses base 8, m = 7, downstream multiplicative depth 5, pattern asymmetric, seeds {1, 2, 3}, and two process-isolated repetitions per seed. All six reports satisfy the comparison contract: the pipelines produce identical canonical digits and downstream functions; every replicated sample avoids bootstrapping; every normalize–scan–restore sample performs exactly one bootstrap.
37
Table 11. Complete latency statistics over six process-isolated samples. Measurement
Mean
Replicated online (s) Normalize + bootstrap (s) Bootstrap component (s) Paired ratio
1.634 6.957 4.809 4.306
95% CI Median [1.459,1.808] [6.669,7.245] [4.493,5.126] [3.695,4.918]
38
1.630 6.938 4.808 4.060
Min. 1.426 6.499 4.360 3.624
p95 Std. dev. 1.793 7.294 5.219 5.073
0.166 0.274 0.302 0.583
References [Bos+21]
Jean-Philippe Bossuat, Christian Mouchet, Juan Ramón Troncoso-Pastoriza, and JeanPierre Hubaux. “Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys”. In: Advances in Cryptology – EUROCRYPT 2021. Vol. 12696. Lecture Notes in Computer Science. Springer, 2021, pp. 587–617. doi: 10.1007/978-3030-77870-5_21. iacr: 2020/1203. [Che+17] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. “Homomorphic Encryption for Arithmetic of Approximate Numbers”. In: Advances in Cryptology – ASIACRYPT 2017. Vol. 10624. Lecture Notes in Computer Science. Springer, 2017, pp. 409– 437. doi: 10.1007/978-3-319-70694-8_15. [CPL26] Gyeongwon Cha, Dongjin Park, and Joon-Woo Lee. “Improved Radix-Based Approximate Homomorphic Encryption for Large Integers via Lightweight Bootstrapped Digit Carry”. In: Advances in Cryptology – EUROCRYPT 2026. Vol. 16544. Lecture Notes in Computer Science. Springer, 2026, pp. 243–273. doi: 10.1007/978-3-032-25327-9_9. iacr: 2025/1740. Robin Geelen. “Revisiting the Slot-to-Coefficient Transformation for BGV and BFV”. [Gee24] In: IACR Communications in Cryptology 1.3, 37 (2024). doi: 10.62056/a01zogy4e-. iacr: 2024/153. Craig Gentry and Yongwoo Lee. Fully Homomorphic Encryption for Matrix Arithmetic. [GL25] Cryptology ePrint Archive, Report 2025/1935. 2025. iacr: 2025/1935. [Har03] David Harris. “A Taxonomy of Parallel Prefix Networks”. In: Proceedings of the 37th Asilomar Conference on Signals, Systems and Computers. IEEE, 2003, pp. 2213–2217. doi: 10.1109/ACSSC.2003.1292395. [Lee+23] Joon-Woo Lee, Eunsang Lee, Young-Sik Kim, and Jong-Seon No. “Rotation Key Reduction for Client–Server Systems of Deep Neural Network on Fully Homomorphic Encryption”. In: Advances in Cryptology – ASIACRYPT 2023. Vol. 14443. Lecture Notes in Computer Science. Springer, 2023, pp. 36–68. doi: 10.1007/978-981-99-8736-8_2. iacr: 2022/532. [LF80] Richard E. Ladner and Michael J. Fischer. “Parallel Prefix Computation”. In: Journal of the ACM 27.4 (1980), pp. 831–838. doi: 10.1145/322217.322232. [Sni86] Marc Snir. “Depth–Size Trade-Offs for Parallel Prefix Computation”. In: Journal of Algorithms 7.2 (1986), pp. 185–201. doi: 10.1016/0196-6774(86)90003-9. [Yan+26] Lianglin Yan, Pengfei Zeng, Heyang Cao, Peizhe Song, and Mingsheng Wang. “Faster Bootstrapping for CKKS with Less Modulus Consumption”. In: Public-Key Cryptography – PKC 2026. Vol. 16554. Lecture Notes in Computer Science. Springer, 2026, pp. 335–366. doi: 10.1007/978-3-032-26740-5_11. iacr: 2025/1403.
39