一種SDH對(A,b)的新的零知識證明協(xié)議

摘要:該文基于DBDH假設(shè)下的TOO/BB-E加密和SDH假設(shè)，提出一種新的SDH對的零知識證明協(xié)議。該協(xié)議比文獻(xiàn)[1]安全性更強。

關(guān)鍵詞:TOO/BB-E加密;DBDH假設(shè);零知識證明

中圖分類號:TP309文獻(xiàn)標(biāo)識碼: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

一些協(xié)議被設(shè)計成使得某個協(xié)議的參與者可以向其他人證明他掌握了某種秘密信息，同時并不泄露秘密信息的內(nèi)容給驗證者，這樣的協(xié)議稱為零知識證明協(xié)議[1]。本文基于DBDH假設(shè)下的TOO/BB-E加密和CR假設(shè)。提出一種新的SDH對的零知識證明協(xié)議。基于該協(xié)議將來可以構(gòu)造一種群簽名方案，其簽名長度為2215bits。

1 預(yù)備知識

1.1 雙線性映射

設(shè)G1和G2是階為素數(shù)p的循環(huán)群，定義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 假設(shè)

如果對于任意概率t-多項式時間算法A，是可以忽略的。

1.3 q-SDH假設(shè)

設(shè)G=是階數(shù)為素數(shù)p的循環(huán)群，如果對所有的概率多項式時間算法A，概率是可忽略的，其中x，γ∈Zp*。

1.4 TOO/BB-E加密算法[2]

設(shè)G1，G2是階為素數(shù)p的循環(huán)群，g為G1生成元，e為可計算的映射e:G1×G1→GT，H1，H2是hash函數(shù)。

密鑰生成:任取x，y，z∈Zp*計算g1=gx，g2=gy，g3=gz和Z=(g1，g2)。

加密:隨機選任意常數(shù)s，k，u，v，μ∈Zp*，令，。

密文:(a1，a2，c1，c2，c3，μ，r) 。

解密:。

2 一種SDH問題的零知識證明的協(xié)議

設(shè)G1，G2，GT為素數(shù)p的循環(huán)群， e，為可計算的雙線性映射e:G1×G1→G2，:G1×G1→GT，g，分別是G1，G2的生成元。取公共參數(shù)ω， 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是抗碰撞的哈希函數(shù)，并且i=1，2。下面使用協(xié)議1證明素數(shù)階群上離散對數(shù)的知識。

協(xié)議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進(jìn)行滿足以下等式的值(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)發(fā)送給Bob， 然后 Bob在Zp中隨機選擇詢問值c發(fā)送給Alice， Alice通過計算并發(fā)送回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:驗證者總是接受與一個誠實示證者的交互即協(xié)議1是完備的。

證明:如果Alice是一個擁有SDH對(A，b)的誠實示證者，并且遵守協(xié)議1中規(guī)定的指令，則， 所以(1)成立，類似的(2)(3)(4)成立;然后，，所以 (6)成立，類似的(7)(8)(9)成立;最后，

所以(5)成立。從而(1) ～ (9)都成立，因此，協(xié)議1是完備的即對Bob隨機選取詢問值的所有情況，Alice的應(yīng)答都能滿足他每一步的驗證。

引理2:協(xié)議1的副本在DBDH假設(shè)下可以仿真。

證明:首先描述一個輸出協(xié)議1證明副本的仿真器， 任意選取A∈G2，s，u，v，k，u∈Zp，

令如果DBDH假設(shè)在群 上成立， 由仿真器生成的五元組(a1，a2，c1，c2，c3)的分布與任一示證者輸出的分布是不可區(qū)分的。仿真器的剩余部分沒有用到知識A， b或s， 所以當(dāng)a1，a2，c1，c2，c3預(yù)先指定時仍然可以使用。當(dāng)預(yù)先指定的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)，與實際的協(xié)議副本相同。

引理3:存在一個協(xié)議1的提取器。

證明:在協(xié)議的第一步，示證者向驗證者發(fā)送(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的響應(yīng)依次為(fs，fu，fv，fb，fδ1，fδ2，fδ3)和(fs'，fu'，fv'，fb'，fδ1'，fδ2'，fδ3')， 它們均要滿足式(1) ～ (9).

令， 將上述三組響應(yīng)值集代入式(1) ～ (9)， 得到上述等式的兩個實例。

將等式(1)的兩個實例等號兩邊相除， 得g△fu=a1△c， 由于指數(shù)是素數(shù)階群的元素， 對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:協(xié)議1是誠實驗證者在DBDH假設(shè)下SDH對知識的零知識證明。

我們可以通過以上3個引理的證明得出定理1的證明。

參考文獻(xiàn):

[1] 張躍宇，陳陳杰，蘇萬力，王育民.一種IND-CCA2完全匿名的短群簽名[J].計算機學(xué)報，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.

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文