Page 418 - 《软件学报》2026年第1期

曹金政 等: 格上困难问题量子求解算法综述 415

密钥结构, 研究者构造了对应的量子密钥恢复攻击, 包括基于 Grover 量子搜索的 NTRU 量子密钥恢复和基于
Claw-Finding 量子碰撞的量子密钥恢复, 如图 11 所示.

NTRU 量子密钥恢复

基于 Grover 基于 Claw-Finding

Fluhrer 等人 , 2015 董经等人 , 2021
[45]
[47]
针对 NTRU 的量子密钥恢复攻击 基于漫步 Claw-Finding 的密钥恢复攻击

Laaji 等人 , 2019
[46]
量子密钥、明文恢复攻击
图 11 NTRU 量子攻击发展概况

6.1 基于 Grover 搜索的 NTRU 量子密钥恢复
Fluhrer 等人 [45] 基于 Grover 量子搜索提出了对 NTRU 的量子密钥恢复, 该方法之后由 Laaji 等人 [46] 扩展为针
对密钥或明文的恢复攻击. 本节总结基于 Grover 搜索的 NTRU 量子密钥恢复原理. 首先将 NTRU 的公钥生成过
程用向量乘积表示, 根据公钥 h(x) = h 0 +h 1 x+...+h N−1 x N−1 的系数定义矩阵.

 
 h 0 h 1 ... h N−1 
 
 
 
 
 
 ... 
 h N h 0 h N−2 
 
   .

H =   . . . . 
 .
 . . . . . . .   

 
 
 
 
 
h 2 h 1 ... h 0
f · H = pg mod q. 模 p ( f · H = 0 mod q) mod p. 在乘积多项式模式
将 ( f,g) 用系数向量表示, 则得到等式 可得
下, 等式可表示为 (( f 1 f 2 )· H = −f 3 · H mod q) mod p.
基于 Grover 量子搜索算法的 NTRU 量子密钥恢复分两步. 首先, 将所有可能的二元组 ( f 3 ,(−f 3 · H mod q) mod p)
存储在列表 L. 随后, 搜索 f 1 f 2 , 使得对应的 (( f 1 f 2 )· H mod q) mod p 存在于列表 L, 即可找到一个满足 (( f 1 f 2 )· H =
− f 3 · H mod q) mod p 的碰撞. 该过程的搜索空间大小为 | f 1 f 2 |. 根据 NTRU 的循环移位特性, 搜索空间可还继续降
N m m m −m
至 | f 1 f 2 |/N: 多项式环 F[x]/(x −1) 中的任意两个多项式 f 1 , f 2 存在关系 (x f 1 ) f 2 = (x ) f 1 f 2 . 更进一步, (x f 1 )(x f 2 ) =
f 1 f 2 , 故 NTRU 密码方案中有 x −m f · H = px g mod q. 该结果表示环 F[x]/(x −1) 中多项式乘 x m 表示多项式向右
N
−m
或向左循环移动 m 位, 循环移动前后的多项式的系数只有位置发生了变化, 而数值保持不变. 因此, 对于公钥 h,
−m
−m
x −m f, x g 也是一组可用的私钥, 对密文进行解密之后, 仅需再次循环位移即可得到明文信息, 且私钥对 (x −m f, x g)
m
m
的恢复方法与 ( f,g) 的恢复方法相同. 在乘积多项式模式下, 同样有 ((x f 1 f 2 )· H = −x f 3 · H mod q) mod p, 即只要
′
′
′

有满足 (( f 1 f 2 )· H = − f 3 · H mod q) mod p 的多项式 f 、 f 、 f 就可以构造 NTRU 的私钥或其循环移位多项式. 综
1 2 3
√
上所述, 基于 Grover 量子搜索的 NTRU 量子密钥搜索的查询复杂度为 O( | f 1 f 2 |/N).
ˆ
文献 [45] 要求使用复杂度 O(1) 的预言机 O 来判定列表 L 中是否存在 (−f 3 · H mod q) mod p 与特定的 (( f 1 f 2 )· H
mod q) mod p 值相等, 从而恢复私钥 f. 对存储于 L ( f 3 ,(−f 3 · H mod q) mod p), 预言定义如下:
中的

 1, ( f 1 f 2 mod q) mod p在列表L中有对应值
ˆ  .

O(f 1 f 2 ) = 
0, 其他

