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

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

ℓ ℓ ′
{(a,m,0),(a,m,1),...,(a,m,2 −1)}, {(a,m⊕∆x,0),(a,m⊕∆x,1),...,(a,m⊕∆x,2 −1)}, 相应的明文差分 ∆P=(0 ℓ ,∆x,∆x )
ℓ×3 2ℓ
∈ F , 将这 2 个明文对存储在列表 T P 中.
2
ℓ (a,m,u 1 ) 和 (a,m⊕∆x,u 2 ) 分别进行 2ℓ 个差分为
(1.2) 对任意 u 1 , u 2 ∈ F , 将差分为 ∆P 的明文对 6 轮加密得到 2
2
∆C = (∆z,∆z ,0 ℓ ) ∈ F ℓ×3 的密文对, 并将其存储在列表 T C 中. 对于给定的 ∆x, ∆z, 由于明密文差分 ∆P 和 ∆C 均以概
′
2
率 p 1 = p 2 = 2 −ℓ 分别传播到区分器的输入差分 (∆x,0 ℓ ,0 ℓ ) 和输出差分 (0 ℓ ,∆z,0 ℓ ), 则 6 轮截断差分传播概率为
−2ℓ
2ℓ
p = p 1 p 2 = 2 −2ℓ . 因此, 至少有 2 ×2 = 1 个明密文对 (P 0 ,P) ∈ F 3ℓ×2 和 (C 0 ,C) ∈ F 3ℓ×2 满足图 2(b) 所示的 6 轮差分特
2 2
′
′
征 (0 ℓ ,∆x,∆x ) → (∆z,∆z ,0 ℓ ).
(1.3) 根据步骤 (1.2) 得到的明文对 (P 0 ,P), 利用 P 0 = (X ,X ,X ) 构造 b-δ-集 G = {P r = X ,X ⊕r,X ⊕∆F )|r
0
O
0
0
0
0
0

0,1 0,2 0,3 0,1 0,2 0,3 0,2
b
ℓ
b
∈ {0,1,...,2 −1}, ∆F O ∈ F }, 利用 G 构造明文对 (P 0 ,P r ), r ∈ [2 −1], 并依次进行 6 轮加密得到对应的密文对 (C 0 ,C r ),
0,2 2
b
′
′
因此得到 2 −1 个明密文对满足图 2(b) 所示的 6 轮差分特征 (0 ℓ ,∆x,∆x ) → (∆z,∆z ,0 ℓ ).
2) 密钥恢复. 包括如下 4 个步骤.
(2.1) 选取步骤 (1.3) 中的一个明文对 (P 0 ,P r ), 对应差分 P 0 ⊕ P r = (0 ℓ ,∆x,∆x ), 根据性质 1, 利用 F 0,2 (t 0,2 )⊕ F 0,2 (t 0,2 ⊕
′
r
′ b b ′
∆x) = ∆x 确定 t 0,2 的唯一值. 当 取遍 [2 −1] 时, 将得到 t 0,2 的 2 −1 个可能值存储在以 (0 ℓ ,∆x,∆x ) 为索引的表 T 2
b
0 2 −1 个可能值.
中, 再由 k 0,2 = t 0,2 ⊕(X ⊕r) 确定子密钥 k 0,2 的
0,2
b r r r ′
,
(2.2) 对每个 r ∈ [2 −1], 依次选取密文对 (C 0 ,C r ) C r = (X ,X ,X ), 显然 C 0 ⊕C r = (∆z,∆z ,0 ℓ ). 猜测子密钥 k 5,1
6,1 6,2 6,3
的值, 根据性质 1 和 X ⊕ F(X ⊕k 5,1 ) = X r 确定 X r 的唯一值. 当 r 取遍 [2 −1] 时, 将得到 X r 的 2 −1 个可能值.
r
b
b
r
6,1 6,3 5,2 5,2 5,2
′ b ′ T 3 中,
类似地, 利用 F 5,2 (t 5,2 )⊕ F 5,2 (t 5,2 ⊕∆z) = ∆z 确定 t 5,2 的 2 −1 个可能值, 并将其存储在以 (∆z,∆z ,0 ℓ ) 为索引的表
b
再由 k 5,2 = t 5,2 ⊕ X r 确定子密钥 k 5,2 的 2 −1 个可能值.
5,2
(2.3) 根据 k 5,1 和 k 5,2 的猜测值, 对步骤 (1.3) 得到的密文集 {C 0 ,C 1 ,...,C 2 b −1 } 分别进行部分解密, 得到区分器输
r r r r ℓ×3 b 0
出处的可能值 X = (X ,X ,X ) ∈ F , r ∈ {0,1,...,2 −1}, 从而得到 ∆-序列 Γ 2 = (∆ 1 ,∆ 2 ,···,∆ 2 b −1 ), 其中, ∆ r = X ⊕

