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

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

∆X r 的具体计算过程如下.
5,3
由加密流程可知:
第 1 轮: ∆F O = F 1,1 (t 1,1 )⊕ F 1,1 (t 1,1 ⊕r).
1,1
第 2 轮: ∆F O 2,1 = F 2,1 (t 2,1 )⊕ F 2,1 (t 2,1 ⊕∆F ).
O
1,1
第 3 轮: ∆F O = F 3,1 (t 3,1 )⊕ F 3,1 (t 3,1 ⊕∆F ) ∆F O = F 3,2 (t 3,2 )⊕ F 3,2 (t 3,2 ⊕r).
,
O
3,1 2,1 3,2
由此可得:

O
r
∆ r = ∆X 5,3 = ∆F ⊕r
3,1
O
= (F 3,1 (t 3,1 )⊕ F 3,1 (t 3,1 ⊕∆F ))⊕r
2,1
O
= (F 3,1 (t 3,1 )⊕ F 3,1 (t 3,1 ⊕ F 2,1 (t 2,1 )⊕ F 2,1 (t 2,1 ⊕∆F )))⊕r
1,1
= (F 3,1 (t 3,1 )⊕ F 3,1 (t 3,1 ⊕ F 2,1 (t 2,1 )⊕ F 2,1 (t 2,1 ⊕ F 1,1 (t 1,1 )⊕ F 1,1 (t 1,1 ⊕r))))⊕r (2)
b
当 r 取遍 [2 −1] 时, 可得到 ∆-序列 Γ 1 = (∆ 1 ,∆ 2 ,...,∆ 2 b −1 ).
由公式 (2) 的最后一行可知, ∆ r 依赖于 t 1,1 , t 2,1 和 t 3,1 的值, 又由公式 (1) 可知, t 2,1 和 t 3,1 由 t 1,1 决定. 而根据命
题 1, t 1,1 有 2 个可能值, 故 ∆-序列 Γ 1 有 2 个可能值. 证毕.
ℓ
ℓ

b-δ-集
X X X X X X
1,1 1,2 1,3 1,1 1,2 1,3
Δx 0 0 r 0 0
k k k k
1,1 1,2 1,1 1,2
Δy
F 1,1 F 1,2 F 1,1 * F 1,2
1,1 t t 1,2 1,1 t t 1,2
Δy X 0 X Δx X X 0 X r X
2,1 k 2,2 k 2,3 * 2,1 k 2,2 k 2,3
2,1 2,2 2,1 2,2
Δz 0
F 2,1 F 2,2 F * F
t t t 2,1 t 2,2
2,1 2,2 2,1 2,2
Δz X Δx X Δy X X r X X
3,1 k 3,2 k 3,2 3,3 * 3,1 k 3,2 k * 3,3
3,1 3,1 3,2
Δx Δy
F F F * F *
t 3,1 t 3,2 t 3,1 t 3,2
3,1 3,2 3,1 3,2
0 X 0 X Δz X * X X X
4,1 k 4,2 k 4,3 4,1 k * 4,2 k 4,3
4,1 4,2 4,1 4,2
? ?
F F F F
4,1 4,2 4,1 4,2
t t t t
4,1 4,2 4,1 4,2
0 Δz 0 ? ? *
X X X X X X
5,1 5,2 5,3 5,1 5,2 5,3
*: 可计算的差分 ?: 未知差分 Δ-序列
(a) 4 轮中间相遇区分器 (b) b-δ-集的构造
图 3 3 分支 Type-III 型 GFS 的 4 轮中间相遇区分器和 b-δ-集 的构造

2.2 3 分支 Type-III 型 GFS 的 6 轮 DS-MITM 攻击及复杂度分析
本节基于命题 1 构造的 4 轮中间相遇区分器, 分别向前向后扩展 1 轮, 实现 3 分支 Type-III 型 GFS 的 6 轮
DS-MITM 攻击, 攻击包括预计算阶段和在线阶段, 具体过程见图 2(b).
ℓ
预计算阶段: 详细过程如定理 1 所示, 并将 ∆-序列 Γ 1 的 2 种可能值存储在以 ∆ r 为索引的表 T 1 中, 其中

b
r ∈ [2 −1].
在线阶段: 包括数据收集和密钥恢复两部分.
1) 数据收集. 包括如下 3 个步骤.
ℓ
(1.1) 任意选取两个向量 m, a ∈ F , 如图 2(b) 所示, 构造满足区分器第 1 分支输入差分为 ∆x 的两个明文集
2