💻 computer science

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

本文介绍了一种针对位逆序同态加密布局的旋转最优前缀扫描算法，该算法通过利用复制-聚合不变性，将旋转复杂度从 $O(m^2)$ 降低至 $O(m)$ ，从而显著降低了计算延迟、内存使用量和评估密钥存储量，并实现了更深层的下游流水线。

原作者： Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

发布于 2026-07-07

📖 1 分钟阅读☕ 轻松阅读

原作者： Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你有一个巨大的、经过加密的电子表格，其中的每个单元格都包含一个秘密数字。你想对这些数字同时进行一种特定的数学技巧：对于每个单元格，你需要知道出现在它之前的数字的“运行总和”（running total）。在同态加密（Homomorphic Encryption，即在不解密的情况下对秘密数据进行计算）的世界里，这被称为“前缀扫描”（prefix scan）。

问题在于，数据并不是以整齐的行形式存储的（如 1, 2, 3, 4）。因为加密方式的原因，数据是以一种被称为“位反转顺序”（bit-reversed order）的特定模式被打乱了。这就像一本页码被重新排列过的书：第 1 页后面跟着的是第 8 页，然后是第 4 页，接着是第 12 页，依此类推。

旧方法：“精确邻居”问题

为了计算运行总和，你通常需要询问你左边的邻居他们的数字。在普通的行中，你的邻居就在一步之遥。但在这种被打乱的“位反转”书中，你的逻辑邻居可能坐在房间的另一头。

旧的方法试图通过派出一名信使（一次“旋转/rotation”）来获取你所需的那个确切的邻居。

类比： 想象你在一个拥有 8 个书架的图书馆里。你需要找左边紧挨着你的那个人。但由于书架是打乱的，“左边”对于不同的人来说意味着不同的物理距离。
代价： 为了让每个人都得到正确的邻居，管理员不得不派出信使走许多不同的路线。对于一本只有 8 页的小书，他需要派出 6 名信使。对于更大的书，信使的数量会爆炸式增长（呈三角形增长：1+2+3+4...）。这既慢又贵，而且需要大量的“密钥”（准许证）来允许信使前往所有这些不同的位置。

新方法：“模仿者”策略

这篇论文的作者意识到他们以前太挑剔了。他们并不需要确切的邻居；他们只需要来自邻居组中任何一个拥有相同信息的人即可。

类比： 与其要求寻找左边那个特定的特定的人，不如想象一下，每个“组”（一个区块的书架）中的每个人都拿着该组总分的相同副本。
神奇的移动： 作者发现了一种方法，只需在计算的每一层进行一次整体旋转，就能完成任务。这单次旋转会将所有人移动到一个位置，使他们恰好站在来自相邻组的某个人旁边。因为该组中的每个人都持有相同的“组总和”副本，所以无论你得到的是哪个人，数学运算都能完美运行。
结果： 以前处理 8 页书需要 6 名信使，现在你只需要每层 1 名信使。对于整本书，你从需要的信使数量（如 28 个）减少到了仅仅是层数（如 7 层）。

他们究竟证明了什么

这篇论文不仅仅是说“这更快了”。他们证明了三个硬性的数学事实：

你无法做得更好： 他们证明了无论你多么聪明，你必须使用至少与计算层数相等的旋转次数。你无法完全跳过信使。
“完美”路径： 他们表明，如果你使用最少数量的信使，这些信使必须遵循一个非常特定且僵化的模式（与 2 的幂相关）。没有回旋余地；数学强制要求这条特定的路径。
权衡： 为了节省信使，你必须在本地做更多的数学工作（保留两组数字而不是一组）。但在他们的测试中，节省信使带来的收益超过了增加的计算量。

现实世界的测试（“进位”问题）

他们在数学中一个非常常见的问题上测试了这一点：进位（比如当你把 9 + 3 相加得到 12 时，你需要把那个 1 “进”到下一列）。

