Page 402 - 《软件学报》2025年第7期

许垠松 等: 分组密码结构的低数据量子密钥恢复攻击 3323

时, 针对 9 轮 Type-1 GFS-KF 的密钥恢复攻击, 本文的方法可与文献 [21] 在复杂度乘积指标上保持一致, 但属于
O(1) 明密文. 对于类 SMS4 GFS-FK 和类 MARS GFS-FK, 本文给出了在 Q1 模型下, 仅需选
选择明文攻击且仅需
择常数项级别规模的明密文即可恢复密钥的方案.

表 1 几类分组密码结构的密钥恢复攻击复杂度比较

目标结构 环境 轮数 时间 (T) 数据 (D) 经典存储 (M) 量子比特 (Q) 复杂度乘积 (TDMQ) 文献
2 n/2
Q2, qCPA 3 O(n) O(2 n/2 ) － O(n) O(n 2 ) [20]
2 n/2
Lai-Massey Q2, qCCA 4 O(n) O(2 n/2 ) － O(n) O(n 2 ) [20]
Q1, CPA 3 O(2 n/4 ) O(1) － O(n) O(n2 n/4 ) 本文
Q1, CPA 6 O(2 3n/4 ) O(2 n/4 ) O(2 n/4 ) O(n) O(n2 5n/4 ) [21]
2 3n/4
Misty L-KF Q2, qCPA 6 O(n2 n/4 ) O(2 n/2 ) － O(n) O(n 2 ) [6]
Q1, CPA 6 O(2 5n/4 ) O(1) － O(n) O(n2 5n/4 ) 本文
Q1, CPA 6 O(2 3n/4 ) O(2 n/4 ) O(2 n/4 ) O(n) O(n2 5n/4 ) [21]
2 3n/4
Misty L-FK Q2, qCPA 6 O(n2 n/4 ) O(2 n/2 ) － O(n) O(n 2 ) [6]
Q1, CPA 6 O(2 3n/4 ) O(1) － O(n) O(n2 3n/4 ) 本文
Q1, CCA 6 O(2 3n/4 ) O(2 n/4 ) O(2 n/4 ) O(n) O(n2 5n/4 ) [21]
2 3n/4
Misty R-KF Q2, qCPA 6 O(n2 n/4 ) O(2 n/2 ) － O(n) O(n 2 ) [6]
Q1, CPA 6 O(2 5n/4 ) O(1) － O(n) O(n2 5n/4 ) 本文
Q1, CCA 6 O(2 3n/4 ) O(2 n/4 ) O(2 n/4 ) O(n) O(n2 5n/4 ) [21]
2 3n/4
Misty R-FK Q2, qCPA 6 O(n2 n/4 ) O(2 n/2 ) － O(n) O(n 2 ) [6]
Q1, CPA 6 O(2 3n/4 ) O(1) － O(n) O(n2 3n/4 ) 本文
Q1, CCA d 2 O(2 (2d−1)n/2d ) O(2 n/2d ) O(2 n/2d ) O(n) O(n2 (2d+1)n/2d ) [21]
2
Type-1 GFS-KF Q2, qCCA d −d +3 O(n/d) O(2 n/d ) － O(n) O(n /d ·2 n/d ) [6]
2
Q1, CPA 3d −3 O(2 n/2d ) O(1) － O(n) O(n2 n/2d ) 本文
2
Q2, qCPA 2d +1 O(n/d) O(2 n/d ) － O(n) O(n /d ·2 n/d ) [6]
类SMS4 GFS-FK
Q1, CPA 2d −1 O(2 n/2d ) O(1) － O(n) O(n2 n/2d ) 本文
2
Q2, qCPA 2d +1 O(n/d) O(2 n/d ) － O(n) O(n /d ·2 n/d ) [6]
类MARS GFS-FK
Q1, CPA 2d −1 O(2 n/2d ) O(1) － O(n) O(n2 n/2d ) 本文
注: 分组长度为 n 比特; d 为分支数

本文第 1 节将介绍 Lai-Massey 结构、Misty 结构、Type-1 型 GFS、类 SMS4 GFS 和类 MARS GFS 的分析研
究现状. 第 2 节介绍本文所攻击分组密码结构的基础知识和概念. 第 3 节介绍 Grover 算法及其应用. 第 4–8 节分
别介绍了 Lai-Massey 结构、Misty 结构、Type-1 型 GFS、类 SMS4 GFS 和类 MARS GFS 的密钥恢复攻击. 最后
总结全文.

1 分组密码结构的密钥恢复攻击相关工作

1990 年, Lai 等人 [3] 提出了 IDEA 算法. Vaudenay 推广了 IDEA 所采用的加密结构, 并称其为 Lai-Massey 结
构. 3 轮和 4 轮 Lai-Massey 结构已被 Vaudenay 等人 [22] 分别证明可以抵抗选择明文攻击 (CPA) 和选择密文攻击
(CCA). Luo 等人 [23] 证明了多轮 Lai-Massey 结构是超生日界限 CCA 安全的. 在量子选择明文攻击 (qCPA) 环境下,
Mao 等人 [20] 提出了 3 轮 Lai-Massey 结构的量子区分器, 且在量子选择密文攻击环境下, 提出了 4 轮 Lai-Massey
结构的量子区分器. 借助于 Simon 算法, Mao 等人提出的量子区分器可在多项式时间内进行区分. 他们还利用
Grover Meets Simon 方法对 Lai-Massey 结构的攻击轮数进行拓展.
Misty 结构 [4] 作为 Feistel 结构的变体, 由 Matsui 在 1997 年 FSE 会议上提出的分组密码 Misty 推广而来, 可分
为 Misty L 和 Misty R 结构. 2019 年, Luo 等人 [24] 分别提出了 Misty L 和 Misty R 结构的 3 轮量子区分器, 并在