Page 11 - 《软件学报》2025年第10期

4408 软件学报 2025 年第 36 卷第 10 期

S
S
⩽ s 2 (A) ⩽ s 1 (A), 此时 s 1 (A) 即为 A 的谱范数. 对于有限集合 , 符号 U(S ) 表示集合 上的均匀分布. 对于概率分
布 D, 使用符号 x ←- D 来表示随机变量 x 服从分布 D. 集合 上的离散概率分布 D 1 和 D 2 的统计距离 ∆(D 1 ,D 2 )
S
1 ∑ [ ]

定义为 ∆(D 1 ,D 2 ) := · Pr x←-D 1 [x = a]−Pr y←-D 2 y = a . 我们使用符号 λ 来表示安全参数, 并称一个函数 f (λ) 是
2
a∈S 1
可忽略的, 如果对任意的 c > 0, 存在 , 使得对任意的 λ ⩾ λ 0 , 不等式 f (λ) ⩽ 恒成立. 当具体的函数形式对我们
λ 0
λ c
的讨论没有影响时, 一般使用符号 negl(λ) 来表示 (某个或者某些不同的) 可忽略的函数. 如果 ∆(D 1 ,D 2 ) ⩽ negl(λ),
则称概率分布 D 1 和 D 2 是统计接近的/统计不可区分的.
2.1 格与离散高斯分布
本文仅讨论满秩的整数格. 更确切地说, 本文讨论的 d 维欧氏格 Λ := L(B) 可写成形如 Z· b 1 +...+Z· b d 的形
d
∗
式, 其中, B := (b 1 |...|b d ) ∈ Z d×d , d 为任意正整数. 格 Λ 的对偶格 Λ 的定义为 Λ := {x ∈ R :< x, y >∈ Z, ∀y ∈ Λ}. 我们
∗
b n K := Q[x]/(x +1) 及其代数
n
也关心特殊的理想/模格. 为了简化讨论, 本文固定正整数 n = 2 , 并考虑特殊的分圆域
R := Z[x]/(x +1) (值得注意的是, 采用与本文类似的分析方法, 本文的结论可以推广到一般的代数数域
n
整数环
n
中). 对于 R 中的多项式 a = a 0 +a 1 · x+...+a n−1 · x n−1 , 我们采用系数嵌入 σ coef 将其嵌入 Z , 即 σ coef (a) := (a 0 ,...,
T a = a 0 +a 1 · x+...+
a n−1 ) . 注意到 R 中两个元素的多项式乘法可以表示为矩阵乘以向量的形式. 对于给定的
a n−1 · x n−1 和 b = b 0 +b 1 · x+...+b n−1 · x n−1 , 经简单计算可知, σ coef (a·b) = M coef (a)·σ coef (b) = M coef (b)·σ coef (a). 其中,

 ... 
 a 0 −a n−1 −a n−2 −a 1 
 
 
 ... 
 a 1 a 0 −a n−1 −a 2  

 
 
 

 a 2 a 1 a 0 ... −a 3  .

M coef (a) :=   
 . . . . 
 . 
 . . . . . 
 . 
 . . . . 
 
 
 
...
a n−1 a n−2 a n−3 a 0
易知, 对于 R 的任意理想 ,
J σ coef (J ) 为一个满秩格.
对于任意给定的正实数 s ∈ R 和向量 c ∈ R , 定义以 为参数、以 为中心的 维高斯函数为 ρ s,c (x) :=
d
s
c
d
||x−c|| 2 1
d
,
e −π· s 2 . 对应地, 以 s 为参数、以 c 为中心的 d 维连续高斯分布 D s,c 对应的概率密度函数为 ·ρ s,c (x) x ∈ R . 可
s d
以将对应的高斯分布限制在任意的格 (或者离散集合) Λ 上, 对应的离散高斯分布 D Λ,s,c 的概率分布函数为
∑
/
ρ s,c (x) ρ s,c (Λ) x ∈ Λ. 这里, ρ s,c (Λ) := ρ s,c (x). 当 c = 0 或者 s = 1 时, 我们省略相关符号中对应的下标, 例如
,
x∈Λ
使用 ρ s (x) ρ(x) 等. 给定任意非奇异的矩阵 B ∈ R d×d , 矩阵 Σ := B· B 是一个实对称正定矩阵 (记为 Σ > 0). 定义
T
,
( )
−1
Σ
ρ B (x) := ρ B · x = e −π·x T ·Σ −1 ·x . 注意到 ρ B (x) 的取值仅仅与 和 x 相关, 因此我们记 ρ Σ (x) := ρ B (x). 为了简化讨
√
√ √ √ T √ √
Σ
论, 这里的 Σ 选择为 的 Cholesky 分解 (即满足条件 Σ = Σ · Σ , Σ 为下三角矩阵). 事实上, 取 Σ 为任意
T
满足条件 Σ = B· B 的矩阵 B 并不会影响后续的讨论. 对于两个实对称正定矩阵 A,B, 如果 A− B 仍为实对称正定
矩阵, 则记 A > B.
当我们在 R 中讨论时, 我们使用符号 f ←- D R,s 来表示多项式 的系数独立地取自参数为 s 的一维离散高
f
( ) d
斯分布 D Z,s . 由于 D Z,s = D Z d ,s , 因此 f ←- D R,s 等价于 的系数组成的向量服从分布 D Z n ,s , 即 σ coef ( f) ←- D Z n ,s .
f
特别地, 我们有 D R d ,s = D Z n·d ,s . 假设 ε > 0 为某正实数. 对任意的 维格 Λ, 定义格 Λ 的 (与 ε 相关的) 光滑参数
d
( )
√ −1
η ε (Λ) 为 min{s : ρ 1/s (Λ \{0}) ⩽ ε}. 类似地, 对于任意的实对称正定矩阵 Σ > 0, 如果条件 η ε Σ ·Λ ⩽ 1 成立, 则记
∗
s>0 ( ) ( )
√ √ −1 √ T
∗
Σ ⩾ η ε (Λ). 根据定义, 条件 η ε Σ ·Λ ⩽ 1 等价于 ρ Σ ·Λ \{0} = ρ √ −1(Λ \{0}) ⩽ 0. 在本文后面的讨论中, 我
∗
Σ
们需要用到如下引理 [1,8,10,33–35] .
引理 1. 以下事实成立.
( )
1 √
−2
(1) 假设 Σ 是实对称正定矩阵, Λ 为某个格, 实数 ε ∈ 0, . 如果 s 1 (Σ) ⩽ η ε (Λ) , 则有 Σ ⩾ η ε (Λ).
2
( √ )
d
( )
(2) 对于 d 维格 Z , 存在可忽略的 ε = ε(λ) 使得 η ε Z ⩽ ω logd .
d
( √ )
(3) 假设已知 d 维格 Λ = L(B) 的一组格基 , 实数 r = ω logd . 则对任意的向量 c ∈ R 和满足条件
d
B