作为本文的一个工具,我们首先给出一个PSF函数的推广算法,该算法是由Gordon等人在设计格基群签名的工作中提出的[28].我们将此算法作为本方案的一个基本工具使用.

引理4.1 存在一个PPT算法以参数n,q = poly(n),m ＞n+8n log q,s 以及一个矩阵作为输入,输出矩阵满足：

1.矩阵A 的分布统计接近均匀分布并且ABt =0(modq)成立.

2.‖T‖≤O(n log q)并且AT=0(modq).

令n 为安全参数,q =poly(n),m ＞n+8n log q.s ≥为一个高斯参数.参数k =ω(log n)为整数.令h:{0,1}* →Znq 为一个安全的、抗碰撞的hash函数.设Alice为签名者,验证者为Bob,而Adjudicator作为一个判决者是一个可信的第三方.

判决者密钥生成: Adjudicator运行陷门抽样算法,得到一个随机矩阵以及相应的陷门基则,(APK,ASK)=(B,T).

密钥生成: Alice以(n,m,q,s,B) 为输入运行陷门抽样算法,得到一个输出矩阵A ∈以及陷门基 则(PK,SK)=(A,T′).

签名: 给定M,Alice选择一个随机比特串r ∈{0,1}k,计算h(M|r).令

则(e,r)作为普通签名.

验证: 当且仅当

该签名合法.

VES签名生成: Alice选择两个随机向量s1,s2 ∈Znq,依照高斯分布DZmq ,s,0 选择一个差错向量e′.Alice计算(www.daowen.com)

并且

Alice 生成一个NIWI（non-interactive witness-indistinguishable）证明π 来说明向量y2 接近格Λ(Bt),该技术的应用与文献[28]类似.

从而Alice发布消息M 的VES: ω =(y1,y2,π,μ,r,M).

VES验证: Bob计算

Bob接受该VES当且仅当

1.π 是正确的;

2.h(M||r)=Ay1(modq);

3.Ac=(h(M||r)+Ay2)(modq);

4.‖c‖≤

判决: 利用私钥T,判决者可以从y1 中抽取(e,s1).于是,假如y1 = Bts1+e(modq)Ae=h(M||r)(modq)并且判决者接受签名,否则拒绝.