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

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

定理 (A 0 ,A) ∈ F 3ℓ×2 满足命题 2 b-δ-集 M = {(A 0 ⊕(r,0 ℓ ,0 ℓ )) ∈ F | r ∈
3ℓ
3. 输入对
2 中区分器的输入, 利用 A 0 构造 2
b ℓ
{0,1,...,2 −1}}, 则可得 ∆-序列 Γ 5 = (∆ 1 ,∆ 2 ,...,∆ 2 b −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
1 F 1 k 1 F 1 k
Δy *
0 X 2,1 0 X 2,2 Δy X 2,3 0 X 2,1 0 X 2,2 * X 2,3
2 F 2 k 2 F 2 k
0

0 X 3,1 Δy X 3,2 Δy X 3,3 0 X 3,1 * X 3,2 * X 3,3
3 F 3 k 3 F 3 k
0

Δy X Δy X 0 X X
4,1 4,2 4,3 * 4,1 * X 4,2 * X 4,3
4 F 4 k 4 F 4 k
Δ y⊕Δz *

Δy X 0 X Δz X X X X
5,1 5,2 5,3 * 5,1 * 5,2 * 5,3
5 F 5 k 5 F 5 k
Δz
*
0 X Δz X 0 X X X X
6,1 6,2 6,3 * 6,1 * 6,2 * 6,3
6 F 6 k 6 F 6 k
?

Δz 0 Δz * ?
*
X X X X X X
7,1 7,2 7,3 7,1 7,2 7,3
Δ-序列 *: 可以计算的差分 ?: 未知差分
(a) 6 轮中间相遇区分器 (b) b-δ-集的构造
图 6 3-cell 型 GFS 的 6 轮中间相遇区分器和 b-δ-集 的构造

证明: 如图 6(b) 所示, 设 X 1,1 ∈ F 的 b 比特活跃, 输入对 (A 0 ,A) ∈ F 3ℓ×2 的差分 ∆A = A 0 ⊕ A = (r,0 ℓ ,0 ℓ ), 根据集合
ℓ
2 2
b (A 0 ,A 0 ⊕(r,0 ℓ ,0 ℓ )), r ∈ [2 −1], 将其加密 r r r r
b
M 可得 2 −1 个输入对 6 轮得到差分为 ∆X = (∆X ,∆X ,∆X ) 的输出对.
7 7,1 7,2 7,3
则 ∆ r = ∆X r 的具体计算过程如下.
7,1
由加密流程可知:
第 1 轮: ∆F = F 1 (t 1 )⊕ F 1 (t 1 ⊕r).
O
1
第 4 轮: ∆F = F 4 (t 4 )⊕ F 4 (t 4 ⊕∆F ).
O
O
4 1
第 5 轮: ∆F = F 5 (t 5 )⊕ F 5 (t 5 ⊕∆F ).
O
O
5 1
由此可得:

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