💻 computer science

Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

This paper introduces a rotation-optimal prefix scan algorithm for bit-reversed homomorphic encryption layouts that reduces the rotation complexity from $O(m^2)$ to $O(m)$ by leveraging a replicated-aggregate invariant, thereby significantly lowering computational latency, memory usage, and evaluation-key storage while enabling deeper downstream pipelines.

Original authors: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, encrypted spreadsheet where every cell holds a secret number. You want to perform a specific math trick on all these numbers at once: for every cell, you need to know the "running total" of all the numbers that came before it. In the world of Homomorphic Encryption (computing on secret data without ever decrypting it), this is called a "prefix scan."

The problem is that the data isn't stored in a neat row like 1, 2, 3, 4. Because of how the encryption works, the data is scrambled in a specific pattern called "bit-reversed order." It's like a book where the pages are shuffled: page 1 is followed by page 8, then page 4, then page 12, and so on.

The Old Way: The "Exact Neighbor" Problem

To calculate the running total, you usually need to ask your neighbor for their number. In a normal row, your neighbor is just one step away. But in this scrambled "bit-reversed" book, your logical neighbor might be sitting on the other side of the room.

The old method tried to solve this by sending a messenger (a "rotation") to fetch the exact specific neighbor you needed.

The Analogy: Imagine you are in a library with 8 shelves. You need to talk to the person on the shelf directly to your left. But because the shelves are scrambled, "left" means different physical distances for different people.
The Cost: To get everyone their correct neighbor, the librarian had to send messengers on many different routes. For a small book of 8 pages, it took 6 messengers. For a bigger book, the number of messengers exploded (it grew like a triangle: 1+2+3+4...). This was slow, expensive, and required a huge library of "keys" (permission slips) to send messengers to all those different spots.

The New Way: The "Copycat" Strategy

The authors of this paper realized they were being too picky. They didn't need the exact neighbor; they just needed anyone from the neighbor's group who had the same information.

The Analogy: Instead of asking for the specific person on the left, imagine that every person in a "group" (a block of shelves) is holding an identical copy of the group's total score.
The Magic Move: The authors found a way to rotate the entire library just once per level of the calculation. This single rotation moves everyone to a spot where they are standing next to someone from the adjacent group. Because everyone in that group is holding the same "group total" copy, it doesn't matter which specific person you get; the math works out perfectly.
The Result: Instead of needing 6 messengers for 8 pages, you only need 1 messenger per level. For the whole book, you go from needing a triangular number of messengers (like 28) down to just the number of levels (like 7).

What They Actually Proved

The paper doesn't just say "this is faster." They proved three hard mathematical facts:

You can't do better: They proved that no matter how clever you are, you must use at least as many rotations as there are levels in the calculation. You can't skip the messengers entirely.
The "Perfect" Route: They showed that if you use the minimum number of messengers, those messengers must follow a very specific, rigid pattern (related to powers of 2). There is no wiggle room; the math forces this specific path.
The Trade-off: To save on messengers, you have to do a little more math work locally (keeping two sets of numbers instead of one). But in their tests, saving the messengers was worth it.

The Real-World Test (The "Carry" Problem)

They tested this on a very common math problem: Carrying numbers (like when you add 9 + 3 and get 12, you have to "carry" the 1 to the next column).

The Setup: They encrypted a list of digits and tried to fix the carries without unscrambling the order.
The Outcome:
- Speed: Their new method was about 20% faster than the old "exact neighbor" method for medium-sized problems.
- Memory: It used 64% less memory because they didn't need to store as many permission keys.
- The Big Win: In a longer chain of calculations, their method saved enough "encryption power" to avoid a massive, slow reset procedure (called "bootstrapping"). This made the whole process 4.3 times faster end-to-end.

Summary

Think of it like a relay race.

Old Method: Every runner had to run a unique, long, winding path to find their specific teammate. It took a lot of energy and time.
New Method: The team realized that if they just ran a short, standardized loop, everyone would end up next to a teammate who had the same baton. It took fewer steps, less energy, and got the job done faster, even though the runners had to hold onto a few extra batons along the way.

The paper proves this shortcut is the absolute fastest possible way to do this specific type of math on scrambled, encrypted data.

Technical Summary: Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

Problem Statement

In packed homomorphic encryption (HE), specifically the CKKS scheme, SIMD operations allow parallel computation on encrypted vectors. However, communication between slots requires cyclic rotations (Galois automorphisms), which are costly operations involving key switching. The cost of a rotation depends on the physical layout of the data.

The paper addresses the problem of performing ordered prefix computations (scans) on $n = 2^m$ elements of an associative, possibly noncommutative monoid when the data is stored in a bit-reversed order. This layout is common in fast transforms and packing conversions.

The core challenge is that a standard "transported-predecessor" scan, which recursively doubles the distance to logical predecessors, incurs a high routing cost in a bit-reversed layout. Because bit reversal permutes logical indices, a single logical shift by $2^t$ decomposes into multiple distinct cyclic displacement classes. Consequently, a direct implementation requires $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ rotations. The authors investigate whether this triangular cost is an inherent property of prefix computation in bit-reversed layouts or an artifact of the specific routing topology.

