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

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

1.3 量子基础知识
量子 DS-MITM 攻击的主要思想是使用量子爪搜索算法寻找 DS-MITM 攻击中预计算阶段和在线阶段所获

得的 ∆-序列 之间的碰撞, 并通过 Grover 算法实现对经典搜索效率的二次加速.
n n f(x 0 ) = 1, 目标是找到满足条件
考虑搜索问题: 给定布尔函数 f : F → F 2 , n ⩾ 1, 如果存在唯一的 x 0 ∈ F 满足
2
2
N = 2 的无序数据库中, Grover 算法将搜索目标条目的时间复杂度从经典
n
的 x 0 (下称目标条目). 在总条目数量为
n/ 2
n O(2 ), 实现了平方加速, 算法详见文献
算法的 O(2 ) 降至 [15].
定义 2. 给定两个函数 f : X → Z, g : Y → Z , 其中 X = [s], Y = [t], s,t ∈ N . 如果存在一对 (x 0 ,y 0 ) ∈ X×Y , 使得
+
f(x 0 ) = g(y 0 ), 则称 (x 0 ,y 0 ) 为函数 f 和 g 的爪.
2001 年, Buhrman 等人 [17] 首次提出量子环境下的爪搜索算法, 由于该算法在量子 DS-MITM 攻击的在线阶段
起到了重要作用, 故在本节详细介绍, 见算法 1.
算法 1. 量子爪搜索算法.
输入: f : X → Z, g : Y → Z;

输出: 爪 (a 0 ,b 0 ).
{ ⌊ √ ⌋}
2
(1) 分别随机选取大小为 l 和 l 的子集 A ⊆ [s] 和 B ⊆ [t], 其中 l ⩽ min s, t , ⌊⌋ 为向下取整函数.
(2) 根据 f 值的大小对条目 ( f(a i ), a i ) 进行排序, 并将其存储在列表 L 中, 其中, a i ∈ A, 1 ⩽ i ⩽ l.
(3) 构造量子预言机 U h : |b⟩|1⟩ → |b⟩|h(b)⊕1⟩, 进行测量判断是否存在一对 (a,b) 满足 f(a) = g(b), 其中,
{
1, 存在 a ∈ A,b ∈ B 使得 f(a) = g(b)
h(b) =
0, 否则
(4) 若 (3) 的测量结果为 |b⟩|0⟩, 则进行下一步, 并记 b 0 = b, 否则, 重复步骤 (1)–(3), 直至测量结果为 |b⟩|0⟩.
(5) 使用经典二分法搜索列表 L, 找到与步骤 (3) 对应的 a, 并记 a 0 = a, 输出爪 (a 0 ,b 0 ).
√
算法 1 步骤 (2) 需要 O(l·logl) 次经典排序, 步骤 (3)–(5) 共需要 O( |B|·log|A|) = O(l·logl) 次量子搜索, 而步
骤 (1) 所需要的时间复杂度相较于步骤 (2)–(5) 可以忽略, 故运行步骤 (1)–(5) 所需要的时间复杂度为 O(l·logl) 次
量子查询. 由于运行一次步骤 (1)–(5) 获得爪 (a 0 ,b 0 ) ∈ A×B 的成功概率为 p = l 2st, 故运行算法 1 需要的时间复杂
/
3
√
√ /
3
度为 O( st l ·llogl) = O( st/l·logl) 次量子查询, 存储复杂度为 O(l·logl) 个量子比特.
此外, 量子 DS-MITM 攻击使用了量子随机存储器 (quantum random access memory, qRAM), 它是经典随机存
储器 (RAM) 在量子环境下的对应产物. 对于给定的存储在量子计算机的数据列表 D = {x i |i ∈ [2 ], x i ∈ F , k ∈ N }
k
n
+
2
n
和常值 y ∈ F , 使用 qRAM 访问 D 的过程定义为酉变换 U qRAM :

2
∑ ∑
U qRAM (D) : a i |i⟩|D⟩|y⟩ → a i |i⟩|D⟩|y⊕ x i ⟩,
i i
∑
其中, a i |i⟩ 是查询地址的叠加, |D⟩|y⊕ x i ⟩ 是第 i 个存储单元的内容.
i
2 3 分支 Type-III 型 GFS 的 6 轮 (量子) DS-MITM 攻击
本节首先简要说明 3 分支 Type-III 型 GFS 的结构特征, 其次, 构造该结构的 4 轮中间相遇区分器, 最后, 基于
该区分器分别向前向后扩展 1 轮, 实现 6 轮 (量子) DS-MITM 攻击, 并给出该攻击的复杂度分析.
ℓ
设该结构的分组长度为 3ℓ 比特, 每个分支的输入长度为 比特, 如图 2(a) 所示. 设第 i 轮的两个轮函数分别为
ℓ ℓ ℓ ℓ ℓ ℓ 3ℓ
F i,1 : F → F 和 F i,2 : F → F , 两个轮密钥分别为 k i,1 ∈ F 和 k i,2 ∈ F , 第 i 轮的输入为 X i = (X i,1 ,X i,2 ,X i,3 ) ∈ F , 其中, X i,j
2
2
2
2
2
2
2
表示第 i 轮第 j 个分支的输入, i ∈ N 且 1 ⩽ j ⩽ 3, 则有:

(X i+1,1 ,X i+1,2 ,X i+1,3 ) = (X i,2 ⊕ F i,1 (k i,1 ⊕ X i,1 ),X i,3 ⊕ F i,2 (k i,2 ⊕ X i,2 ),X i,1 ).
O
O
另外, 记 F i,j 的输入输出分别为 F I i,j 和 F , 相应的输入输出差分分别记为 ∆F I i,j 和 ∆F .
i,j
i,j