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

416 软件学报 2026 年第 37 卷第 1 期

在此预言机基础上, 文献分析了部分 NTRU 参数下密钥恢复的复杂度, 如表 6 所示.

表 6 部分 NTRU 参数集的量子复杂度

参数集 N df 2 df 1 df 3 k 量子复杂度 L列表大小
136 107.3
EES593EP1 593 10 10 8 192 2 2
132 107.1
EES587EP1 587 10 10 8 192 2 2
103 75.9
EES401EP2 401 8 8 6 112 2 2
111 65.9
EES439EP1 439 9 8 5 128 2 2
EES743EP1 743 11 11 15 256 2 196 2 195.2

6.2 基于 Claw-Finding 量子碰撞的 NTRU 量子密钥恢复
基于 Grover 量子搜索的 NTRU 量子密钥恢复需要使用判断矩阵乘积匹配的预言机, 且假定其容易通过量子
实现, 但这种预言机在实际的量子算法设计中较为复杂. 此外, 基于 Grover 量子搜索的 NTRU 量子密钥恢复需要
预先计算大量的 ( f 3 ,(−f 3 · H mod q) mod p) 值并储存在列表中, 这进一步增加了实现难度. 为避免以上问题, 需要考
虑新的 NTRU 量子攻击算法. 除了使用 Grover 量子搜索算法, 还存在使用 Claw-Finding 量子碰撞算法 [17] 的 NTRU
量子密钥恢复.
Claw-Finding 量子碰撞算法的思路类似中间相遇攻击. 给定有限集合上的两个函数 f : X → Z 和 g : Y → Z,
Claw-Finding 量子碰撞算法可以找到一对 (x,y) 称为 claw, 使得 f(x) = g(y). 要将该算法应用于 NTRU 量子密钥恢
(−f 3 · H mod q) mod p 定义为两个函数, 之后用 Claw-Finding 量子碰撞算法求
复中, 可将 (( f 1 f 2 )· H mod q) mod p 与
出满足两个函数相等的 ( f 1 f 2 ) 和 , 进而得到私钥 f.
f 3
为了构造 Claw-Finding 量子算法, Tani 等人 [17] 依靠 Johnson 图来描述 Claw-Finding 问题. 一个 Johnson 图 J(n,k)
{1,2,...,n} 的大小为 k 的子集表示. 当且仅当两个点对应的子集仅有一个元
是一个连通正则图, 图上每个顶点都用
素不同时, 两点之间有边. 如图 12 给出了点集合 (a,b,c,d,e) 组成的 Johnson 图 J(5,3) 示例. 为了将 NTRU 的密钥
恢复攻击转化为 Claw-Finding 问题, 首先定义两个 Johnson 图 J 1 (| f 1 f 2 |,l), J 2 (|− f 3 |,m). 由此两个图定义图类积
.
′
′
G = J 1 ×J 2 , 将 J 1 , J 2 上的点分别表示为 F, G, 则 G 上点为 (F,G) G 上两个点 (F,G) 和 (F ,G ) 之间有边当且仅当
′
′ G, G 之间分别有边.
F, F 和

abc
cde abd
bde abe

bce acd

bcd ace
ade
图 12 Johnson 图 J(5, 3) 示例

实现 Claw-Finding 量子碰撞算法的基本思路是在 (f, g) 的定义域中选取一定数量的输入值构造 Johnson 图上
的点, 进而按照定义生成图类积 G, 如果当前的点中含有一对输入可构成碰撞, 则该点为目标点. 为了利用量子漫
步找到目标点, 需要利用自循环将原始的 Johnson 图由无向图变为部分有向图, 令目标点只会漫步到自身, 否则依
据转移概率继续进行散射. 通过此方法构造的 Claw-Finding 量子碰撞算法分为检测算法和搜索算法两部分, 其中
检测算法是搜索算法的子过程. Claw-Finding 量子碰撞算法使用的预言机仅需读取 ( f 1 f 2 · H) 和 (−f 3 · H) 的函数值,
且不需要存储大规模列表, 相比基于 Grover 搜索的 NTRU 量子密钥中的预言机更为简单. 令 Q 2 (claw finding (M 1 , M 2 ))