Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

本文提出了一种针对轻量级混合 ARX-SPN 密码 GFSPX 的量子比特优化量子电路实现方案，并通过并行化 Grover 攻击评估了其抗量子安全性，结果显示其总量子成本为 $1.12 \times 2^{159}$ 个门，尽管该数值低于 NIST 第 1 级阈值，但相较于其他轻量级设计仍展现出更优越的抵抗能力。

要点

想象你拥有一把非常特殊、轻量级的数字锁（称为GFSPX），专为保护智能传感器或 RFID 标签等小型设备上的数据而设计。这把锁旨在实现高速运行并极低能耗，因此完美契合“物联网”的需求。

然而，一种名为量子计算机的新型“超级工具”正在兴起。与逐一把钥匙逐一检查的普通计算机不同，量子计算机可以同时检查大量钥匙，从而可能更快地破解这些锁。本文提出了一个简单的问题：如果量子计算机试图破解这把特定的锁，实际难度会有多大？

以下是他们研究发现的分解说明，采用日常类比：

1. 锁的设计：混合引擎

GFSPX 锁并非仅由单一机制构建。它是一种混合体，就像一辆同时使用汽油引擎和电动马达的汽车。

• “汽油”部分（ARX）： 这部分使用简单的数学运算（加法、旋转、异或），效率极高，但在将变化扩散到数据中时可能稍显缓慢。
• “电动”部分（SPN）： 这部分使用复杂的替换网络（类似于洗牌），能非常迅速地扩散变化。
• 结果： 通过结合两者，该锁既快速又高效。作者专门为量子计算机构建了该锁的数字蓝图，以精确观察其内部运作方式。

2. 量子蓝图：构建电路

为了测试这把锁，研究人员必须构建一个“量子电路”。你可以将其想象为建造一个微型、可逆的工厂，其中每一步都可以完美撤销（因此不会丢失任何信息）。

• 挑战： 量子计算机非常脆弱。你不能随意复制数据；你必须非常小心地处理“量子比特”（即量子位，就像微小的旋转陀螺）。
• 解决方案： 研究人员优化了设计，以使用尽可能少的量子比特（共 209 个）。他们在数学部分使用了一种称为“行波进位加法器”的巧妙技巧，这就像一条非常高效的装配线，不浪费空间。
• 占用空间： 最终蓝图非常紧凑，需要相当于 209 个量子比特的“工厂面积”，以及特定数量的步骤（门）来执行一次完整的加密。

3. 攻击： “Grover"搜索

为了破解这把锁，量子计算机使用Grover 算法。

• 类比： 想象你有一个巨大的图书馆，里面有 $2^{128}$ 本书（这是一个大得难以想象的数量），其中只有一本书拥有正确的钥匙。
  • 普通计算机就像一位一次只检查一本书的图书管理员。这需要耗费永恒的时间。
  • 量子计算机则像一位神奇的图书管理员，可以同时检查多本书。它找到正确书籍所需的时间大约只需平方根级别。
• 陷阱： 为了确保量子计算机不会选错书（即避免“假阳性”），研究人员让计算机同时检查三把不同的锁（使用三组不同的明文/密文对）。如果一把钥匙能同时打开这三把锁，那它肯定就是正确的钥匙。

4. 裁决：坚固，但并非“后量子”证明

研究人员计算了此次量子攻击的总“成本”。

• 成本： 他们发现，破解这把锁需要巨大的计算能力，大约相当于 $1.12 \times 2^{159}$ 次运算。
• 标准： 美国国家标准与技术研究院（NIST）为未来设定了“安全门槛”。要被视为真正能抵御量子计算机（1 级安全），一把锁的成本至少需要达到 $2^{170}$。
• 结果： GFSPX 锁低于安全门槛。它不足以符合最严格的后量子标准。
  • 然而，论文指出，与其他轻量级锁相比，GFSPX 实际上是最难破解的之一。它处于一个“甜蜜点”：对于小型设备而言非常高效，同时仍能提供对量子攻击的适度抵抗，即使它未能通过最高级别的安全测试。

5. 结论

论文总结道，虽然这种混合锁对于当前资源受限的设备非常出色，但 128 位的密钥长度实在太小，无法在未来抵御坚定的量子攻击。

• 权衡： 你可以拥有一把微小且快速的锁（适合当今的传感器），或者一把巨大且缓慢的锁（适合未来的量子安全），但这种特定设计试图兼顾两者，却在“未来安全”方面略微不足。
• 未来建议： 为了使该设计真正具备抗量子能力，作者建议要么延长密钥长度（例如 192 位或 256 位），要么调整数学部分，使其更难被量子计算机处理。

简而言之：GFSPX 是一把非常巧妙、高效的锁，比其大多数同类更难破解，但若不进行升级，它还不够强大，无法抵御未来超级强大的量子计算机。

技术摘要

技术摘要：混合 ARX-SPN 密码体制 GFSPX 的量子电路实现与 Grover 密码分析

