Page 405 - 《软件学报》2025年第7期

3326 软件学报 2025 年第 36 卷第 7 期

i−1 i−1 i−1 i−1
x 0 x 1 x 2 x d −1
… …
F i

…
i i i i
x 0 x 1 x d−2 x d−1
图 6 第 i 轮类 MARS 广义 Feistel 结构

3 Grover 算法及其应用

对于从 N 个无序元素列表中搜索出一个目标元素的问题, 一般情形下, 经典算法平均需要 N/2 次查询列表.
√
而基于量子计算的并行计算特性, Grover 算法仅需要 N 次查询, 相比于经典搜索进行了二次加速. Grover 算法
具体过程如算法 1 所示. 此外, Brassard 等人 [33] 又在 Grover 算法的基础上拓展出幅度放大算法, 并且针对密码分
析中常见的碰撞问题, 提出了 BHT 碰撞搜索算法 [34] .
算法 1. Grover 算法 [12] .

输入: 量子 Oracle O f 可执行变换 O f |x⟩|q⟩ = |x⟩|q⊕ f(x)⟩, 其中, 布尔函数 f(x) = 1 仅当 x = x 0 0 ⩽ x ⩽ 2 −1 n+1
n
,
;
个量子比特;
输出: x 0 .
⊗n
1. 制备初始态 |φ 1 ⟩ = |0⟩ |0⟩.
2 n −1 [ ]
1 ∑ |0⟩−|1⟩
⊗n
2. 在前 n 个量子比特上执行 H , 以及在最后一个量子比特上执行 HX, 得到态 |φ 2 ⟩ = √ |x⟩ √ .
2 n x=0 2
2 n −1
⌈ √ ⌉ [ ] R 1 ∑
R ≈ π 2 /4 次 [ ]
n
3. 执行 Grover 迭代算子 G = (2|φ 2 ⟩⟨φ 2 |− I)O f 得到态 |φ 3 ⟩ = (2|φ 2 ⟩⟨φ 2 |− I)O f √ |x⟩
2 n
[ ] [ ] x=0
|0⟩−|1⟩ |0⟩−|1⟩
√ ≈ |x 0 ⟩ √ .
2 2
4. 测量前 n 个量子比特, 得到 .
x 0
在量子密码分析中, 通常利用 Grover 算法直接穷举搜索正确密钥, 因此复杂度由密钥空间大小决定, 但是该
方法的复杂度不一定低于利用经典分析方法 (不利用量子计算机) 来恢复密钥. 但是, 利用 Grover 算法直接穷举搜
索正确密钥的方法仅需要几个已知明文与其对应的密文, 这也是该方法相比于其他量子密码分析方法的另一优
势, 只需要经典查询且数据复杂度仅为常数项级别. 为了发挥这一优势, Daiza 等人 [19] 针对 3 轮 Feistel-KF 结构 (或
称为 Feistel-2 结构) 提出了新的量子密钥恢复攻击, 而不需要量子查询. 其基本思想是根据 3 轮 Feistel-KF 结构的
一些特性, 利用 Grover 算法搜索出所需的中间状态值, 并根据这些中间状态值搜索出正确轮密钥. 相比于其他量
n/4
子攻击, 该攻击仅需要经典查询且数据复杂度为 O(1). 尽管需要 O(2 ) 时间 n ( 为分组长度), 但依然优于经典分析
n/2
的 O(2 ).

4 对 Lai-Massey 结构的密钥恢复攻击
受 Daiza 等人 [19] 工作的启发, 本文将分析 3 轮 Lai-Massey 结构, 并利用 Grover 算法辅助进行搜索计算, 提出
新型量子密钥恢复攻击.
如图 7 所示的 3 轮 Lai-Massey 结构, 其中 F 1 、 F 2 和 F 3 为轮函数, σ(x L , x R ) = (x R , x L ⊕ x R ) x L 和 x R 分别表示 x i
(
1
n
0
a
的左半部分和右半部分比特). 设 [a,b] ∈ {0,1} , 其中, 、 b 分别表示高位 n/2 比特和低位 n/2 比特. 设 [x , x ],
i i
[y ,y ] ∈ {0,1} i = 0,1,2,3 [x , x ] [y ,y ] 为 3 轮 Lai-Massey 结构的输入, [x , x ] [y ,y ] 作为输出.
0
1
,
1
0
0
0
1
.
1
n
,
,
0
1

0
3
i
3
3
3
0
0
0
i