💻 computer science

Beyond Controlled Noise: Achieving Symmetric FHE through Dynamic Position Shifting

本文提出了一种新颖的对称全同态加密方案，该方案通过采用带有动态位置偏移的明文分片来缓解传统噪声增长和计算开销，利用双调节器系统管理乘法运算，并借助绑定机制确保抵御代数攻击的安全性。

原作者： Mostefa Kara

发布于 2026-05-18

📖 1 分钟阅读☕ 轻松阅读

原作者： Mostefa Kara

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

想象你有一条秘密信息，比如一份蛋糕食谱，你希望让厨师用它来烹饪，却从不向他们展示实际的食材。在密码学领域，这被称为全同态加密（FHE）。通常，要做到这一点就像戴着厚重、笨拙的烤箱手套试图烤蛋糕，让你的双手变得迟缓而笨拙。每次混合食材时，“噪声”（即那些烤箱手套）都会加剧，最终导致蛋糕无法被正确烤制。

本文提出了一种使用对称全同态加密的新颖且更轻量的方法。作者不再依赖厚重的烤箱手套，而是采用一套巧妙的洗牌与拆分系统来保持数据的洁净。

以下是该系统的运作原理，分解为几个简单的概念：

1. 问题：“噪声”爆炸

在传统方法中，如果你将两个加密数字相乘，加密内部的“噪声”（数学上的静态干扰）会急剧增长。这就像试图在拥挤的房间里低声传递秘密；如果你将消息从一个人传给另一个人，人群的嘈杂声最终会淹没话语。现有的解决方案试图通过“自举”（一种复杂且缓慢的信号刷新过程）来解决这个问题，这就像每隔几分钟就停止游戏以重置房间。

2. 解决方案：将消息拆分为碎片

作者的想法是将秘密消息（即食谱）切分成三个较小的部分（碎片）。

设置：他们不是隐藏一个巨大的秘密，而是将三个小碎片隐藏在三个不同的“位置”（我们称之为位置 1、位置 2 和位置 3）。
魔术技巧：他们使用特殊的“调节密钥”。可以将这些密钥想象成交通指挥员或洗牌员。

3. 乘法如何运作（“交错”机制）

当你想要将两个加密数字相乘时，系统不会简单地将它们强行合并。相反，它会在碎片之间玩一场“抢椅子”游戏：

规则：如果你将位置 1 中的一个碎片与位置 1 中的另一个碎片相乘，结果不会停留在位置 1。“调节器”会强制将其移动到位置 2。
循环：如果你将位置 2 和位置 3 中的碎片相乘，结果会移动到位置 1。
结果：碎片不断被洗牌到新的位置。这防止了“噪声”在同一个地方堆积。这就像一场接力赛，每次传递接力棒（即数学运算）时，都会交给一名全新的选手，这样就没有任何一名选手会感到疲惫（即积累过多的噪声）。

4. “双调节器”安全网

为了确保没有人能够作弊或破解出密钥，系统使用两种类型的调节器协同工作：

指数调节器：控制数学运算移动的位置（即交通方向）。
系数调节器：控制数字的大小（即归一化权重）。

论文声称这两种调节器是“双约束”的。想象一下试图打开一个保险箱，需要同时转动两把不同的钥匙。如果黑客试图猜测其中一把钥匙，另一把钥匙会改变锁的结构，使得破解谜题变得不可能。这保护了密钥不被通过代数技巧窃取。

5. 论文声称的成果（结果）

速度：由于不需要沉重的“自举”过程，该方法的速度极快。论文指出，加密耗时约为0.02 毫秒（比眨眼还快）。
体积：加密后的数据非常小（仅 9 KB），而其他方法可能需要数百 KB。
准确性：数学运算完美无误。你可以任意多次地相乘数字，只要最终答案不超过特定限制（即所用素数的大小）。不存在会耗尽的“噪声预算”。
安全性：该系统能抵御标准黑客攻击（IND-CPA）。然而，论文承认一个主要局限性：它对量子计算机不安全。其安全性依赖于分解大整数的难度，而量子计算机可以轻松解决这一问题。

总结类比

可以将此方案想象成一场秘密接力赛。

旧方式：一名选手背着一个沉重且嘈杂的背包。每次传递接力棒时，背包都会变得更重、更嘈杂，直到选手崩溃。
本文的方式：消息被拆分成三个小包。每次传递接力棒时，这三个包会在三名不同的选手之间交换，并且这些包会被神奇地调整大小以保持轻便。选手们永远不会感到疲惫，消息也始终保持清晰。唯一的缺点是：如果超级快速的量子机器人出现，它或许能够破解路线图，但就目前而言，这是在普通计算机上安全保存秘密的一种非常快速且高效的方法。

