💻 computer science

Quantum Key Search Algorithms under Side-channel Attack

本文提出了一种改进的量子密钥搜索算法，该算法利用侧信道攻击诱导的误差分布，实现了相对于经典方法的超二次方加速，并优于像 Glaser 这样的现有量子方法，同时通过高效的 Dicke 态实现解决了输入态制备的挑战。

原作者： Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

发布于 2026-08-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

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

想象一下，你正试图破解一个巨型高科技保险箱的密码锁。在这个数字安全的世界里，这个“锁”是一个加密密钥——一串长长的由 0 和 1 组成的字符串，它保护着你的消息、银行账户和秘密。几十年来，打开这个保险箱的唯一方法就是尝试每一个可能的组合，一个接一个地试，直到你运气好中招为止。这就像是在一个巨大的钥匙环上尝试每一把钥匙；如果有一十亿把钥匙，你可能需要尝试五亿把才能找到正确的那一把。这就是“经典”的处理方式，而且速度很慢。

然后，科学家们发现了一个神奇的工具，叫做“量子计算机”。把它想象成不仅仅是一个更快的计算器，而是一个可以同时观察许多把钥匙的巫师。利用一种被称为格罗弗算法（Grover's algorithm）的著名技巧，这个巫师可以比传统方式更快地找到正确的钥匙——将时间从十亿次尝试缩减到大约三万次。但转折点在于：如果你不必从零开始呢？如果你有一个狡猾的小偷已经窥视了保险箱，并得到了一个“有噪声的”、模糊版本的密钥呢？也许他看到的密钥“大致上”是 101010，但其中一些位元有些模糊。这被称为“侧信道攻击”。这就像是在保险箱上发现了一个指纹，它给了你一个提示，尽管这个提示并不完美。一个大问题是：我们能否利用这些模糊的提示让这个量子巫师变得更聪明、更高效？

这篇由信息工程大学研究团队撰写的论文，深入探讨了正是这样的场景。他们问道：如果攻击者拥有一个带有错误（比如一张模糊的照片）的有噪声密钥，我们如何利用量子计算机比以往任何时候都更快地找到真实的密钥？

研究人员首先研究了普通计算机如何处理这种情况。他们意识到，如果你知道密钥“大致上”是正确的，你就不应该随机猜测。相反，你应该从看起来与有噪声密钥完全一致的密钥开始猜，然后猜那些只有一个微小错误的密钥，接着是两个错误的，以此类推。这就像是在图书馆里寻找书籍，你应该从那些看起来最像你要找的那本书的书籍开始，而不是走进房间后方随便抓取书籍。他们精确计算了这种“聪明”的经典方法需要进行多少次猜测。

接下来，他们构建了一种新的量子算法来执行同样的操作，但利用了量子力学的力量。他们注意到，之前的量子方法试图将搜索空间划分为按几何模式增长（1，然后 10，然后 100）的区块。然而，研究人员发现，这个“有噪声密钥”的提示实际上创造了一个基于错误位数（汉明距离）的特定模式。他们决定不再使用几何模式，而是根据错误的具体数量对密钥进行分组：一组是 0 个错误的密钥，一组是 1 个错误的，一组是 2 个错误的，依此类推。

他们设计了一种策略，让量子计算机逐个处理这些组，并从最有可能包含答案的组开始。为了实现这一点，他们必须解决一个棘手的问题：如何准备量子计算机，使其只观察例如恰好有 3 个错误的密钥，而不浪费时间在其他密钥上。他们通过使用一种特殊的量子态——“狄克态”（Dicke state）解决了这个问题。你可以把狄克态想象成一副组织得非常完美的扑克牌，其中每张牌都有相同数量的红桃。一旦他们拥有了这个有组织的态，他们就可以轻松地翻转这些牌以匹配有噪声的密钥。这种准备过程是非常高效的，不需要额外的、杂乱的设备。

