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

2258 软件学报 2026 年第 37 卷第 5 期

and O(2 3ℓ/2 ·ℓ) quantum queries. The results demonstrate that the time complexity in Q1 model is significantly reduced compared with
classical scenarios.
Key words: generalized Feistel structure; quantum meet-in-the-middle attack; Q1 model; quantum claw finding algorithm; Grover’s algorithm

分组密码在网络通信和信息安全领域发挥着极其重要的作用. 1970 年, Feistel 等人 [1] 在设计 Lucifer 算法时提
出 Feistel 结构, 该结构因 DES 算法 [2] 的广泛使用而流行. 广义 Feistel 结构 (generalized Feistel structure, GFS) 是
Feistel 结构的变体形式, 通常采用多分支非平衡 Feistel 结构, 通过不同的置换操作 (如非线性替换与循环移位) 来
[3]
[4]
增强算法的混淆与扩散效果, 且保留了 Feistel 结构加解密一致的优点, 如: Type-I/III 型 GFS , n-cell 型 GFS 等.
这 3 类 GFS 都通过将输入数据划分为多个子块, 允许在单轮操作中对多个子块进行并行处理, 有效提升了加解密
效率.
1977 年, Diffie 等人 [5] 在对 DES 算法进行安全性分析时首次提出了中间相遇攻击, 其思想是利用存储复杂度
来降低攻击过程中所需的时间复杂度. Demirci 等人 [6] 在 FSE 2008 利用中间相遇攻击的思想, 构造了 AES 算法 [7]
的 4 轮中间相遇区分器, 并提出了该算法的 8 轮中间相遇攻击, 被称为 Demirci-Selçuk 中间相遇 (Demirci-Selçuk
meet-in-the-middle, DS-MITM) 攻击. 随后, 研究者们基于文献 [6] 的工作开展了大量抵抗分组密码算法中间相遇
攻击的安全性研究 [7−11] . 2010 年, Dunkelman 等人 [8] 改进了文献 [6] 的工作, 结合多重集、差分枚举和密钥桥技术,
有效提高了 AES 算法 DS-MITM 攻击效率. 2014 年, Guo 等人 [12] 首次针对 Feistel 结构提出了 6 轮 DS-MITM 攻
击. 2017 年, Dong 等人 [13] 构造了 3 分支 Type-I 型 GFS 的 9 轮中间相遇区分器, 向后扩展 1 轮实现了该结构的 10
轮 DS-MITM 攻击. 2019 年, 邓元豪等人 [14] 构造了 Type-III 型 GFS 的 d+1 轮中间相遇区分器, 向前扩展 1 轮实现
了该结构的 d+2 轮密钥恢复攻击.
随着量子计算的发展, 为设计后量子时代的分组密码算法, 研究者需要考虑分组密码算法在量子环境下的安
全性. Grover 算法 [15] 是一种在无序数据库中搜索目标条目的标准搜索算法, 相较于经典环境, 它实现了搜索目标
条目所需时间的二次加速. 2000 年, Brassard 等人 [16] 在文献 [15] 的基础上提出了量子振幅放大 (quantum amplitude
amplification, QAA) 技术, 并指出 Grover 算法可以看作是量子振幅放大算法的一种特例. 随后, Buhrman 等人 [17] 采
用 QAA 技术提出了量子爪搜索算法, 用于解决碰撞问题. 这些算法的提出为后续量子 DS-MITM 攻击的发展提供
了理论基础.
根据 Zhandry 等人 [18] 提出的量子环境中伪随机函数 (pseudo random function, PRF) 安全性的概念, Kaplan 等
人 [19] 针对密码算法的量子分析提出了两种模型: 标准安全模型 (Q1 模型) 和量子安全模型 (Q2 模型). 在 Q1 模型
中, 攻击者可以访问量子计算机执行任何离线计算, 但只能以经典的方式执行在线查询; 而在 Q2 模型中, 攻击者
除了进行离线量子计算外, 还可以利用量子叠加态对量子预言机进行在线查询. 在量子环境下, 分组密码的安全性
分析成为学者们关注的焦点, 出现了大量针对 Feistel 结构以及 GFS 的量子安全性分析成果. 2010 年, Kuwakado
等人 [20] 构造了 3 轮 Feistel 结构的周期函数, 将其作为量子区分器, 同时利用 Simon 算法 [21] 搜索该函数的周期, 研
究表明, 3 轮 Feistel 结构在量子环境下不再安全. 2019 年, Dong 等人 [22] 结合 Grover 算法和 Simon 算法给出
Feistel 结构以及两类 GFS 的量子区分器的构造方法, 证明了针对这些结构的量子安全性分析所需的时间复杂度
均优于 Grover 量子暴力搜索的时间复杂度. 在 PQCrypto 2020, Hodžić等人 [23] 对 Type-III 型 GFS 进行了分析, 构
造了该结构的 5 轮量子区分器. 随后, 于博等人 [24] 提出了针对若干非平衡 GFS 的量子密码分析, 相较于暴力穷举
搜索, 该攻击的效率更高. 同年, 李艳俊等人 [25] 在考虑轮函数内部结构的情况下对 MIBS 算法进行了 7 轮量子密钥
恢复攻击, 该攻击不仅使用了较少的量子比特, 而且时间复杂度更低. 2023 年, 邹剑等人 [26] 将 Simon 量子区分器的
周期函数和生日攻击的思想相结合, 提出了一种针对 Feistel、Misty 等结构的新型密钥恢复攻击, 该攻击所需的存
储复杂度和时间复杂度相较于现有的密钥恢复攻击更低.
近年来, 学者们将传统分析方法和量子分析方法相结合, 提出了量子差分密码分析 [27] 、量子 DS-MITM 攻击 [28]
等. 2018 年, Hosoyamada 等人 [28] 针对 Feistel 结构进行了 6 轮量子 DS-MITM 攻击, 结果表明, 相较于文献 [12] 中
给出的 6 轮 DS-MITM 攻击的结果, 量子计算机可以显著提升 DS-MITM 攻击的效率. 2022 年, Wang 等人 [29] 利用