技术摘要：超越受控噪声：通过动态位置移位实现对称全同态加密

问题陈述
传统的全同态加密（FHE）方案，特别是基于格构造的方案（如 BGV、BFV、CKKS），存在令人望而却步的计算开销和复杂的噪声管理问题。这些方案通常需要昂贵的操作（如自举或重线性化）以在同态乘法期间维持正确性。虽然对称 FHE 提供了一条降低开销的潜在路径，但朴素的对称设计（例如平凡加密 $c = mk$）在实践中会失效，因为在乘法过程中噪声或秘密密钥指数会呈指数级增长，导致该方案无法适用于深层算术电路。现有文献缺乏一种不依赖基于格的复杂性、能有效调控密文增长的对称 FHE 构造。

方法论
本文提出了一种新颖的对称 FHE 方案，用明文分片和动态插位机制取代了传统的噪声管理。其核心架构依赖于模块化加密基础 $c = mk + rp $（其中$ p $为素数模数，$ r$ 为随机标量），该基础天然具有可加性，但在乘法下不稳定。

为了解决乘法不稳定性，作者引入了以下机制：

明文分片：消息 $m$ 被概率性地分割为三个分片（ $m_1, m_2, m_3$ ），使得它们的和等于 $m$ 。每个分片在不同的“位置密钥”（ $k_1, k_2, k_3$ ）下进行加密。
双调节器系统：一组被称为“调节器”的公钥控制乘法过程。这些调节器分为：
- 指数调节器（ $t_i$ ）：将密文分片的乘积重定向至新的逻辑位置。这防止了秘密密钥指数的累积（例如，将 $k^x \cdot k^y$ 转换为与新的位置 $k^z$ 相关的形式），而不是允许它们呈指数级复合增长。
- 系数调节器（ $d_i$ ）：对乘法产生的标量系数进行归一化，确保输出保持正确的代数形式以供解密。
插位机制：该方案在三个位置（ $P_1, P_2, P_3$ ）的循环流上运行。当分片相乘时，结果不会返回到原始位置（这将需要风险较高的逆运算），而是移位到由确定性函数决定的目标位置（例如 $P_1 \times P_1 \to P_2$ ）。这创建了一个闭环系统，其中分片被持续重新洗牌，但永远不会丢失或呈指数级膨胀。

主要贡献

新颖的对称构造：本文引入了首个利用插位和明文分片来调控密文增长的对称 FHE 方案，填补了轻量级密码学文献中的空白。
无噪声的乘法深度：与基于格的方案不同，该方法不会遭受随机噪声累积的影响。“噪声”项（$rp $）在每一步模$ p $约减时都会消失。因此，该方案支持**无界乘法深度**，仅受限于明文容量（即消息的乘积必须小于素数模数$ p$）。
双重绑定安全性：安全性依赖于一种绑定机制，其中指数调节器和系数调节器相互依赖。攻击者无法通过操纵一个调节器来隔离秘密密钥 $k$ ，因为会受到另一个调节器未知参数的阻碍。
形式化安全分析：作者基于两个困难性假设提供了 IND-CPA 安全证明：乘法掩码假设（ $MMA_p$ ）和隐藏模数不可区分性（ $HMP_n$ ）。位置密钥的安全性基于离散对数假设（DLA）和整数分解（IFA）。

结果与性能
本文在标准 Intel i7-10700 CPU 上对提出的方案与成熟的基于格模型（BGV、BFV、CKKS、TFHE）进行了性能评估比较：

效率：提出的方案表现出显著更轻的性能。加密时间约为 0.02 毫秒，同态加法几乎可以忽略不计（0.002 毫秒）。
密文大小：密文大小紧凑，为 9 KB，而基于格的方案通常为数百 KB。
正确性：该方案在 $\mathbb{Z}_p$ 中实现了精确的同态加法和乘法，无需自举或模数切换。
局限性：该方案不具备 IND-CCA 安全性（这是同态方案由于可塑性而具有的一个已知属性），并且不具备后量子安全性，因为其安全性依赖于 DLA 和 IFA，而这些假设易受肖尔算法（Shor's algorithm）的攻击。

意义
本文声称，对于优先考虑速度和紧凑性而非后量子安全性的场景，提供了一种高效、轻量级的传统 FHE 替代方案。通过消除对复杂噪声管理和自举的需求，所提出的“插位”机制为对称同态加密提供了一种确定性方法。作者将该工作定位为资源受限环境（如物联网）的可行解决方案，在这些环境中经典安全假设仍然成立，同时承认需要未来的工作来将插位机制适配到后量子设置中。