2008年,Gentry等设计了一个随机预言机模型下可证安全的格基签名方案,本文称之为GPV签名.作为“hash and sign”方法设计格基签名的典型代表,GPV签名一经提出就成为格上数字签名设计的重要工具.GPV签名方案的参数同上述PSF的基本参数.设h(·) :{0,1}* →Zn 为一个抗碰撞的安全hash函数.

密钥生成.利用陷门抽样算法输出一个随机均匀的矩阵以及对应格Λ⊥q(A)上的陷门基T,则公钥为A,签名密钥为T.

签名.设消息为M ∈{0,1}*,随机选择一个长度为k 的比特串r,计算h(M,r).令

则消息的签名为(r,e).

验证.(www.daowen.com)

当且仅当签名满足Ae=h(M,r)(modq),成立接受签名.

说明: GPV签名及原像抽样函数中的原像的最小熵至少为ω(log n).这意味着,对于值域中的每一个向量y,都有约2ω(log n)个原像.因此,在使用原像抽样函数设计密码方案时切忌不能对同一个向量给出两个不同的原像,那样将意味着陷门信息的泄露.该结论被广泛的应用于本书的安全证明环节.2010年[47]通过并行运算大幅提升了原像抽样函数的实现效率.

原像抽样函数提出后就显示出了强大的设计功能,成为格密码设计一个非常有用的工具.原像抽样函数通过保证输出向量服从高斯分布,达到保护陷门基信息的目的.有效解决了早期格密码如NTRU,GGH等存在的陷门信息泄露的不足.另一个能够实现输出高斯分布进而保护陷门信息的方法是由Lyubashevsky提出的拒绝抽样技术.

利用原像抽样函数实现的方案设计中,安全证明是其中重要一环.在安全证明环节中,模拟者必须具有原像抽样的模拟能力,而对于不掌握陷门信息的模拟者而言这是困难的.因此,直接基于原像抽样函数设计的方案大多基于随机预言机模型设计.即通过随机预言机实现对敌手“原像询问”时的完美模拟.为了摆脱设计方案时对随机预言机的依赖.2010年起,原像抽样函数被陆续改进为几类格基代理算法,用于标准模型下格密码方案的设计.格基代理算法可以将一个带陷门基的格按照一定方式扩展为一个更大维数的格,同时生成该格的一组陷门基.不仅如此,新生成的格的陷门基完美的隐藏了原始格的陷门基.换句话说,利用新格的陷门基不能得到原来格上陷门基的任何信息.格基代理技术成为格上设计在标准模型下安全密码方案及格上身份基密码的一个重要工具.Bonsai trees（盆景树）技术作为首次提出的格基代理算法,在格密码的设计中具有举足轻重的地位.