“把 $R$ 变成欧氏格;理论常在该空间取球形或椭圆形 格上离散 Gaussian,再拉回并约化。处理复嵌入时通常以 $\sqrt2$ 缩放实、虚坐标,使欧氏内积与迹形式相容。原始归约还常使用…”
形式陈述 ​
继续采用
对格
若希望以中心
两种记法可经平移转换,但中心符号的位置不同;把
与具有相同指数核的连续各向同性 Gaussian
这个等式只对齐连续密度的指数参数,不表示离散样本的坐标标准差恰为
直觉
连续 Gaussian 给空间中每一点一个随距离平滑衰减的权重;离散 Gaussian 只保留格点,再除以所有保留权重之和。
当
在正交直积格上,坐标权重可以分解;一般斜格上,格基坐标中的独立一维采样对应的是另一种椭圆几何。安全证明要求球形 canonical Gaussian 时,不能用“每个系数独立同分布”作为无条件替代。
例子与边界
对
归一化常数
所以
同一数值也能检验“sigma 直接填成
若取陪集
无限支撑不等于能用有限精度直接枚举。实际采样器要证明输出与理想分布的统计距离、截尾失败概率及侧信道性质;使用浮点 exp 后再归一化的玩具实现不能自动继承理想定理。
推论与应用
离散 Gaussian 的尾界让格向量以高概率保持短,同时其 Fourier 自对偶结构使模格统计可分析。这种“短而不集中于单一可预测点”的组合支撑陷门原像采样、GPV 签名、LWE 误差生成及最坏情形归约。
在 Ring-LWE 中,误差常先在数域 canonical embedding 的欧氏格上定义,再映回商环表示;在 Module-LWE 中则扩展到若干嵌入坐标。若实现改用系数嵌入、舍入 Gaussian 或二项分布,就需要新的参数换算与安全论证,不能只沿用
参考资料
- 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。