一種新的（Ａ，ｘ，ｙ）知識的零知識證明協(xié)議

摘要：基于線性假設(shè)下的Cramer-shoup加密方案和SDH假設(shè)，提出一種新的(A，x，y)知識的零知識證明協(xié)議。該協(xié)議比文獻(xiàn)[2]中SDH對(A，x)知識的零知識證明協(xié)議多了一個參數(shù)。

關(guān)鍵詞：線性Cramer-shoup加密；零知識證明；SDH假設(shè)

中圖分類號：TP309文獻(xiàn)標(biāo)識碼：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確信證明者知道某一秘密知識而沒有向驗證者泄露有關(guān)該秘密的任何有用信息。在文獻(xiàn)[1]中，Bonch 等人基于線性假設(shè)下的線性加密方案和SDH假設(shè)給出了擁有SDH對(A，x)知識的一種零知識證明協(xié)議，并據(jù)此構(gòu)造了一種CPA完全匿名的短群簽名方案；在文獻(xiàn)[2]中，張躍宇等人基于線性假設(shè)下的Cramer-shoup加密方案和SDH假設(shè)給出了擁有SDH對(A，x)知識的另一種零知識證明協(xié)議，并據(jù)此構(gòu)造了一種IND-CCA2完全匿名的短群簽名方案。本文基于線性假設(shè)下的Cramer-shoup加密方案和SDH假設(shè)給出了擁有三元組(A，x，y)知識的一種新的零知識證明協(xié)議。由于三元組(A，x，y)比SDH對(A，x)多一個參數(shù)，基于本文的協(xié)議將來可構(gòu)造滿足不可陷害性的IND-CCA2完全匿名的短群簽名方案。

2 預(yù)備知識

2.1 雙線性群

設(shè)G1=，G2=和G3 是階為素數(shù)p的循環(huán)群，e:G×G→GT為可計算得映射，該映射具有兩個性質(zhì)：1) 雙線性，即對所有的u∈G1，v∈G2 及a，b∈Z，有e(ua，vb)ab 。2) 非退化性，即e(g1，g2)≠1。

2.2 q-SDH假設(shè)

設(shè)G=是階數(shù)為素數(shù)p 的循環(huán)群，對所有的概率多項式時間算法 A，概率

■是可忽略的，其中x，y∈Zp*。

2.3 判定線性Diffie-Hellman(DLDH)假設(shè)

設(shè)G=是階數(shù)為素數(shù)p 的循環(huán)群， u，v，h，η∈G，且a，b∈Z ，對所有的概率多項式時間算法 A ， 概率

■是可忽略的。

3 一種新的(A，x，y)知識的零知識證明協(xié)議

設(shè)GT為素數(shù)階p的循環(huán)群，e:G×G→GT為可計算得映射。取公共參數(shù)w，g，g1，g2，g3，h∈G，其中w=gγ， γ∈Zp*。

令■。三元組(A，x，y)滿足■，其中A∈G，x，y∈Zp，且Ax+γ=ghy。下面用協(xié)議1證明素數(shù)階群上離散對數(shù)知識。

協(xié)議1示證者Alice隨機選取α，β∈Zp計算A的線性Cramer-Shoup加密■，然后計算輔助值δ1=xα， δ2=xβ，Alice和驗證者Bob進(jìn)行滿足以下等式值(α，β，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)發(fā)送給Bob，Bob在Zp中隨機選擇詢問值c發(fā)送給Alice，Alice計算并發(fā)送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 協(xié)議1是誠實驗證者在判定線性假設(shè)下三元組(A，x，y)知識的零知識證明。

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

引理1 協(xié)議1是完備的，即驗證者總是接受與一個誠實示證者的交互。

證明如果Alice是一個擁有三元組(A，x，y) 的誠實示證者，并且遵循協(xié)議1規(guī)定的指令，那么（1）—（7）式必然成立。

首先■，所以（1）式成立，類似的（2）、（3）式成立；然后■，所以（5）式成立，類似的（6）、（7）成立；最后

■

所以（4）式成立。因此，對Bob隨機選取詢問值的所有情況，Alice的應(yīng)答都能滿足他每一步的驗證.

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

證明 首先描述一個輸出協(xié)議1證明副本的仿真器選取A∈G，α，β∈Zp，令T1=g1α，T2=g2β，T3=g3α+β，T4=Ah1αh2β。假設(shè)判定線性假設(shè)在G上成立，由仿真器生成的四元組(T1，T2，T3，T4)的分布與任一示證者輸出的分布是不可區(qū)分的，仿真器的剩余部分沒有用到A，x，y， α或β，所以當(dāng)T1，T2，T3，T4預(yù)先指定時仍可以使用，當(dāng)預(yù)先指定的T1，T2，T3，T4是某個A的隨機線性Cramer-Shoup加密時，證明副本的剩余部分可以被完美仿真。

隨機選取詢問值c∈Zp，Sα，Sβ，Sx，Sy，Sδ1， Sδ2∈Zp，計算

■

上述值顯然滿足等式（1）—（7），進(jìn)一步，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)，與實際的協(xié)議副本相同。

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

證明 在協(xié)議1的第一步，示證者向驗證者發(fā)送(T1，T2，T3，T4，R1，R2，R3，R4，R5，R6，R7)。對于不同的詢問值c和c'，示證者的響應(yīng)分別為(Sα，Sβ，Sx，Sy，Sδ1， Sδ2)和(Sα'，Sβ'，Sx'，Sy'，Sδ1'， Sδ2')，它們均滿足等式（1）—（7），令■的定義與前邊類似，將上述兩組響應(yīng)值集代入（1）—（7），得到上述等式的兩個實例。

將等式（1）的兩端分別相除得g1ΔSa=T1Δc，由于指數(shù)是素數(shù)階群上的元素，對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)一樣。

參考文獻(xiàn)：

[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].計算機學(xué)報，2007，30(10):1865-1871.