首先介绍一个能够以高斯分布输出整数的抽样算法,记作SampleZ.设s 为高斯参数,c为实数,n 为安全参数,SampleZ 算法的输出分布为以实数c 为中心的高斯分布DZ,s,c.

算法.SampleZ

输入: (s,c,n).1.x ∈Z ⋂[c-st,c+st].

2.以概率ρs(x-c)∈(0,1]输出x.

输出:x.

存在一个概率多项式时间算法能够通过格的一组基向量依照高斯分布抽取格上向量.本书称此算法为高斯抽样算法,记作SampleD.利用该算法可以在任意格Λ 上按照高斯分布DΛ,s,c 进行抽样.(注意到,找格的一组普通的基向量是容易的)我们假设SampleD 接入一个能够从DZ,s′,c′ 进行抽样的SampleZ 算法作为子程序.设B 为一个n 维格Λ 的基,s ＞0 为高斯参数,c 为一个中心.

算法.SampleD

输入: B,s ＞0,c ∈Rn.(www.daowen.com)

1.令vn ←0,cn ←c,For i ←n,n-1,··· ,1,do:

(a)令

(b)选择zi ～DZ,s′,c′

(c)ci-1 ←ci-zibi,vi-1 ←vi-zibi

2.输出v0.

输出:v0

可以验证SampleD 算法的输出服从高斯分布并且v0 到中心的距离由格基B 的Gram-Schmit正交向量的范数决定[38].从而容易想象假如输入SampleD 算法的基向量属于陷门基、具有较小的范数,则输出的向量v0 也应该与中心的距离较小.若没有陷门基的帮助,SampleD 无法输出中心附近的格向量.从而可以借助SampleD 定义一个以陷门基为陷门信息的单向函数,这就是PSF.