当他们运行模拟实验来测试新方法时，结果令人印象深刻。他们使用了一个 256 位密钥（一个非常长、非常安全的密钥），且错误率极低，仅为 1%（意味着有噪声的密钥 99% 是正确的）。

如果一个标准的经典计算机在没有任何提示的情况下进行搜索，它需要大约 $2^{256}$ 次猜测。
有了有噪声的提示，一个聪明的经典计算机仍需要大约 $2^{62.29}$ 次猜测。
然而，他们的新量子算法只需要大约 $2^{19.77}$ 次猜测。

这意味着他们的量子方法明显比聪明的经典方法更快。他们计算出的“加速因子”为 3.15，高于之前方法（如 Glaser 的方法）所实现的 2.73。简单来说，他们的量子巫师不仅是在同时观察更多的钥匙，而且是在凭借其特定的组织方式，优先观察“正确的”钥匙。

该论文还明确反对使用旧有的、呈几何增长的区块策略（如 Montanaro 的算法）。他们证明了，由于错误遵循特定的“伯努利分布”（一种随机翻转的模式），几何增长的方法并不是最高效的。他们基于“汉明距离”的方法——即按错误的精确数量进行分组——更符合现实情况。

总之，这项研究表明，通过将来自侧信道攻击的“模糊提示”与巧妙组织的量子搜索策略相结合，我们可以比以前更快地破解密钥。虽然这些结果目前是基于模拟和数学证明，而非在物理量子计算机上运行代码，但数学逻辑展示了一条通往超快速量子密钥搜索的清晰路径，这种搜索能超越传统的猜测法和之前的量子尝试。该团队得出结论，这种方法不仅在理论上是成立的，而且在实践中也是可行的，因为他们提出的“狄克态”准备过程可以用可控的步骤完成，且不需要额外的、复杂的硬件。

技术摘要：侧信道攻击下的量子密钥搜索算法

问题陈述
本研究探讨了在攻击者拥有通过侧信道攻击（SCA）获得的含噪声密钥的情况下，针对加密算法的密钥搜索问题。在这种场景下，攻击者获得的密钥 $Y$ 与真实的靶密钥 $k^*$ 之间存在一定的汉明距离（比特翻转数量）。密钥空间的概率分布并非均匀分布，而是由比特错误率（BER） $\alpha$ 决定的 $n$ 次伯努利分布。挑战在于如何高效地搜索这种非均匀密钥空间以找到 $k^*$ ，并充分利用由侧信道攻击提供的先验信息。虽然经典的暴力搜索需要 $O(N)$ 次查询，标准的 Grover 算法提供 $O(\sqrt{N})$ 次查询，但两者都未能充分利用由侧信道攻击引起的特定伯努利分布结构。此外，现有的量子方法（如 Montanaro 算法）在准备具有相等后验概率的密钥块所需的特定初始叠加态时面临困难。

方法论
作者提出了一个涵盖理论建模、算法设计和状态准备的综合框架：

