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

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

⟩ ⟩ ⟩
|ψ 7 ⟩ = |ψ 6 ⟩k 0,2 k 5,1 k 5,2 .

b {C 0 ,C 1 ,...,C 2 b −1 }, 解密 1

(2.6) 根据 2 −1 组候选子密钥 (k 5,1 ,k 5,2 ) 和密文集 轮得到 ∆-序列 Γ 2 , 可得:

|ψ 8 ⟩ = |ψ 7 ⟩|Γ 2 ⟩,
再利用量子删除操作, 仅保留 |ψ 1 ⟩ 和 |Γ 2 ⟩, 得到最终的叠加态:

∑ 1
|ψ 9 ⟩ = √ |I 1 ⟩|I 2 ⟩|Γ 2 ⟩,
2 2ℓ
I 1 ∈T P ,I 2 ∈T C
′
同时, 将 Γ 2 存储在以 (I 1 , I 2 ) 为索引的表 T 中.
4
′ ′
(2.7) 利用量子爪搜索算法将表 T 和 T 进行匹配, 以获得正确密钥.
1
4
下面分析攻击的时间和存储复杂度.
在预计算阶段, 步骤 (1.2) 和 (1.4) 所需的时间复杂度分别为 O(2 ) 和 O(2 ) 次量子查询, 故所消耗的总时间为
ℓ
ℓ/ 2
ℓ
2ℓ
ℓ
O(2 ℓ/ 2 +2 ) ≈ O(2 ) 次量子查询. 此外, 该阶段还需要 O(2 ·ℓ) 个量子比特存储表 T .
′
1
在线阶段的复杂度主要由步骤 (2.7) 决定, 即使用量子爪搜索算法, 从表 T 和 T 中搜索爪 ((∆z,∆y),(I 1 ,I 2 )) 使
′
′
4
1
ℓ 6ℓ (2 b −1)×ℓ . 根

得函数 f(∆z,∆y) = g(I 1 ,I 2 ), 其中, 函数 f : ∆z×∆y → Γ 1 , ∆z,∆y ∈ F , 函数 g : I 1 ×I 2 → Γ 2 , I 1 ,I 2 ∈ F , Γ 1 ,Γ 2 ∈ F

2 2 2
据算法 1, 当 l = 2 时, 该阶段的时间复杂度为 O(2 3ℓ/ 2 ·ℓ) 次量子查询.
ℓ
综上所述, 在 Q1 模型下对 3 分支 Type-III 型 GFS 进行 6 轮量子 DS-MITM 攻击所需要的复杂度如下.
ℓ
(1) 数据复杂度为 O(2 ) 个选择明文.
′ ℓ ℓ/ 2 ℓ ℓ 3ℓ/ 2 ·ℓ) 次量子查
(2) 由于构造表 T 和运行爪搜索算法 (l = 2 ) 的时间复杂度分别为 O(2 +2 ) ≈ O(2 ) 和 O(2
1
O(2 3ℓ/ 2 ·ℓ) 次量子查询.
询, 因此, 总的时间复杂度为
′ ℓ 2ℓ ℓ 2ℓ
(3) 构造表 T 和运行爪搜索算法筛选密钥 (l = 2 ) 需要 O(2 ·ℓ +2 ·ℓ) ≈ O(2 ·ℓ) 个量子比特.
1
3 3 分支 Type-I 型 GFS 的 11 轮 (量子) DS-MITM 攻击及其复杂度分析
本节首先简要介绍 3 分支 Type-I 型 GFS 的结构特征, 其次, 利用文献 [13] 构造的 3 分支 Type-I 型 GFS 的 9
轮中间相遇区分器对该结构实施 11 轮 DS-MITM 攻击和量子 DS-MITM 攻击, 并进行复杂度分析.
ℓ
设该结构的分组长度为 3ℓ 比特, 每个分支的输入长度为 比特, 如图 4(a) 所示. 设第 i 轮的轮函数为 F i : F ℓ
2
ℓ ℓ ℓ×3
i
→ F , 轮密钥为 k i ∈ F , 第 轮的输入为 X i = (X i,1 ,X i,2 ,X i,3 ) ∈ F , i ∈ N, 则有:
2 2 2

(X i+1,1 ,X i+1,2 ,X i+1,3 ) = (X i,2 ⊕ F i (k i ⊕ X i,1 ),X i,3 ,X i,1 ).

X X X
0,1 0,2 0,3
Δx 0 k Δ x' 0
0 F
i X ,1 X i ,2 i X ,3 0 t
i k 0 X 0 X Δx X
i F 1,1 1,2 1,3
9 轮中间相遇区分器
Δz X 10,1 k 10 0 X 10,2 0 X 10,3
F
10 t 10
i X + 1,1 i X + 1,2 i X + 1,3
Δz' 0 Δ z
X 11,1 X 11,2 X 11,3
(a) 第 i 轮结构 (b) 11 轮 DS-MITM 攻击
图 4 3 分支 Type-I 型 GFS 第 i 轮结构和 11 轮 DS-MITM 攻击

O
I O I ∆F .
另外, 记 F i 的输入输出分别为 F 和 F , 相应的输入输出差分分别记为 ∆F 和
i i i i
接下来, 我们利用文献 [13] 构造的 9 轮中间相遇区分器对 11 轮 3 分支 Type-I 型 GFS 进行 DS-MITM 攻击及
复杂度分析.
预计算阶段: 将文献 [13] 构造区分器阶段 (0 ℓ ,0 ℓ ,∆x) → (∆z,0 ℓ ,0 ℓ ) 得到的 ∆-序列 Γ 3 的 2 种可能值存储在表 T 5 中.
ℓ