摘要：基于线性假设下的Cramer-shoup加密方案和SDH假设，提出一种新的(A,x,y)知识的零知识证明协议。该协议比文献[2]中SDH对(A,x)知识的零知识证明协议多了一个参数。
关键词：线性Cramer-shoup加密；零知识证明；SDH假设
中图分类号：TP309文献标识码：A文章编号：1009-3044(2008)34-1760-02
A New Zero Knowledge Proof Protocal for Knowledge of (A,x,y)
WANG Zhan-jun1, MA Hai-ying2
(1.School of Scicnce, Nantong University, Nantong 226007, China; 2.Computer Science and Technology School, Nantong University, Nantong 226019, China)
Abstract: This paper presents a new zero knowledge protocol for knowledge of (A,x,y), which is based on Cramer-shoup encryption from linear assumption. Compared with reference,this protocol has one more parameter.
Key words: linear cramer-shoup encryption; zero knowledge proof; SDH assumption
1 引言
秘密的零知识证明是指证明者P使验证者V确信证明者知道某一秘密知识而没有向验证者泄露有关该秘密的任何有用信息。在文献[1]中，Bonch 等人基于线性假设下的线性加密方案和SDH假设给出了拥有SDH对(A,x)知识的一种零知识证明协议，并据此构造了一种CPA完全匿名的短群签名方案；在文献[2]中，张跃宇等人基于线性假设下的Cramer-shoup加密方案和SDH假设给出了拥有SDH对(A,x)知识的另一种零知识证明协议，并据此构造了一种IND-CCA2完全匿名的短群签名方案。本文基于线性假设下的Cramer-shoup加密方案和SDH假设给出了拥有三元组(A,x,y)知识的一种新的零知识证明协议。由于三元组(A,x,y)比SDH对(A,x)多一个参数，基于本文的协议将来可构造满足不可陷害性的IND-CCA2完全匿名的短群签名方案。
2 预备知识
2.1 双线性群
设G1=
2.2 q-SDH假设
设G=
■是可忽略的,其中x,y∈Zp*。
2.3 判定线性Diffie-Hellman(DLDH)假设
设G=
■是可忽略的。
3 一种新的(A,x,y)知识的零知识证明协议
设GT为素数阶p的循环群，e:G×G→GT为可计算得映射。取公共参数w,g,g1,g2,g3,h∈G，其中w=gγ, γ∈Zp*。
令■。三元组(A,x,y)满足■，其中A∈G,x,y∈Zp，且Ax+γ=ghy。下面用协议1证明素数阶群上离散对数知识。
协议1示证者Alice随机选取α,β∈Zp计算A的线性Cramer-Shoup加密■，然后计算辅助值δ1=xα, δ2=xβ，Alice和验证者Bob进行满足以下等式值(α,β,x,y, δ1, δ2)的知识证明。
■
证明过程如下
Alice随机选取rα,rβ,rx,ry,rδ1, rδ2,∈Zp，计算
■
然后将(T1,T2,T3,T4,R1,R2,R3,R4,R5,R6,R7)发送给Bob，Bob在Zp中随机选择询问值c发送给Alice，Alice计算并发送Sa=ra+ca,Sβ=rβ+cβ,Sx=rx+cx,Sy=ry+Cy,Sδ1=rδ1+cδ1, Sδ2=rδ2+cδ2，最后Bob验证以下7个等式：
■
如果上述7个等式都成立，Bob接受证明。
定理1 协议1是诚实验证者在判定线性假设下三元组(A,x,y)知识的零知识证明。
定理1的证明可以通过以下3个引理的证明得出。
引理1 协议1是完备的，即验证者总是接受与一个诚实示证者的交互。
证明如果Alice是一个拥有三元组(A,x,y) 的诚实示证者，并且遵循协议1规定的指令，那么（1）—（7）式必然成立。
首先■，所以（1）式成立，类似的（2）、（3）式成立；然后■，所以（5）式成立，类似的（6）、（7）成立；最后
■
所以（4）式成立。因此，对Bob随机选取询问值的所有情况，Alice的应答都能满足他每一步的验证.
引理2 协议1的副本在判定假设下可以仿真。
证明 首先描述一个输出协议1证明副本的仿真器选取A∈G,α,β∈Zp，令T1=g1α,T2=g2β,T3=g3α+β,T4=Ah1αh2β。假设判定线性假设在G上成立，由仿真器生成的四元组(T1,T2,T3,T4)的分布与任一示证者输出的分布是不可区分的，仿真器的剩余部分没有用到A,x,y, α或β，所以当T1,T2,T3,T4预先指定时仍可以使用，当预先指定的T1,T2,T3,T4是某个A的随机线性Cramer-Shoup加密时，证明副本的剩余部分可以被完美仿真。
随机选取询问值c∈Zp，Sα,Sβ,Sx,Sy,Sδ1, Sδ2∈Zp，计算
■
上述值显然满足等式（1）—（7），进一步，R1,R2,R3,R4,R5,R6,R7这些值的分布的分布与实际副本的分布一样。此时仿真器输出的副本为(T1,T2,T3,T4,R1,R2,R3,R4,R5,R6,R7,c, Sα,Sβ,Sx,Sy,Sδ1, Sδ2)，与实际的协议副本相同。
引理3 存在一个协议1的提取器。
证明 在协议1的第一步，示证者向验证者发送(T1,T2,T3,T4,R1,R2,R3,R4,R5,R6,R7)。对于不同的询问值c和c"，示证者的响应分别为(Sα,Sβ,Sx,Sy,Sδ1, Sδ2)和(Sα",Sβ",Sx",Sy",Sδ1", Sδ2")，它们均满足等式（1）—（7），令■的定义与前边类似，将上述两组响应值集代入（1）—（7），得到上述等式的两个实例。
将等式（1）的两端分别相除得g1ΔSa=T1Δc，由于指数是素数阶群上的元素，对g1ΔSa=T1Δc求根运算得g1■=T1，其中■=ΔSα/Δc，类似的，由等式（2）可得g2■=T2，由等式（3）可得g3■+■=T3，将等式（5）两端相除得■，代入g1■=T1得■，同理由（6）得Δ■δ2=β??Sx，最后将等式（4）两端相除得
■
令■，
将上述等式去Δc得：
■
令■，可得■，因此提取器得到了(■,■,■)，这个三元组与Cramer-Shoup加密(T1,T2,T3,T4)中的(A,x,y)一样。
参考文献：
[1] Bonch D,Boyen X,Shacham H.Short group signatures[C].California,USA:Proceedings of 24th Annual International Cryptology Conference,2004:41-55.
[2] 张跃宇,陈杰,苏万力,等.一种IND-CCA2完全匿名的短群签名[J].计算机学报,2007,30(10):1865-1871.