摘要:该文基于DBDH假设下的TOO/BB-E加密和SDH假设,提出一种新的SDH对的零知识证明协议。该协议比文献[1]安全性更强。
关键词:TOO/BB-E加密;DBDH假设;零知识证明
中图分类号:TP309文献标识码:A文章编号:1009-3044(2010)21-5793-03
A New Zero Knowledge Proof Protocal for Knowledge of SDH Pair (A,b)
CHEN Xin, WANG Zhan-jun
(School of Science, Nantong University ,Nantong 226007, China)
Abstract: This paper presents a new zero-knowledge protocol for SDH pair, which based on TOO/BB-E encryption from DBDH assumption. This protocal"s security is stronger than reference[1].
Key words: TOO/BB-E encryption; DBDH assumption; zero knowledge proof
一些协议被设计成使得某个协议的参与者可以向其他人证明他掌握了某种秘密信息,同时并不泄露秘密信息的内容给验证者,这样的协议称为零知识证明协议[1]。本文基于DBDH假设下的TOO/BB-E加密和CR假设。提出一种新的SDH对的零知识证明协议。基于该协议将来可以构造一种群签名方案,其签名长度为2215bits。
1 预备知识
1.1 双线性映射
设G1和G2是阶为素数p的循环群,定义g是G1的生成元;e是可计算的映射e:G1×G1→G2,满足以下条件:
1) 双线性:对于所有的u∈g1,v∈g1及a,b∈Z,有e(ua,vb)=e(u,v)ab。
2) 非退化性:e(g,g)≠1。
3) 可计算性:?坌u,v∈G1,e(u,v)是可计算的。
1.2 DBDH 假设
如果对于任意概率t-多项式时间算法A,是可以忽略的。
1.3 q-SDH假设
设G=
1.4 TOO/BB-E加密算法[2]
设G1,G2是阶为素数p的循环群,g为G1生成元,e为可计算的映射e:G1×G1→GT,H1,H2是hash函数。
密钥生成:任取x,y,z∈Zp*计算g1=gx,g2=gy,g3=gz和Z=(g1,g2)。
加密:随机选任意常数s,k,u,v,μ∈Zp*,令,。
密文:(a1,a2,c1,c2,c3,μ,r) 。
解密:。
2 一种SDH问题的零知识证明的协议
设G1,G2,GT为素数p的循环群, e,为可计算的双线性映射e:G1×G1→G2,:G1×G1→GT,g,分别是G1,G2的生成元。取公共参数ω, g, g1,g2, g3, ∈G1,g∈G2 其中ω=γ, γ∈Zp*, g1=gx,g2=gy,g3=gz,Z=e(g1,g2),并任取s,k,u,v,μ∈Zp,SDH对(A,b)满足, 其中A∈G2,b∈Zp*且Ab+γ=,定义Hi是抗碰撞的哈希函数,并且i=1,2。下面使用协议1证明素数阶群上离散对数的知识。
协议1
示证者Alice随机选择s,k,u,v,μ∈Zp, 计算(A,b)的TOO/BB-E加密a1=gu,a2=gy,α=H1(gk),c1=gs,c2=ZSA,c3=(g1αg3)S,β=H2(a1,a2,c1,c2,c3),r=(k-β-uμ)v-1 mod p,然后计算辅助值δ1=sb, δ2=ub, δ3=vb。
Alice和验证者Bob进行满足以下等式的值(s,u,v,b, δ1, δ2, δ3)的知识证明:
证明过程如下:
首先, Alice随机选择rs,ru,rv,rb,rδ1,rδ2,rδ3∈Zp, 计算R1←gru,,R2←grv,R3←grs,R4←(g1αg3)rs,, 。接下来示证者Alice将(a1,a2,c1,c2,c3,R1,R2,R3,R4,R5,R6,R7,R8,R9)发送给Bob, 然后 Bob在Zp中随机选择询问值c发送给Alice, Alice通过计算并发送回fs=rs+cs,fu=ru+cu,fv=rv+cv,fb=rb+cb,fδ1=rδ1+cδ1,fδ2=rδ2+cδ2,fδ3=rδ3+cδ3∈Zp, 最后, Bob验证以下9个等式:
如果上述9个等式都成立,则Bob接受证明。
引理1:验证者总是接受与一个诚实示证者的交互即协议1是完备的。
证明:如果Alice是一个拥有SDH对(A,b)的诚实示证者,并且遵守协议1中规定的指令,则, 所以(1)成立,类似的(2)(3)(4)成立;然后,,所以 (6)成立,类似的(7)(8)(9)成立;最后,
所以(5)成立。从而(1) ～ (9)都成立,因此,协议1是完备的即对Bob随机选取询问值的所有情况,Alice的应答都能满足他每一步的验证。
引理2:协议1的副本在DBDH假设下可以仿真。
证明:首先描述一个输出协议1证明副本的仿真器, 任意选取A∈G2,s,u,v,k,u∈Zp,
令如果DBDH假设在群 上成立, 由仿真器生成的五元组(a1,a2,c1,c2,c3)的分布与任一示证者输出的分布是不可区分的。仿真器的剩余部分没有用到知识A, b或s, 所以当a1,a2,c1,c2,c3预先指定时仍然可以使用。当预先指定的a1,a2,c1,c2,c3是某个元素A的随机线性TOO/BB-E加密时,证明副本的剩余部分可以被完美仿真。
随机选择询问值,并令,则式(1)成立。u和c选定后, ru和fu中选定其中一个, 则另一个也随之确定, 并且如果一个是均匀随机选择的, 那么另一个也必将是均匀随机选择的, 所以fu和R1的分布与实际副本相同。R2,R3,R4的选择也是类似的。选择fb,fδ1,fδ2,fδ3∈Zp, 并令所有被计算的值的分布依然与实际副本一样。
令, 情况也是相同的。这时仿真器输出的副本为(a1,a2,c1,c2,c3,R1,R2,R3,R4,R5,R6,R7,R8,R9,c,fs,fu,fv,fb,fδ1,fδ2,fδ3),与实际的协议副本相同。
引理3:存在一个协议1的提取器。
证明:在协议的第一步,示证者向验证者发送(a1,a2,c1,c2,c3,R1,R2,R3,R4,R5,R6,R7,R8,R9,c,fs,fu,fv,fb,fδ1,fδ2,fδ3)。对于不同的询问值c和c",示证者Alice的响应依次为(fs,fu,fv,fb,fδ1,fδ2,fδ3)和(fs",fu",fv",fb",fδ1",fδ2",fδ3"), 它们均要满足式(1) ～ (9).
令, 将上述三组响应值集代入式(1) ～ (9), 得到上述等式的两个实例。
将等式(1)的两个实例等号两边相除, 得g△fu=a1△c, 由于指数是素数阶群的元素, 对g△fu=a1△c求根运算得g=a1, 其中= △fu/△c, 同理由等式(2) ,(3),(4)得将式(6)的两个实例等号两边分别相除,得g△fb=a1△fδ2, 代入a1=g得△fδ2=△fb, 类似的由(7),(8),(9)也可得△fδ3=△fb,△fδ1=△fb。最后,将式(5)的两个实例相除得:
令△fb/△c对上式两边去△c得:
令,可得 。
因此提取器得到了SDH对(A,),因为fs=rs+cs,fs"+rs+c"s. 所以, 。从而这个对与加密(a1,a2,c1,c2,c3,u,r)中的SDH对相同。
定理1:协议1是诚实验证者在DBDH假设下SDH对知识的零知识证明。
我们可以通过以上3个引理的证明得出定理1的证明。
参考文献:
[1] 张跃宇,陈陈杰,苏万力,王育民.一种IND-CCA2完全匿名的短群签名[J].计算机学报,2007,30(10):1865-1871.
[2] Aggelos Kiayias, Moti Yung. Group Signature with Efficient Concurrent Join [J]. Proceedings of Eurocrypt. Theory and Application of Cryptographic Techniques,1991, 63(3), 257-265.
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文