Page 380 - 《软件学报》2026年第5期

杜小妮 等: 三类非平衡广义 Feistel 结构的量子中间相遇攻击 2259

Grover 和量子爪搜索算法对 7 轮 AES 进行量子 DS-MITM 攻击时, 提出了 3 种权衡数据/内存/时间复杂度的量子
方案, 进一步降低了攻击的时间复杂度. 次年, 受文献 [28] 的启发, Xu 等人 [30] 提出了 Feistel 结构的 7 轮量子 DS-
MITM 攻击, 改进了文献 [12] 的工作. 2024 年, Zou 等人 [31] 构建了 Misty L-KF 结构 [32] 的 5 轮区分器, 并向前扩展
1 轮实现了 6 轮量子 DS-MITM 攻击, 结果表明, 相较于经典环境下的 DS-MITM 攻击, 该攻击所需的时间复杂度
更低.
通过对文献 [13,14,22−24] 的研究发现, 不仅 Type-I/Type-III 型 GFS 在经典 DS-MITM 攻击下的轮数有待提
高, 而且 n-cell 型 GFS 的 DS-MITM 攻击尚为空白. 虽然已有相关的量子密码分析结果, 但有关三者的抗量子 DS-
MITM 攻击的研究仍是空白. 作为一种新的攻击方式, 量子 DS-MITM 攻击结合量子计算的优势和中间相遇的思
想, 相较于经典 DS-MITM 攻击, 能够显著提升攻击效率. 因此, GFS 量子 DS-MITM 攻击的安全性有必要进一步
研究. 鉴于此, 本文首先对 3 分支 Type-III 型、3 分支 Type-I 型和 n-cell 型 GFS 进行更长轮数的 DS-MITM 攻击,
其次在 Q1 模型下对这 3 类 GFS 进行量子 DS-MITM 攻击, 最后给出相应的复杂度分析, 具体结果见表 1. 主要贡
献如下.

表 1 3 类 GFS 的 (量子) DS-MITM 攻击结果

结构类型 环境 轮数 时间复杂度 数据复杂度 存储复杂度 参考来源
2ℓ
2ℓ
经典 5 O(2 ) O(2 3ℓ/2 ) O(2 ) 文献[14]
ℓ
3ℓ
2ℓ
Type-III型 * 经典 6 O(2 ) O(2 ) O(2 ) 第2.2节
ℓ
2ℓ
Q1 6 O(2 3ℓ/2 ·ℓ) O(2 ) O(2 ·ℓ) 第2.3节
2ℓ
2ℓ
2ℓ
经典 10 O(2 ) O(2 ) O(2 ) 文献[13]
2ℓ
2ℓ
ℓ
Type-I型 * 经典 11 O(2 ) O(2 ) O(2 ) 第3节
ℓ
2ℓ
Q1 11 O(2 3ℓ/2 ·ℓ) O(2 ) O(2 ·ℓ) 第3节
经典 2(n+1) O(2 ) O(2 ) O(2 ) 第4.2节
2ℓ
ℓ
2ℓ
n-cell型
2ℓ
ℓ
Q1 2(n+1) O(2 3ℓ/2 ·ℓ) O(2 ) O(2 ·ℓ) 第4.2节
注: *表示本文仅探讨3分支Type-III型与Type-I型GFS

(1) 研究 3 分支 Type-III 型 GFS 的 (量子) DS-MITM 攻击. 首先, 结合多重集和差分枚举技术构建 4 轮中间相
遇区分器, 分别向前向后扩展 1 轮进行 6 轮 DS-MITM 攻击; 其次, 在 Q1 模型下利用 Grover 和量子爪搜索算法进
行 6 轮量子 DS-MITM 攻击, 所需要的时间复杂度为 O(2 3ℓ/ 2 ·ℓ) 次量子查询, 比经典环境下 DS-MITM 攻击所需的
时间复杂度更低.
(2) 与 (1) 的原理类似, 利用文献 [13] 的 9 轮中间相遇区分器, 对 3 分支 Type-I 型 GFS 进行 (量子) DS-MITM
攻击. 首先, 在经典环境下, 进行 11 轮 DS-MITM 攻击, 相较文献 [13], 攻击轮数更高, 且降低了所需的数据复杂度;
其次, 在量子环境下, 实现 3 分支 Type-I 型 GFS 的 11 轮量子 DS-MITM 攻击, 相应的时间复杂度为 O(2 3ℓ/ 2 ·ℓ) 次
量子查询.
(3) 与 (1) 的原理类似, 研究 n-cell 型 GFS 的 (量子) DS-MITM 攻击方案. 首先, 以 3-cell 型 GFS 为例, 构建 6
轮中间相遇区分器, 并对其进行 8 轮 DS-MITM 攻击和量子 DS-MITM 攻击, 攻击的时间复杂度分别为 O(2 ) 次 8
2ℓ
轮加密和 O(2 3ℓ/ 2 ·ℓ) 次量子查询. 其次, 将该结论扩展到 n-cell 型 GFS, 对其构建 2n 轮中间相遇区分器, 并进行
2(n+1) 轮 DS-MITM 攻击和量子 DS-MITM 攻击. 相应地, 攻击的时间复杂度分别为 O(2 ) 次 2(n+1) 轮加密和
2ℓ
O(2 3ℓ/ 2 ·ℓ) 次量子查询.
本文第 1 节给出了必要的符号说明, DS-MITM 攻击的基本原理以及相关量子算法的基础知识. 第 2 节对 3 分
支 Type-III 型 GFS 进行了 6 轮 (量子) DS-MITM 攻击, 并给出了相应的复杂度分析. 第 3 节对 3 分支 Type-I 型 GFS
进行了 11 轮 (量子) DS-MITM 攻击. 第 4 节以 3-cell 型 GFS 为例分析了 n-cell 型 GFS 的 (量子) DS-MITM 攻击
方案. 最后总结全文.