格上高斯分布很早就被用来研究格的一些性质[40],近年来,研究者发现使用高斯分布能够有效的隐藏格上陷门信息,实现方案的安全性.不仅如此,近年来,研究者找到了几种实现格上高斯分布的有效方法,掌握了格上高斯分布的很多良好性质,这些积累大大促进了高斯分布作为重要工具在格密码设计领域的应用[38,41–44,28,45].方便起见,以下以Λ⊥q(A)为例,介绍格上高斯分布的基本概念和基本结论.首先给出Rm 上以σ ＞0 为参数,c ∈Rm 为中心的离散高斯分布的密度函数

格Λ⊥q(A)上的离散高斯分布的定义为

由定义可知,离散高斯分布DΛ⊥q (A),σ(x) 可以看做从参数为σ的高斯分布中抽取向量x ∈Rn,而该向量恰好为格Λ⊥q(A) 上向量（x ∈Λ⊥q(A)）的条件分布.特别的,当我们表示以0点为中心的高斯分布时,我们经常将0点省略.

我们引入格关于参数∈＞0 的光滑参数的概念[32].

定义2.12 给定一个n 维格Λ 和一个正有理数∈＞0,光滑参数η∈(Λ) 定义为满足ρ1/σ(Λ*∖{0})≤∈成立的最小的正整数σ.

对几乎所有的矩阵A ∈和几乎所有的∈总有当高斯分布的高斯参数超过光滑参数时,格上高斯分布展现了许多良好的密码特性而这些特质被广泛的应用于密码设计环节.以下我们不加证明的给出这些与高斯分布、光滑参数相关的基本结论.

引理2.4 [32]设Λ 为一个n 维格.则对任意的∈∈(0,1),s ＞η∈(Λ),向量c ∈Rn,我们有

该引理说明本质上看当参数大于光滑参数时高斯分布的基本形状不会因为格的传递而发生改变.(www.daowen.com)

以下引理为当前大部分格基签名方案的正确性验证提供了理论依据.

引理2.5 [32,38]对任意格Λ,c ∈Span(Λ),∈∈(0,1)以及s ＞η∈(Λ),

当以参数s从离散高斯分布中抽样,得到的样本以极大概率距离中心c的距离最多为这保证了我们在进行高斯抽样时,得到的结果是以极大概率满足范数方面的一定要求.这条性质成为很多格基签名验证算法的设计基础.

引理2.6 [46]对任意n 维格Λ,c ∈Rn,∈＞0 s ＞2η∈(Λ)以及任意格上向量x ∈Λ,我们有

若∈＜则格上离散高斯分布DΛ,s,c 的最小熵至少是n-1.

以上引理是PSF能够有效防止密钥信息泄露的理论保证,而且该引理被广泛的应用于基于高斯抽样设计的数字签名方案的安全证明环节.

引理2.7 设矩阵A ∈的列生成 ,并且令则对e ～DZm,s,u=Ae(modq)所服从的分布统计接近上的均匀分布.