5 5,1 5,2 5,3 2 5,3
b
r
X , r ∈ [2 −1].
5,3
(2.4) 将步骤 (1.3) 中的 2 −1 个明密文对 (P 0 ,P r ) 和 (C 0 ,C r ), 步骤 (2.1)–(2.3) 中的 2 −1 组子密钥 (k 0,2 ,k 5,1 ,k 5,2 )
b
b
以及相应的 ∆-序列 Γ 2 = (∆ 1 ,∆ 2 ,...,∆ 2 b −1 ) 存储在以 ∆ r 为索引的表 T 4 中. 当 b ⩾ 3 时, 检查表 T 1 和 T 4 中的 ∆-序列 是
(k 0,2 ,k 5,1 ,k 5,2 ) 为正确密钥; 否则, 匹配不成功, 另外选取一对明文重复上述步骤
否匹配, 若匹配, 则猜测的子密钥
(2.1)–(2.4).
下面给出攻击的复杂度分析.
ℓ ℓ ℓ ℓ
(1) 由于在线阶段构造了两个大小分别为 2 的明文集, 故该攻击的数据复杂度为 O(2 +2 ) ≈ O(2 ) 个选择明文.
2ℓ
(2) 由于预计算阶段构造表 T 1 所需的时间复杂度为 O(2 ) 次 6 轮加密, 在线阶段猜测子密钥所需的时间复杂
3ℓ
3ℓ
O(2 ) 次 6 O(2 ) 次 6 轮加密.
度为 轮加密, 因此, 攻击所需的时间复杂度为
ℓ
b T 4 所需的存
(3) 由于存储的是 ∆-序列, 而 ∆-序列 中有 2 −1 个 , 且每个 ∆ i 的长度为 比特, 故存储表 T 1 和
∆ i
2ℓ 2ℓ 2ℓ b
储复杂度为 O(2 +2 ) ≈ O(2 ) 个长度为 (2 −1)ℓ 的比特块.
2.3 3 分支 Type-III 型 GFS 的 6 轮量子 DS-MITM 攻击及复杂度分析
本节首先基于命题 1 构造的 4 轮中间相遇区分器, 分别向前向后扩展 1 轮, 实现 3 分支 Type-III 型 GFS 的 6
轮量子 DS-MITM 攻击; 其次, 对攻击的复杂度进行分析.
攻击过程包括预计算阶段和在线阶段.
2ℓ
ℓ
O(2 ) 次 6 O(2 ) 次量子查
1) 预计算阶段. 通过量子并行叠加, 将经典环境下的时间复杂度从 轮加密降低到
询, 具体步骤如下.
(1.1) 根据区分器第 1 ∆x 制备量子叠加态:
分支差分
2 ℓ −1 2 ℓ −1
∑ 1 ∑ 1
|φ 1 ⟩ = √ |∆z⟩ √ |∆y⟩|∆x⟩.
2 ℓ 2 ℓ
∆z=0 ∆y=0
(1.2) 依据公式 (1) 利用 |φ 1 ⟩ 得到图 , , t 3,2 , 即:
Grover 算法搜索 3(a) 中的状态 t 1,1 t 2,1 t 3,1 和