设置： 他们加密了一组数字，并尝试在不重新排列顺序的情况下修复进位。
结果：
- 速度： 对于中等规模的问题，他们的新方法比旧的“精确邻居”法快了约 20%。
- 内存： 由于不需要存储那么多权限密钥，它节省了 64% 的内存。
- 重大胜利： 在更长的计算链中，他们的方法节省了足够的“加密能量”，从而避免了一个极其缓慢的重置程序（称为“自举/bootstrapping”）。这使得整个过程端到端地提高了 4.3 倍。

总结

把它想象成一场接力赛。

旧方法： 每个跑者都必须沿着一条独特的、漫长且曲折的路径去寻找他们特定的队友。这消耗了大量的能量和时间。
新方法： 团队意识到，如果他们只是跑一个简短的标准循环，每个人最终都会站在一个持有相同接力棒的队友旁边。这需要的步骤更少，消耗的能量更低，尽管跑者需要同时拿着更多的接力棒。

这篇论文证明了这种快捷方式是处理这类打乱的、加密数据时，进行此类特定数学运算的最快方式。

技术摘要：位逆序同态布局下的旋转最优非交换前缀扫描

问题陈述

在打包同态加密（HE）中，特别是 CKKS 方案，SIMD 操作允许在加密向量上进行并行计算。然而，槽位（slots）之间的通信需要循环旋转（Galois 自同构），这是一种涉及密钥切换（key switching）的高昂操作。旋转的成本取决于数据的物理布局。

本文解决了在存储于位逆序（bit-reversed）顺序中的 $n = 2^m$ 个元素（属于一个可能的非交换幺半群）上执行有序前缀计算（扫描）的问题。这种布局在快速变换和打包转换中非常常见。

核心挑战在于，标准的“传输前驱项”（transported-predecessor）扫描通过递归地倍增与逻辑前驱项的距离来进行计算，但在位逆序布局下会产生高昂的路由成本。由于位逆序置换了逻辑索引，单个逻辑位移 $2^t$ 会分解为多个不同的循环位移类。因此，直接实现需要 $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ 次旋转。作者研究了这种三角形成本是位逆序布局中前缀计算的固有属性，还是特定路由拓扑的产物。

方法论与构建

本文引入了一种复制聚合不变性（replicated-aggregate invariant），将旋转次数从二次方降低到线性。

语义复制（Semantic Replication）： 该构建不再是将每个槽位路由到其精确的逻辑前驱项，而是维持一种状态，使得每个对齐的逻辑块内的每个槽位都存储该块的完整聚合值。
兄弟块交换（Sibling-Block Exchange）： 在扫描的每一层 $d$ $d$ （组合大小为 $2^d$ $2^{d}$ 的块）中，算法按特定偏移量 $s_d = 2^{m-d-1}$ $s_{d} = 2^{m - d - 1}$ 旋转聚合状态。
- 在位逆序下，父块的两个子块占据着由 $s_d$ 分隔的物理余数类。
- 一个由 $s_d$ 产生的旋转将一个槽位映射到兄弟块中的某个位置。由于兄弟块的聚合值在所有槽位中都是复制的，因此兄弟块中的任何位置都能提供正确的语义值。
- 这允许一次定向循环旋转同时为两种方向的子块提供有效的聚合值，并通过选择操作数顺序的公共掩码（public masks）来保持非交换幺半群的正确性。
独占扫描公式化（Exclusive Scan Formulation）： 作者实现了一种独占扫描（输出当前元素之前的前缀）。这避免了为了检索用于进位修正的传入进位而必须进行的最终逻辑前驱项位移，否则该需求会重新引入对布局敏感的路由。
下界证明： 本文证明了对于在该模型中计算依赖于所有 $2^m$ 个输入的电路， $m$ 次旋转是全局下界。该证明依赖于子集和论证：如果使用了 $R$ 次旋转，则最多只有 $2^R$ 个不同的输入位移可以到达一个固定的输出。为了覆盖所有 $2^m$ 个输入， $R \ge m$ 是必要的。此外，本文证明了要达到这一界限，旋转偏移量必须构成一个完整的 2-adic 基（一个偏移量对应每个估值为 $0, \dots, m-1$ ）。

