摘 要:針對一般秘密共享方案或可驗(yàn)證秘密共享方案存在的缺點(diǎn)，結(jié)合橢圓曲線上雙線性對性質(zhì)和運(yùn)用雙線性Diffie-Hellman問題，構(gòu)造了一個(gè)基于雙線性對的無可信中心可驗(yàn)證秘密共享方案。在該方案中，共享秘密S是素?cái)?shù)階加法群G1上的一個(gè)點(diǎn)，在秘密分發(fā)過程中所廣播的承諾Cj是與雙線性有關(guān)的值。利用雙線性對的雙線性就可以實(shí)現(xiàn)共享秘密的可驗(yàn)證性，有效地防止參與者之間的欺詐行為，而不需要參與者之間執(zhí)行復(fù)雜的交互式證明，因而該方案避免了為實(shí)現(xiàn)可驗(yàn)證性而需交互大量信息的通信量和計(jì)算量，通信效率高，同時(shí)該方案的安全性等價(jià)于雙線性Diffie-Hellman假設(shè)的困難性。

關(guān)鍵詞:秘密共享;交互式證明; 雙線性對; 可信中心

中圖分類號(hào):TP393.08 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2010)12-0066-03

Verifiable Secret Sharing Scheme Based on Bilinear-pairs without Distribution Center

SHANG Xiao-yang， TANG Xi-lin

(School of Mathematics， South China University of Technology， Guangzhou 510640， China)

Abstract:NDBP-VSS based on bilinear-pairings is proposed in combination with the properties of bilinear-pairs on elliptic curve and bilinear Diffie-Hellman problem to overcome the disadvantages of the general secret sharing schemes and verifiable secret sharing schemes， in which the sharing secret S is a point on additive cyclic group G1 and the commitmentCj is the value relative to bilinear-pairs. The verifiableness of the sharing secret can be implemented by the properties of bilinear-pairs without implementation of complex interaction proofs of participants and numerous calculation. The communication efficiency was improved by the scheme. The security of this scheme is equivalent to the bilinear Diffie-Hellman assumption.

Keywords:secret sharing;interaction rerification; bilinear-pair; credible center

0 引 言

在秘碼體制中，可以將對關(guān)鍵信息的控制權(quán)利分發(fā)給團(tuán)體中的一些成員管理，分散加密、解密、簽名、驗(yàn)證權(quán)利。為了解決此類問題，1979年，Shamir率先提出門限秘密共享方案。門限秘密共享是信息安全和數(shù)據(jù)保密中的重要手段，它在重要信息和秘密數(shù)據(jù)的安全存放、傳輸、合法利用中起著非常關(guān)鍵的作用。

近年來，許多專家學(xué)者主要針對秘密共享方案中的防欺詐問題展開了研究。相繼分別提出了基于Lagrange插值多項(xiàng)式、射影幾何、中國剩余定理以及矩陣乘法的Karnin-Greene-Hellman門限秘密共享方案。在一般的秘密共享方案[1-5] 中存在2個(gè)問題:一是秘密分發(fā)中心是否將正確的子秘密分發(fā)給各個(gè)成員，各成員怎樣才能驗(yàn)證自己所接收到的子秘密是正確的;二是在秘密恢復(fù)階段，如何鑒別各成員提供子秘密的正確性。對這2個(gè)問題的研究，專家、學(xué)者提出了可驗(yàn)證的秘密共享方案[5]。本文結(jié)合可驗(yàn)證秘密共享方案[5]，提出了基于雙線性對的無可信中心的可驗(yàn)證秘密共享方案。

1 預(yù)備知識(shí)

1.1 雙線性對

定義1設(shè)G1，G2均為素?cái)?shù)階的加法群和乘法群，且|G1|=|G2|=q(q是一大素?cái)?shù))。假設(shè)G1，G2中離散對數(shù)問題是難解的。雙線性映射e:G1×G1→G2的性質(zhì)如下:

