“Gaussian版本也解释格平滑参数中为什么出现对偶频率的质量:零频率给平均背景,其他频率给位置变化。本页严格证明的是一维周期化接口;一般秩格还需要相应维数、余体积和对偶坐标,不能把一维因子…”
形式陈述
本页固定 Gaussian 质量函数
对正秩
由于
尺度变换满足
因为
直觉
把连续 Gaussian 按格平移后叠加,会留下由对偶格频率描述的周期波纹。Poisson 求和表明,频率
最短对偶向量主导最慢衰减,但定义要对所有非零对偶点求和。只检查
一维Poisson求和接口给这项机制的直接证明与有限尾证书:先构造连续周期化,再计算其Fourier系数,用Fejér唯一性收尾。Gaussian平移的首个修正可以为负,因此相位不能先行丢弃;做上界时才对全部非零频率取绝对值。一般秩格的余体积与对偶坐标仍按本页公式保留,不能只照搬一维步长因子。
“平滑”不是说离散格变成连续集合,也不是采样器的数值舍入精度。它是一条分布界的阈值:超过它后,平移后的 Gaussian 质量、模格统计和某些卷积具有可控的近均匀性。
例子与边界
对
取
这个夹逼可逐项复算,也显示忽略负频率会把质量少算一半。
若缩放到
推论与应用
对
因而在
这也把
故任意垂直平移并不保持这条近常数界。这些性质是格上离散 Gaussian卷积、拒绝采样与原像采样分析的共同接口。
平滑参数还连接原格和对偶格的几何尺度。密码归约常用可计算的上界替代精确
参考资料
- Daniele Micciancio and Oded Regev, “Worst-Case to Average-Case Reductions Based on Gaussian Measures,” SIAM Journal on Computing 37(1), 2007, Sec. 2。
- Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan, “Trapdoors for Hard Lattices and New Cryptographic Constructions,” STOC, 2008, Sec. 2。
- Chris Peikert, “An Efficient and Parallel Gaussian Sampler for Lattices,” CRYPTO, 2010。