问题陈述
量子计算的出现从根本上挑战了经典对称密钥原语的安全性。虽然 Shor 算法威胁着公钥密码学，但 Grover 算法为无序搜索提供了二次加速，有效地将对称密钥构造的安全裕度减半。因此，为物联网（IoT）和 RFID 等资源受限环境设计的轻量级分组密码（BCs）需要对其后量子韧性进行严格重新评估。具体而言，需要量化对结合加法 - 旋转 - 异或（ARX）和替换 - 置换网络（SPN）范式的混合设计发动密钥恢复攻击所需的量子资源。

方法论
作者提出了 GFSPX 的综合性量子电路实现与 Grover 密码分析。GFSPX 是一种轻量级分组密码，具有 64 位数据块和 128 位秘密密钥。GFSPX 采用 4 分支广义 Feistel 结构（GFS），集成了两个不同的功能块：基于 ARX 的函数（$F_1$）用于非线性，以及 32 位 SPN 结构（$F_2$）用于快速扩散。

方法论分为三个阶段：

1. 量子电路实现：将 GFSPX 的经典结构映射为可逆量子电路。作者利用 Feistel 网络固有的可逆性来最小化辅助量子比特（ancilla qubit）的使用。
   • $F_1$（ARX）：使用基于 Cuccaro 等人架构的紧凑行波进位加法器（RCA）实现。这种方法通过省略模加法的最终进位位，并利用原位多数（MAJ）和 UnMajority-and-Add（UMA）门，最大限度地减少了量子比特开销。
   • $F_2$（SPN）：S 盒层（基于 PRESENT）使用最小集合的 CNOT 和 Toffoli 门合成，无需额外辅助量子比特。置换层（P 层）通过可并行化的 SWAP 门实现，以保持低电路深度。
   • 密钥调度：128 位主密钥调度被实现为包含 113 位左循环移位、S 盒替换和轮计数器异或的幺正演化，并针对原位执行进行了优化。
2. 资源估算：使用标准分解指标（NOT 和 CNOT 成本 = 1，Toffoli 成本 = 6）计算量子成本。分析评估了基线成本（不包括 SWAP 路由开销）和上限（将 SWAP 分解为三个 CNOT）。
3. Grover 密码分析：构建了一个并行化的 Grover 预言机（$U_f$）以评估该密码体制对抗密钥恢复攻击的能力。为了消除 128 位密钥空间中的虚假匹配，预言机利用三个明文 - 密文对（$r=3$）。攻击复杂度通过将预言机的资源指标乘以最优 Grover 迭代次数（$\approx \frac{\pi}{4}2^{64}$）进行估算。

主要贡献

• 优化的量子实现：本文提供了针对 GFSPX 的量子比特优化量子电路，实现了209 个量子比特的占用空间。该设计实现了32,498个门的基线量子成本，电路深度为7,617。
• 混合架构分析：本研究详细阐述了混合 ARX-SPN 设计的资源分布，表明虽然模加原语主导了总门数，但 SPN 组件中并行化的置换层有助于保持具有竞争力的门 - 深度比。
• 定量安全评估：作者使用三个明文 - 密文对构建了 Grover 预言机，并在 NIST 的 MAXDEPTH 框架下计算了总攻击成本。分析显示，对于$r=3$，总量子攻击成本约为$1.12 \times 2^{159}$个门。
• 比较基准测试：该实现与其他轻量级密码（如 PRESENT、GIFT、SIMON、SPECK）进行了基准测试。GFSPX 在比较的设计中实现了最低的成本 - 深度比（4.27），表明其具有高并行执行效率。

结果

• 资源指标：完整的 20 轮 GFSPX 电路需要 209 个量子比特。基线成本为 32,498，当包含 SWAP 路由开销时上升至 47,789。电路深度为 7,617。
• 攻击复杂度：密钥恢复攻击的总量子成本估算为$1.12 \times 2^{159}$（针对$r=3$）。
• 安全分类：在 NIST 后量子密码学框架下，Level 1 安全阈值（相当于 AES-128）要求总攻击成本至少为$2^{170}$。GFSPX 的估算成本（$2^{159}$）低于此阈值。
• 设计权衡：虽然 GFSPX 表现出比许多纯 SPN 设计（集中在$2^{152}$左右）更高的量子攻击抵抗力，但其 128 位密钥长度在结构上不足以实现针对高级量子对手的 NIST Level 1 安全。混合设计的成本深受 ARX 组件（模加）的影响，使其安全特征更接近于基于 ARX 的密码体制，如 SIMON 和 SPECK。

意义
本文声称其发现为下一代密码设计中经典硬件效率与量子韧性之间的平衡提供了关键见解。该研究强调了一个根本性的权衡：虽然混合 ARX-SPN 构造提供了比纯 SPN 设计更强大的经典性能和更好的量子抵抗力，但 128 位密钥长度在结构上仍不足以实现针对高级量子对手的 NIST Level 1 安全。作者建议未来的研究应侧重于扩展密钥长度（例如至 192 或 256 位）或优化可逆模加原语以提高安全裕度。本工作中建立的方法论为评估资源受限环境中的其他混合设计提供了一个严格的框架。