Skip to content

格平滑参数

Lattice smoothing parameter · Smoothing parameter · 格的平滑参数

使全部非零对偶频率的 Gaussian 质量降到给定误差预算以下的最小尺度。

条目类型
定义

形式陈述

本页固定 Gaussian 质量函数

ρs(x)=exp(πx22s2),ρs(A)=xAρs(x).

对秩 kΛε>0平滑参数定义为

ηε(Λ)=inf{s>0:ρ1/s(Λ{0})ε}.

由于

ρ1/s(w)=eπs2w2,

s 增大时非零对偶格质量单调下降。对固定正误差预算,离散性保证定义有限且为正。这个约定让 s 具有长度量纲;有些资料把指数写成 x2/(2σ2) 或交换 s1/s,引用数值界时必须先对齐 convention。

尺度变换满足

ηε(cΛ)=|c|ηε(Λ)(c0),

因为 (cΛ)=c1Λ。误差预算越小,要求压低的对偶总质量越严格,ηε 越大;方向写反通常意味着把 ρ1/s 的参数误读了。

直觉

把连续 Gaussian 按格平移后叠加,会留下由对偶格频率描述的周期波纹。Poisson 求和表明,频率 wΛ 的振幅按 eπs2w2 衰减。平滑参数选择一个宽度,使除零频率外的总振幅至多为 ε;此后模格分布接近均匀,基本区域中的具体位置几乎不再影响总 Gaussian 质量。

最短对偶向量主导最慢衰减,但定义要对所有非零对偶点求和。只检查 λ1(Λ) 能给上界或下界的线索,不能一般地把无穷尾项删除。高维中短壳层可能包含很多点,总质量由长度和计数共同决定。

“平滑”不是说离散格变成连续集合,也不是采样器的数值舍入精度。它是一条分布界的阈值:超过它后,平移后的 Gaussian 质量、模格统计和某些卷积具有可控的近均匀性。

例子与边界

Λ=Z,对偶仍是 Z,于是

ρ1/s(Z{0})=2m=1eπs2m2.

ε=0.1。在 s=1 时,首项为 2eπ0.08643,其余从 2e4π0.00000697 起,总和小于 0.1;故 η0.1(Z)<1。在 s=0.9 时,仅 m=1 两项约为 2e0.81π0.157,已经超过预算,所以

0.9<η0.1(Z)<1.

这个夹逼可逐项复算,也显示忽略负频率会把质量少算一半。

若缩放到 3Z,对偶为 13Z,同一预算下平滑宽度恰扩大三倍。若误以为原格越稀就该用更窄 Gaussian,会与尺度公式矛盾:稀疏原格对应更密的短对偶频率,需要更大的 s 才能压低它们。

ε 不是失败概率的自动同义词。定理可能把统计距离界成 cεε/2 或其他函数,取决于采用的距离归一化与引理;应用时必须引用完整结论,而非只检查 sηε

推论与应用

s 达到适当的 ηε(Λ) 阈值后,函数 ρs(Λ+c) 对平移 c 的依赖很小,连续 Gaussian 模 Λ 接近均匀。这些性质是格上离散 Gaussian卷积、拒绝采样与原像采样分析的共同接口。

平滑参数还连接原格和对偶格的几何尺度。密码归约常用可计算的上界替代精确 ηε,例如以对偶逐次极小或 Gram–Schmidt 长度控制采样宽度;这些是充分条件,不能反过来宣称低于该上界就一定不安全或无法采样。

参考资料
  • 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。
关系图谱4 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

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