设n 为安全参数,q =poly(n),m ≥5n lg q.

1.利用陷门抽样算法,输出一个随机均匀的矩阵以及对应格Λ⊥q(A)上的陷门基T,满足‖T‖≤O(n log q).令高斯参数

2.矩阵A 定义了一个陷门单向函数f(s) = As(modq) ,T 为陷门.函数的定义域为 对任给的向量u ∈Zn ,利用陷门可以求的u 在f(s)=As(modq)下的原像.

算法.SamplePre(A,T,s,u)

输入: A,u ∈Zn,T,s.

1.计算t ∈Zm: At=u(modq).(www.daowen.com)

2.抽取

3.输出e=t+v.

输出:e.

容易验证Ae = At+Av = u(modq),且由引理2.6,向量u 在f(s) =As(modq)下的原像的最小熵至少为n-1.

在原像抽样函数中,输入的基向量的范数决定了输出向量的尺寸.特别的,当我们选择一组陷门基作为基向量时,输出向量的范数能够达到较小的要求.从而,PSF成为一个陷门单向函数,只有拥有陷门的人才能输出符合要求的向量u 在f(s)=As(modq)下的原像.这就是第一个基于随机预言机模型的的可证明安全的格基数字签名: GPV 数字签名方案.