基于雙線性的無可信中心可驗證秘密共享方案

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

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

中圖分類號:TP393.08 文獻標識碼:A

文章編號: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ā)給團體中的一些成員管理，分散加密、解密、簽名、驗證權(quán)利。為了解決此類問題，1979年，Shamir率先提出門限秘密共享方案。門限秘密共享是信息安全和數(shù)據(jù)保密中的重要手段，它在重要信息和秘密數(shù)據(jù)的安全存放、傳輸、合法利用中起著非常關(guān)鍵的作用。

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

1 預(yù)備知識

1.1 雙線性對

定義1設(shè)G1，G2均為素數(shù)階的加法群和乘法群，且|G1|=|G2|=q(q是一大素數(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) 可計算性。對P，Q∈G1，都存在一個有效的多項式時間的算法來計算e(P，Q)。

1.2 Diffie-Hellman問題

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

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

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

(2) 計算性Diffie-Hellman問題(CDHP)。給定(g，a#8226;g，b#8226;g)，對任意的a，b∈Z*|G|，計算(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，計算e(P，P)abc∈G2。

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

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

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

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

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

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

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

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個Ft-1相加，并滿足F0=F(0)=S，計算Si=F(i)作為成員Γi(i=1，2，…，n)的共享份額，并通過安全信道秘密發(fā)送給Γi(i=1，2，…，n);同時保密F1，F(xiàn)2，…，F(xiàn)t-1，計算并廣播與雙線性對有關(guān)的承諾Cj=e(P，F(xiàn)j)，j=0，1，2，…，t-1。

2.3 子密鑰驗證階段

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

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

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

當t個成員Γj(j=0，1，2，…，t-1)拿出他們各自的子密鑰Si后可利用Lagrange插值多項式來恢復(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驗證S的正確性:C0=e(P，S)。

2.5 安全性分析

(1) 在上述可驗證的秘密共享方案中，G1上的多項式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問題，這就保證了該可驗證秘密共享方案的安全性。

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

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

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

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

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

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

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

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

秘密重構(gòu)階段當t個成員Γi(i=1，2，…，t，i∈B，|B|=t)正確產(chǎn)生他們各自的子密鑰Si后，就可以用Lagrange插值多項式來計算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驗證S的正確性，即C0=e(P，S)。在上述無可信中心秘密共享方案中，通過雙線性對的雙線性就可以實現(xiàn)方案的可驗證性，不需要執(zhí)行任何復(fù)雜的交互，因此其通信效率比較高。

(2) 該方案安全性分析

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

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

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

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

4 結(jié) 語

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

參考文獻

[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]甘志，李鑫，陳克非.公開可驗證的門限簽密方案[C].中國密碼學(xué)會2004年論文集，2004.

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

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

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

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

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

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