Methodology and Construction

The paper introduces a replicated-aggregate invariant to reduce the rotation count from quadratic to linear.

Semantic Replication: Instead of routing every slot to its exact logical predecessor, the construction maintains a state where every slot within an aligned logical block stores the complete aggregate of that block.
Sibling-Block Exchange: At each level $d$ $d$ of the scan (combining blocks of size $2^d$ $2^{d}$ ), the algorithm rotates the aggregate state by a specific offset $s_d = 2^{m-d-1}$ $s_{d} = 2^{m - d - 1}$ .
- Under bit reversal, the two children of a parent block occupy physical cosets separated exactly by $s_d$ .
- A rotation by $s_d$ maps a slot to some position in the sibling block. Because the sibling's aggregate is replicated across all its slots, any position in the sibling block provides the correct semantic value.
- This allows a single directed cyclic rotation to supply valid aggregates for both child orientations simultaneously, preserving correctness for noncommutative monoids via public masks that select operand order.
Exclusive Scan Formulation: The authors implement an exclusive scan (outputting the prefix before the current element). This avoids the need for a final logical-predecessor shift to retrieve the incoming carry for digit correction, a requirement that would otherwise reintroduce layout-sensitive routing.
Lower Bound Proofs: The paper establishes that $m$ rotations are a global lower bound for any circuit computing an output depending on all $2^m$ inputs in this model. The proof relies on a subset-sum argument: if $R$ rotations are used, at most $2^R$ distinct input displacements can reach a fixed output. To cover all $2^m$ inputs, $R \ge m$ is necessary. Furthermore, the paper proves that achieving this bound requires the rotation offsets to form a complete 2-adic basis (one offset for each valuation $0, \dots, m-1$ ).

Key Contributions

Optimal Scan Construction: An inclusive and exclusive scan algorithm that achieves $R = m$ rotations and $D = m$ monoid depth for bit-reversed layouts. This reduces the rotation count from the direct topology's $O(m^2)$ to $O(m)$ .
Rigidity of Optimality: A characterization of all optimal circuits. If a circuit uses exactly $m$ rotations, the offsets must form a complete 2-adic basis. This proves that the rotation profile is rigid, even if the circuit topology varies.
Rotation-Key Frontier: An analysis of the trade-off between the number of directly keyed offsets ( $K$ $K$ ) and the number of online rotation calls ( $R$ $R$ ).
- The paper derives a product lower bound: $\prod (c_j + 1) \ge 2^m$ , where $c_j$ is the number of times key $j$ is used.
- When $K$ divides $m$ , the exact frontier is proven to be $R^* = K \cdot (2^{m/K} - 1)$ .
Radix-CKKS Instantiation: Application of the exclusive scan to exact carry and borrow propagation in radix-based CKKS. This allows for integer comparison and modular arithmetic without restoring the natural order or performing a final shift.
Batching Efficiency: Demonstration that the rotation savings hold for fully occupied digit-major interleavings, where $g$ independent integers are packed into a single ciphertext without multiplying the rotation count.

Results and Evaluation

The authors implemented the algorithm in Lattigo (Go) and compared it against two baselines:

Direct Bit-Reversed Predecessor: The naive $O(m^2)$ rotation approach.
Normalize–Scan–Restore: A baseline that converts data to natural order, scans, and converts back.

Key Findings at $m=7$ (128 slots):

Rotations: Reduced from 28 (direct) to 7 (replicated).
Evaluation Keys: Storage reduced by 70.0% (908.6 MB $\to$ 272.6 MB).
Memory: Peak heap usage reduced by 63.9% (2.30 GB $\to$ 830.5 MB).
Latency: The replicated scan improved isolated scan latency by 19.9% over the direct predecessor method.
End-to-End Pipeline: In a depth-5 downstream pipeline, the replicated scan avoided a full bootstrapping operation required by the normalize-restore baseline. This yielded a mean paired speedup of 4.31 $\times$ (95% CI [3.69, 4.92]).

The paper notes that while "normalize–scan–restore" has lower isolated latency for small $m$ due to fewer monoid compositions, the replicated scan becomes faster at $m \ge 5$ and offers superior resource efficiency (keys, memory, modulus levels).

Significance and Claims

The paper claims that preserving a bit-reversed SIMD representation does not impose an unavoidable rotation overhead for ordered prefix computation. The significance lies in:

Breaking the Quadratic Barrier: Proving that the $O(m^2)$ cost of direct routing in bit-reversed layouts is not inherent but can be reduced to the theoretical lower bound of $O(m)$ via semantic replication.
Resource Trade-offs: Establishing that the reduction in routing cost (rotations) and key storage comes at the expense of increased packed monoid work ( $2m-1$ compositions vs. $m$ ) and a second live state vector. The paper argues this trade-off is favorable for deep pipelines where modulus levels and bootstrapping are bottlenecks.
Exactness: Providing exact lower bounds and frontier characterizations for rotation-key management, moving beyond heuristic optimizations to provable limits for specific dependency patterns.

The work is presented as a specific optimization for the bit-reversed layout constraint, distinct from general prefix network theory, and is validated through rigorous combinatorial proofs and empirical evaluation in a standard CKKS implementation.