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

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

 c−1
 ∑
  
 1,

[±N]  ∃i c ∈ [±N]\ν : l i j = −l i c + t
  
  .
f t :   → {0,1}, ν 7→ 
   j=1
c−1 

0, else


 
[±N]
 
  i 1 ,i 2 ,...,i c−1 , 进而得到 c-求和问
Grover 量子搜索算法能在定义域    中搜索使 f t (i 1 ,i 2 ,...,i c−1 ) = 1 的系数

 
c−1
题的一个单解. 基于 Grover 量子搜索算法构造的量子 c-求和步骤如算法 3 所示.
算法 3. 量子 c-求和算法.
输入: L = (l 1 ,..., l N );
输出: 集合 S 或⊥.
1. 初始化 QRAM 存储 O W
2. 对 L 中每个 l j , 加入 O W 第 j 位
ˆ
3. 定义预言 O(i 1 ,i 2 ,...,i c−1 ):
4. 从 O W 中取出 l i 1 , l i 2 ,..., l i c−1
c−1
∑
5. IF 存在 l c 使得 l i j = −l i c + t
j=1
6. 输出 1
7. 以下步骤重复 O(N) 次:
ˆ
8. Grover 搜索找到 i 1 ,...,i c−1 , 使 O(i 1 ,...,i c−1 ) = 1
c−1
∑
9. 根据 (i 1 ,i 2 ,...,i c−1 ) 恢复 i c 满足 l i j = −l i c + t
j=1
10. S ← S ∪{{i 1 ,...,i c }}
11. IF |S | = N
12. 输出 S
13. 输出⊥
由于 BKW 中 c-求和的目标向量为零向量, 故系数 (i 1 ,i 2 ,...,i c ) 与 (−i 1 ,−i 2 ,...,−i c ) 不应重复出现. 所以, 函数
  


 1
[±N]  N 
       c−2 c−1 c−2
f t (i 1 ,i 2 ,...,i c−1 ) 的定义域大小可折半为 |D| =    · =     2 ⩽ N 2 . Grover 量子搜索算法找到单解的复杂




c−1 2 c−1

√ √ c/2−1 c/2−1
2 /N) = O(N
2
−1
度可估计为 O( |D|/| f (1)|) = O( N c−1 c−2 c/2−1 c/2−1 ), 量子 c-求和算法的总时间复杂度为 O(N · N 2 )
= O(N 2 ). 相比经典 c-求和算法的时间复杂度 O((2N) ), 采用量子 Grover 搜索的 c-求和算法实现了平方级
c/2 c/2−1
c−1
加速. 基于此 c-求和算法, 给定 m BKW 个 k 维 LWE 采样, 设计量子 BKW 如算法 4 所示.
算法 4. 量子 c-求和 BKW 算法.
k(1+ϵ a )
b = , ϵ a > 0;
输入: 分块个数 a > 0, 分块长度
a
输出: LWE 秘密向量 s.
(约化阶段)
1. FOR i ← 1,2,...,m BKW
2. FOR j ← 1,2,...,a−1
b
3. L ← c-SP(L,0 )
4. IF L = ∅