(1) 雙線性。對P，Q，R∈G1;a，b∈Z*q，有e(P+Q，R)=e(P，R)e(Q，R)， e(P，Q+R)=e(P，Q)e(P，R)， e(aP，bQ)=e(P，Q)ab;

(2) 非退化性。P，Q∈G1，使得e(P，Q)≠1;

(3) 可計(jì)算性。對P，Q∈G1，都存在一個(gè)有效的多項(xiàng)式時(shí)間的算法來計(jì)算e(P，Q)。

1.2 Diffie-Hellman問題

Diffie-Hellman問題定義:假設(shè)加法群G=〈g〉，G的兩個(gè)元素g1:=a#8226;g和g2:=b#8226;g。已知g是生成元，但不知道a和b，要計(jì)算g3=(ab)#8226;g。

定義2設(shè)G是有限循環(huán)群，g是G的生成元。

(1) 離散對數(shù)問題(DLP)。給定(g，a#8226;g)，對任意的a∈Z*|G|，求a;

(2) 計(jì)算性Diffie-Hellman問題(CDHP)。給定(g，a#8226;g，b#8226;g)，對任意的a，b∈Z*|G|，計(jì)算(ab)#8226;g;

(3)判定性Diffie-Hellman問題(DDHP)。給定(g，a#8226;g，b#8226;g)，對任意的a，b∈Z*|G|，判斷(ab)#8226;g=c#8226;g是否成立。

(4) 雙線性Diffie-Hellman問題(BDHP)。給定(P，aP，bP，cP)，對任意a，b∈R Z*q，計(jì)算e(P，P)abc∈G2。

2 基于橢圓曲線的可驗(yàn)證秘密共享方案[5-8]

假設(shè)該方案有一個(gè)秘密需要在n個(gè)參與者Γi(i=1，2，…，n)之間共享，僅當(dāng)t個(gè)或t個(gè)以上的參與者聯(lián)合才能恢復(fù)秘密，而少于t個(gè)參與者的任何組合都無法得到秘密的任何信息。為實(shí)現(xiàn)秘密的分配，系統(tǒng)中需要有一個(gè)誠實(shí)可信的秘密分發(fā)中心D。具體方案如下:

該方案分為4個(gè)階段:系統(tǒng)初始化階段、子秘密分發(fā)階段、子密鑰驗(yàn)證階段和秘密重構(gòu)階段。

2.1 系統(tǒng)初始化階段

設(shè)G1是素?cái)?shù)階的橢圓曲線加法群，其階為q，并且G1=〈P〉;G2是q階乘法群，它們之間存在雙線性映射，能被有效計(jì)算;G1，G2上的離散對數(shù)都是難解的;秘密S∈G1。

2.2 子秘密分發(fā)階段

秘密分發(fā)中心D隨機(jī)選取F0 ，F(xiàn)1 ，F(xiàn)2 ，…，F(xiàn)t-1 ∈G*1 ，構(gòu)造一個(gè)G1上t-1次多項(xiàng)式:

F(x)=F0+F1#8226;x+F2#8226;x2+…+Ft-1#8226;xt-1

式中:Ft-1#8226;xt-1表示在橢圓曲線加法群G1上xt-1個(gè)Ft-1相加，并滿足F0=F(0)=S，計(jì)算Si=F(i)作為成員Γi(i=1，2，…，n)的共享份額，并通過安全信道秘密發(fā)送給Γi(i=1，2，…，n);同時(shí)保密F1，F(xiàn)2，…，F(xiàn)t-1，計(jì)算并廣播與雙線性對有關(guān)的承諾Cj=e(P，F(xiàn)j)，j=0，1，2，…，t-1。

2.3 子密鑰驗(yàn)證階段

Γi接收到Si后，可通過下式驗(yàn)證接收到子密鑰的正確性:

e(P，Si)=∏t-1j=0Cijj

2.4 秘密重構(gòu)階段

當(dāng)t個(gè)成員Γj(j=0，1，2，…，t-1)拿出他們各自的子密鑰Si后可利用Lagrange插值多項(xiàng)式來恢復(fù)秘密S:

S=∑i∈B[ LBi(i)#8226;Si]

式中:LBi(i)為插值系數(shù)，LBi(x)=∏j∈B\\\\{i}x-xjxi-xj。

隨后可利用公開信息C0驗(yàn)證S的正確性:C0=e(P，S)。

2.5 安全性分析

(1) 在上述可驗(yàn)證的秘密共享方案中，G1上的多項(xiàng)式F(x)的系數(shù)F0 ，F(xiàn)1 ，F(xiàn)2 ，…，F(xiàn)t-1 ∈G*1和承諾C0，C1，C2，…，Ct-1都是安全的，它們都屬于雙線性Diffie-Hellman問題，這就保證了該可驗(yàn)證秘密共享方案的安全性。

(2) 在上述可驗(yàn)證的秘密共享方案中，任何t-1個(gè)或少于t-1成員的聯(lián)合都不能重構(gòu)秘密，它們也屬于雙線性Diffie-Hellman問題，這也就保證了該可驗(yàn)證秘密共享方案的安全性。

3基于雙線性對的無可信中心可驗(yàn)證秘密共享方案構(gòu)成

(1) 由于一般秘密共享方案或可驗(yàn)證的秘密共享方案都需要一個(gè)誠實(shí)可信的秘密分發(fā)中心D來分發(fā)秘密，但現(xiàn)實(shí)中很難找到這樣一個(gè)可信中心D，這就成為秘密共享方案的一個(gè)瓶頸。本文將上述可驗(yàn)證的秘密共享方案推廣為無可信中心的秘密共享方案。

約定上述基于橢圓曲線的可驗(yàn)證秘密共享方案為BP_VSS[ S;Cj;Si;F(x)] 。其中，S為共享秘密;Cj為公共信息;Si為Γi的子秘密;F(x)為可信中心隨機(jī)選取的函數(shù)。

本文提出的方案包括3個(gè)階段:秘密分發(fā)階段、計(jì)算子秘密階段、秘密重構(gòu)階段。

秘密分發(fā)階段成員Γi執(zhí)行基于雙線性對的無可信中心可驗(yàn)證秘密共享方案NDBP_VSS[ i;Cij;Sik;F(x)] ，即Γi隨機(jī)選取i ∈R G1 和多項(xiàng)式Fi (x) = ∑t-1j = 0Fij xj∈R G1 [x]，使得Fi(0)=Fi0=i;同時(shí)Γi保密多項(xiàng)式Fi(x)，并公布Cij=e(P，F(xiàn)ij)，0≤jk)的正確性可以被接收者驗(yàn)證。

計(jì)算子秘密階段所有成員成功發(fā)送了他們的子密鑰后，每個(gè)參與者計(jì)算他的秘密共享份額Si:

Si=∑nj=1Fj(i)

秘密重構(gòu)階段當(dāng)t個(gè)成員Γi(i=1，2，…，t，i∈B，|B|=t)正確產(chǎn)生他們各自的子密鑰Si后，就可以用Lagrange插值多項(xiàng)式來計(jì)算S:

S=∑i∈B[ LBi(i)#8226;Si]

式中:LBi(i)為Lagrange插值系數(shù)，LBi(x)=∏j∈B\\\\{i}x-xjxi-xj。

記S∑ni=1i，C∏nk=1Cki，F(xiàn)(x)∑ni=1Fi(x)。隨后可利用公開信息C0驗(yàn)證S的正確性，即C0=e(P，S)。在上述無可信中心秘密共享方案中，通過雙線性對的雙線性就可以實(shí)現(xiàn)方案的可驗(yàn)證性，不需要執(zhí)行任何復(fù)雜的交互，因此其通信效率比較高。

(2) 該方案安全性分析

① 無可信中心的秘密共享方案的安全性上述基于橢圓曲線的可驗(yàn)證秘密共享方案的安全性，都是基于雙線性Diffie-Hellman假設(shè)的難解性。利用雙線對的雙線性和計(jì)算性Diffie-Hellman問題、判定性Diffie-Hellman問題，證明本文提出方案的安全性雙線性Diffie-Hellman假設(shè)的難解性。

②Γk所接收到的Sik=Fi(k)的正確性可以被驗(yàn)證。

由于Fi(k)=Fik，所以Γk可以計(jì)算Cik ′ = e(P，F(xiàn)ik )，再根據(jù)Γi公布的信息Cik  ，與自己計(jì)算得到的Cik ′進(jìn)行比較，若二者相等，則Γi沒有欺騙Γk，否則Γk接收的Fi(k)就不正確。

③ 通過雙線性對的雙線性性質(zhì)可以有效地防止參與者之間的欺詐行為，而不需要參與者之間執(zhí)行復(fù)雜的交互式協(xié)議，因而該方案的效率比較高。

4 結(jié) 語

在此，基于橢圓曲線上雙線性的對性質(zhì)提出了一種無可信中心的可驗(yàn)證秘密共享方案，它突破一般秘密共享方案需有誠實(shí)可信的秘密分發(fā)中心來分發(fā)共享秘密的常規(guī)，結(jié)合橢圓曲線上雙線性對的雙線性，運(yùn)用雙線 性的Diffie-Hellman假設(shè)，通過分布式，實(shí)現(xiàn)對無可信秘密分發(fā)中心的共享秘密分發(fā)，利用橢圓曲線上雙線性對的雙線性性質(zhì)可以有效地防止參與者之間的欺詐行為，而不需要參與者之間執(zhí)行復(fù)雜的交互式協(xié)議就可以進(jìn)行秘密共享的公開驗(yàn)證，因而該方案的通信效率比較高，具有很好的應(yīng)用價(jià)值。由于無線傳感器網(wǎng)絡(luò)自身的一些特性，如網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是動(dòng)態(tài)變化的，所有的節(jié)點(diǎn)都是分布式存在的，不存在可信的第三方，且節(jié)點(diǎn)的資源有限等特點(diǎn)，如何把本文所提出的方案運(yùn)用到無線傳感器網(wǎng)絡(luò)將是下一步繼續(xù)研究的目標(biāo)。

參考文獻(xiàn)

[1]TAN K J，ZHU H W， GU S J. Cheater identification in threshold scheme [J].Computer Communication，1999，22(8):762-765.

[2]YANG Chou-chen， CHANG Ying-yi， HWANG Min-shiang. Amulti-secret sharing scheme[J].Applied Mathematics and Computation，2004，152(2):483-490.

[3]LIN Chang-yu， LEIN Harn. Perfect threshold secret sharing scheme[M]. Beijing: Key Laboratory of Communication and Information System， 2009.

[4]甘志，李鑫，陳克非.公開可驗(yàn)證的門限簽密方案[C].中國密碼學(xué)會(huì)2004年論文集，2004.

[5]田有亮，彭長根.基于雙線性對的可驗(yàn)證秘密共享方案[J].計(jì)算機(jī)應(yīng)用，2007，27(12):125-127.

[6]黃東平，王華勇，黃連生，等.動(dòng)態(tài)門限秘密共享方案[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版，2006，46(1):102-105.

[7]許春香，魏仕民，肖國鎮(zhèn).定期更新防欺詐的秘密共享方案[J].北京:計(jì)算機(jī)學(xué)報(bào)，2002，25(6):657-660.

[8]張串絨，肖國鎮(zhèn).利用身份和雙線性對的多重簽密方案[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版，2007，34(2):270-273.

[9]廖遼軍，柳毅，王育民.一個(gè)有效的(t，n)門限多重秘密共享體制[ J] .電子學(xué)報(bào)，2006(4):2-3.

[10]韓金廣，亢保元，王慶菊.一個(gè)新的防欺詐動(dòng)態(tài)秘密共享方案[ J] .華東交通大學(xué)學(xué)報(bào)，2005，22(4):155-157，164.