核心贡献

最优扫描构建： 一种针对位逆序布局的包含性（inclusive）和独占性（exclusive）扫描算法，实现了 $R = m$ 次旋转和 $D = m$ 次幺半群深度。这使旋转次数从直接拓扑的 $O(m^2)$ 降低到了 $O(m)$ 。
最优性的刚性（Rigidity of Optimality）： 对所有最优电路的特征化。如果一个电路恰好使用了 $m$ 次旋转，则其偏移量必须构成一个完整的 2-adic 基。这证明了即使电路拓扑发生变化，旋转剖面也是具有刚性的。
旋转密钥前沿（Rotation-Key Frontier）： 分析了直接密钥偏移量数量（ $K$ $K$ ）与在线旋转调用次数（ $R$ $R$ ）之间的权衡。
- 本文导出了乘积下界： $\prod (c_j + 1) \ge 2^m$ ，其中 $c_j$ 是密钥 $j$ 被使用的次数。
- 当 $K$ 整除 $m$ 时，确切的前沿被证明为 $R^* = K \cdot (2^{m/K} - 1)$ 。
Radix-CKKS 实例化： 将独占扫描应用于基于基数（radix-based）的 CKKS 中的精确进位与借位传播。这使得无需恢复自然顺序或执行最终位移即可进行整数比较和模运算。
批处理效率： 展示了复制扫描在全填充的“进位优先”（digit-major）交错布局中依然保持节省旋转的优势，其中 $g$ 个独立的整数被打包在单个密文中，而不会增加旋转次数。

结果与评估

作者在 Lattigo (Go) 中实现了该算法，并将其与两个基准进行对比：

直接位逆序前驱项（Direct Bit-Reversed Predecessor）： 朴素的 $O(m^2)$ 旋转方法。
标准化–扫描–恢复（Normalize–Scan–Restore）： 将数据转换为自然顺序，进行扫描，然后再转换回来的基准方法。

在 $m=7$ (128 个槽位) 时的关键发现：

旋转次数： 从 28 次（直接法）减少到 7 次（复制法）。
评估密钥： 存储空间减少了 70.0% (908.6 MB $\to$ 272.6 MB)。
内存： 峰值堆内存使用量减少了 63.9% (2.30 GB $\to$ 830.5 MB)。
延迟： 相比于直接前驱项方法，复制扫描将孤立扫描延迟降低了 19.9%。
端到端流水线： 在深度为 5 的下游流水线中，复制扫描避免了“标准化–恢复”基准方法所要求的完整自举（bootstrapping）操作。这产生了 4.31 $\times$ 的平均配对加速 (95% CI [3.69, 4.92])。

论文指出，虽然对于较小的 $m$ ，“标准化–扫描–恢复”由于幺半群组合次数较少而具有较低的孤立延迟，但当 $m \ge 5$ 时，复制扫描变得更快，并且在资源效率（密钥、内存、模数层级）方面表现更优。

意义与主张

本文声称，保留位逆序 SIMD 表示形式并不意味着在有序前缀计算中存在不可避免的旋转开销。其意义在于：

打破二次方壁垒： 证明了在位逆序布局中，直接路由导致的 $O(m^2)$ 成本并非固有，可以通过语义复制降低到 $O(m)$ 的理论下界。
资源权衡： 明确了减少路由成本（旋转）和密钥存储是以增加打包幺半群工作量（ $2m-1$ 次组合对比 $m$ 次）以及第二个活跃状态向量为代价的。本文认为，对于模数层级和自举操作成为瓶颈的深层流水线，这种权衡是极其有利的。
精确性： 为旋转密钥管理提供了精确的下界和前沿特征，超越了针对特定依赖模式的启发式优化，达到了可证明的极限。

这项工作被呈现为针对位逆序布局约束的一种特定优化，有别于通用的前缀网络理论，并通过在标准 CKKS 实现中的严格组合证明和实证评估得到了验证。