Skip to content

格上离散 Gaussian 分布

Discrete Gaussian over a lattice · Lattice Gaussian distribution · 格 Gaussian 分布

以 Gaussian 质量归一化后定义在格或格陪集上的离散概率分布。

条目类型
定义

形式陈述

继续采用

ρs(x)=eπx22/s2,ρs(A)=xAρs(x).

对格 Λ、平移 cs>0格上离散 Gaussian DΛ+c,s 是支撑在陪集 Λ+c 上的概率分布

Pr[X=x]=ρs(x)ρs(Λ+c)(xΛ+c).

若希望以中心 c 加权而支撑仍为 Λ,则写

DΛ,s,c(x)=eπxc2/s2yΛeπyc2/s2.

两种记法可经平移转换,但中心符号的位置不同;把 DΛ+c,s 的权重误写成 ρs(xc) 会把“平移支撑”和“移动中心”混成不同分布。

与具有相同指数核的连续各向同性 Gaussian N(0,σ2I) 比较,其密度指数为 x2/(2σ2),参数换算为

s=2πσ.

这个等式只对齐连续密度的指数参数,不表示离散样本的坐标标准差恰为 σDΛ,s,c 的实际矩依赖格、中心和 s;只有在相应平滑或连续近似条件下才能把二者近似比较。2π 因子以及离散化造成的矩偏差,都必须在尾界、噪声率和实现标准差之间显式处理。

直觉

连续 Gaussian 给空间中每一点一个随距离平滑衰减的权重;离散 Gaussian 只保留格点,再除以所有保留权重之和。s 小时质量集中在离中心最近的少数格点,s 大时跨越更多格壳层,但支撑始终可数,并不会变成连续分布。

s 高于适当的平滑参数时,移动中心或观察模某个子格的分布更规律:对偶格的非零 Fourier 频率已被压低。平滑阈值服务于近均匀性和卷积论证,并不表示低于阈值时分布没有定义;任意 s>0 都能正规化。

在正交直积格上,坐标权重可以分解;一般斜格上,格基坐标中的独立一维采样对应的是另一种椭圆几何。安全证明要求球形 canonical Gaussian 时,不能用“每个系数独立同分布”作为无条件替代。

例子与边界

Λ=Z、中心零且 s=1,未归一化权重为

ρ1(0)=1,ρ1(±1)=eπ0.043214,ρ1(±2)=e4π0.00000349.

归一化常数

ρ1(Z)=1+2eπ+2e4π+1.086435,

所以 Pr[X=0]0.9204,而每个 ±1 的概率约为 0.0398。这不是“先采样标准正态再四舍五入”:后者按单位区间积分,零点概率约为 0.383,与逐点权重正规化完全不同。

同一数值也能检验“s 不是标准差”。忽略极小的高阶尾项时,s=1 的离散样本方差约为 20.0398=0.0796,标准差约 0.282;同指数核的连续 Gaussian 标准差却是 1/2π0.399。把实现接口中的 sigma 直接填成 ss/2π,都必须先确认接口生成的是哪一种分布。

若取陪集 Z+1/2,最靠近零的 ±1/2 权重相等,因此分布至少有两个主峰;支撑中根本没有零。若改写成 DZ,1,1/2,支撑回到整数,主峰变成 01。两者由平移对应,但样本所在集合不同,协议编码时必须保持一致。

无限支撑不等于能用有限精度直接枚举。实际采样器要证明输出与理想分布的统计距离、截尾失败概率及侧信道性质;使用浮点 exp 后再归一化的玩具实现不能自动继承理想定理。

推论与应用

离散 Gaussian 的尾界让格向量以高概率保持短,同时其 Fourier 自对偶结构使模格统计可分析。这种“短而不集中于单一可预测点”的组合支撑陷门原像采样、GPV 签名、LWE 误差生成及最坏情形归约。

在 Ring-LWE 中,误差常先在数域 canonical embedding 的欧氏格上定义,再映回商环表示;在 Module-LWE 中则扩展到若干嵌入坐标。若实现改用系数嵌入、舍入 Gaussian 或二项分布,就需要新的参数换算与安全论证,不能只沿用 s 的同一个数值。

参考资料
  • Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan, “Trapdoors for Hard Lattices and New Cryptographic Constructions,” STOC, 2008, Sec. 2.3。
  • Daniele Micciancio and Oded Regev, “Worst-Case to Average-Case Reductions Based on Gaussian Measures,” SIAM Journal on Computing 37(1), 2007。
  • Chris Peikert, “An Efficient and Parallel Gaussian Sampler for Lattices,” CRYPTO, 2010。
关系图谱8 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系