概率建模： 研究假设密钥空间分布遵循独立同分布（i.i.d.）的比特翻转，其概率为 $\alpha$ 。利用贝叶斯定理，证明了候选密钥的后验概率仅取决于其与噪声密钥 $Y$ 的汉明距离 $d$ 。这确立了具有相同汉明距离的密钥具有相同的后验概率。
经典基准： 推导了一种经典密钥搜索算法，该算法按后验概率降序（即从汉明距离 $d=0$ 到 $d=n$ ）遍历候选密钥。基于每个距离处的候选密钥的二项分布，严格计算了期望查询复杂度 $G_c$ 。
改进的量子算法：
- 划分策略： 不同于 Montanaro 算法将密钥空间划分为几何增长的块 $\{1, c, c^2, \dots\}$ ，本文建议根据汉明距离 $d$ 将密钥空间划分为 $(n+1)$ 个块 $\{R_0, R_1, \dots, R_n\}$ 。每个块 $R_d$ 包含所有恰好有 $d$ 个比特错误的 $\binom{n}{d}$ 个候选密钥。
- 搜索执行： 算法按概率降序（即增加 $d$ ）迭代遍历这些块。对于每个块 $R_d$ ，它准备该块内密钥的均匀叠加态，并应用 Grover 搜索。
- 复杂度分析： 通过对每个块中目标密钥存在的概率进行加权，求和各块中 Grover 搜索的成本，从而推导出量子查询复杂度 $G_q$ 。
初始状态准备： 为了解决准备特定块 $R_d$ $R_{d}$ 叠加态的困难，作者建立了候选密钥态与 Dicke 态 $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ 之间的等价关系。他们证明，通过对 Dicke 态 $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ 应用张量积形式的 Pauli-X 门 ( $X^{\otimes Y}$ $X^{\otimes Y}$ )，可以生成与噪声密钥 $Y$ $Y$ 处汉明距离为 $d$ $d$ 的密钥的均匀叠加态。
- 实现： 使用基于 Bärtschi 和 Eidenbenz 研究的短深度、分而治之电路来准备 Dicke 态，该电路不需要辅助量子比特。最终状态通过根据噪声密钥 $Y$ 应用 $O(d)$ 个 X 门获得。

核心贡献

理论推导： 本文对侧信道攻击条件下的经典和量子密钥搜索的计算复杂度进行了严谨的推导，特别模拟了 $n$ 次伯努利分布。
算法改进： 引入了一种改进的量子密钥搜索算法，该算法利用基于汉明距离的块划分策略。研究表明，与 Montanaro 算法使用的几何增长划分相比，该策略更符合侧信道攻击场景中的实际密钥分布。
状态准备解决方案： 通过将问题转化为 Dicke 态准备问题，解决了输入状态准备的瓶颈。研究表明，所需的态可以通过 $O(nd)$ 个 CNOT 门生成，且具有低电路深度（对于离子阱拓扑为 $O(d \log \frac{n}{d})$ ，对于超导拓扑为 $O(\sqrt{nd})$ ），且无需辅助量子比特。

结果
针对 1% 比特错误率（BER, $\alpha = 0.01$ ）的 256 位加密密钥进行的模拟结果显示了显著的性能提升：

复杂度降低： 在 SCA 条件下，经典算法的查询复杂度从 $2^{256}$ （无 SCA）降至 $2^{62.29}$ 。所提出的量子算法进一步将其降低至 $2^{19.77}$ 。
加速因子： 所提出的量子算法相对于 SCA 条件下的经典算法实现了 3.15 倍 的加速。相比之下，Glaser 等人在相同条件下分析 Montanaro 算法时报告的加速因子为 2.73 倍。作者指出，与 [9] 中提出的 Montanaro 几何增长算法相比，其搜索效率提升了 15.38%。
与边界值的比较： 本文声称，在这一特定分布场景下，推导出的量子查询复杂度（ $2^{19.77}$ ）比 Glaser 为 Montanaro 算法估计的上界/下界（ $2^{21.59}$ 和 $2^{17.59}$ ）更加精确且更紧凑。
资源效率： 该状态准备方案被证明适用于短深度电路，并提供了针对 $n=256$ 且 $d=4$ 的具体资源计数（例如 1024 个 CNOT 门，0 个辅助量子比特）。

意义
本文声称其研究为侧信道攻击下的量子密码分析提供了从理论分析到实际实现的完整链条解决方案。通过利用侧信道噪声的特定结构（伯努利分布），所提出的算法实现了相对于经典算法的超二次方加速，优于之前的量子搜索适配方案（如 Montanaro 算法）。利用短深度、无辅助量子比特电路准备必要初始态的能力，解决了实际部署量子密钥搜索的关键障碍。作者断言，这些结果为存在以噪声密钥形式提供的先验信息的情景，提供了更准确的复杂度估计和更高效的搜索策略。未来的工作确定为探索该算法与特定密码（AES, SM4）的集成，以及分析量子噪声的影响。

技术摘要：侧信道攻击下的量子密钥搜索算法

类似论文