橢圓曲線上的信息論安全的可驗證隱秘共享方案

千里之行，始于足下。第2頁/共2頁精品文檔推薦橢圓曲線上的信息論安全的可驗證隱秘共享方案2011年12月JournalonCommunicationsDecember2011第32卷第12期通信學(xué)報Vol.32No.12橢圓曲線上的信息論安全的可驗證隱秘共享方案

田有亮1,3，馬建峰2，彭長根3，陳曦1

（1.西安電子科技大學(xué)通信工程學(xué)院，陜西西安710071；

2.西安電子科技大學(xué)計算機學(xué)院，陜西西安710071；

3.貴州大學(xué)理學(xué)院，貴州貴陽550025）

摘要：基于橢圓曲線上的雙線性對技術(shù)，構(gòu)造一種可驗證隱秘共享方案。該方案的信息率為2/3，與Pederson的方案(Crypto91)及相關(guān)方案相比，本方案在相同的安全級不下有較高的信息率，從而提高了隱秘共享協(xié)議的效率。并且，理論上證明該方案是信息論安全的。最終，將上述方案推廣到無可信中心的事情，設(shè)計了無可信中心的隱秘共享方案。經(jīng)分析表明，所提方案具有更高的安全性和有效性，能更好地滿腳應(yīng)用需求。

關(guān)鍵詞：隱秘共享；可驗證的隱秘共享；橢圓曲線離散對數(shù)；雙線性對；BDH假設(shè)

中圖分類號：TP309文獻(xiàn)標(biāo)識碼：B文章編號：1000-436X(2011)12-0096-07

Information-theoreticsecureverifiablesecret

sharingschemeonellipticcurvegroup

TIANYou-liang1,3,MAJian-feng2,PENGChang-gen3,CHENXi1

(1.SchoolofTelecommunicationsEngineering,XidianUniversity,Xi’an710071,China;2.SchoolofComputerScienceandTechnology,

XidianUniversity,Xi’an710071,China;3.CollegeofScience,GuizhouUniversity,Guiyang550025,China)Abstract:Basedonthebilinearpaironellipticcurves,averifiablesecretsharing(VSS)anddistributedverifiablesecretsharingwereconstructed.Theinformationrateoftheschemeis2/3.ComparedwithPederson’sscheme(Crypto91)andtherelatedschemes,theschemeismoreefficientunderthesamesecuritylevel.Atthesametime,thesecurityoftheschemewasprovedtheoretically.Theresultrevealsthattheschemeisinformation-theoreticsecurity.Finally,theVSShasbeenextensionstothecasewithoutadealer(orwithoutatrustedcenter).Adistributiveverifiablesecretsharingbasedonbilinearpairwasproposed.Analysisshowsthattheseschemesaremoresecureandeffectivethanothers,anditcanbemoreapplicableinspecialsituation.

Keywords:secretsharing;verifiablesecretsharing;ellipticcurvesdiscretelogarithm;bilinearpairing;Diffie-Hellmanassumption

1引言

在密碼體制中，能夠?qū)㈥P(guān)鍵操縱和權(quán)利分發(fā)給團體中的成員舉行治理，以分散加/解密、簽名和驗證權(quán)利。1979年，Shamir[1]和Blakley[2]分不基于Lagrange插值多項式和射影幾何理論提出門限隱秘共享方案，算是為了解決此類咨詢題。Stadler[3]提出在線隱秘共享機制，引入公告牌（NB）公布一些輔

收稿日期：2010-06-30；修回日期：2010-12-14

基金項目：國家科技部重大專項基金資助項目（2011ZX03005-002）；國家自然科學(xué)基金資助項目（60872041,61072066,60963023,60970143,61100230,61100233）；中央高?；究蒲袠I(yè)務(wù)費基金資助項目（JY10000903001,JY10000901034）FoundationItems:TheMajorNationalScienceandTechnologyProgram(2011ZX03005-002);TheNationalNaturalScienceFoun-dationofChina(60872041,61072066,60963023,60970143,61100230,61100233);TheFundamentalResearchFundsfortheCen-tralUniversities(JY10000903001,JY10000901034)

第12期田有亮等：橢圓曲線上的信息論安全的可驗證隱秘共享方案·97·

助信息。文獻(xiàn)[4,5]研究了將模運算用于隱秘共享，提出了基于中國剩余定理的隱秘共享方案。文獻(xiàn)[6]討論了多項式的運算與數(shù)的運算以及Lagrange插值多項式與中國剩余定理的相似性。近年來，研究人員要緊針對多隱秘共享、防欺騙等方面展開研究[7,8]。

為了解決在Shamir的隱秘共享方案中存在的2個咨詢題。1)莊家（隱秘的持有者）的老實性：若莊家將錯誤的子隱秘分發(fā)給部分或全部成員，各成員怎么驗證莊家發(fā)送來的子隱秘是正確的？2)成員的老實性：在恢復(fù)隱秘時期，若某些惡意的成員提供的是假的子隱秘，其他成員怎么鑒不？對這2個咨詢題的研究，就形成了可驗證的隱秘共享方案（簡記作VSS）。首次提出這種思想的是文獻(xiàn)[9]，而Feldman[10]的工作則使這種隱秘共享方案受到了眾多密碼研究者的重視。隨后，Pedersen[11,12]給出了更為簡潔、有用的方案。然而，不管在Shamir的普通隱秘共享方案中，依然在VSS方案中，都需要假設(shè)莊家和各成員之間有隱秘信道（privatechannel）,以便分發(fā)子秘鑰。在文獻(xiàn)[13~15]中，也對該咨詢題舉行了研究，但都存在諸多缺點：文獻(xiàn)[13]中需對每個共享隱秘作預(yù)計算，而且子隱秘的認(rèn)證需要各方在線合作，從而計算量和通信量都非常大；Harn提出的方案[14]，其安全性是基于離散對數(shù)的難解性，為了防止參與者之間的欺詐，需要執(zhí)行一具交互式驗證協(xié)議，計算量很大；Hwang和Chang[15]提出了一具多重隱秘共享方案，但該方案存在分發(fā)者計算量大，效率別高等缺點。

眾所周知，橢圓曲線密碼系統(tǒng)在密鑰長度、安全性等方面都比基于大整數(shù)分解和離散對數(shù)的密碼系統(tǒng)更具有優(yōu)勢。而橢圓曲線上的雙線性對是構(gòu)造加密、簽名等諸多密碼算法的重要工具，如：代數(shù)曲線上的WeilPairing和TateParing。在2000年，WeilPairing被用來構(gòu)造KeyAgreement[16]，這是KeyAgreement協(xié)議的一具突破；在2001年的密碼學(xué)會上，Boneh和Franklin利用橢圓曲線上的雙線性對設(shè)計了基于身份的加密方案[17]；同年的亞密會上，Boneh、Lynn和Shacham提出基于雙線性對的短簽名方案[18]；此后，許多基于BLS短簽名方案被提出。雙線性對技術(shù)成為構(gòu)造諸多密碼算法的重要工具，并且也促進(jìn)這些方面的蓬勃進(jìn)展。但是，基于雙線性對技術(shù)對隱秘共享舉行研究相對較少。最近，Shi等[19]基于橢圓曲線上的離散對數(shù)咨詢題提出了(t,n)門限可驗證多隱秘共享方案；Wang等[20]用雙線性對提出了動態(tài)可驗證多隱秘共享方案；田有亮等基于雙線性對技術(shù)研究了隱秘共享方案的可驗證性[21~23]和可公開驗證性[24]咨詢題，有效地將雙線性對技術(shù)引入到隱秘共享方案中以解決隱秘共享的可驗證性及可公開驗證性；他們提出用雙線性對的雙線性性質(zhì)解決隱秘共享的可驗證性咨詢題[25,26]。李慧賢等[23]利用雙線性對構(gòu)建可證明安全的隱秘共享方案的新辦法，基于公鑰密碼體制的語義安全的標(biāo)準(zhǔn)定義，提出了適合隱秘共享方案的語義安全定義，并提出了一具新的基于雙線性對的門限隱秘共享方案，對其正確性、安全性和性能舉行分析討論和證明。

可見，以雙線性對技術(shù)為工具深入研究隱秘共享方案，不管是在理論上，依然在實際應(yīng)用中都具有重要的價值和意義。本文針對上述提到的咨詢題，在田有亮等工作[25]的基礎(chǔ)上，從別同的角度，提出一種橢圓曲線上的信息論安全的可驗證隱秘共享方案及無可信中心的可驗證密碼共享方案。本文也間接提出了一種基于雙線性對的完備躲藏、完美綁定的知識答應(yīng)方案。隱秘共享方案在防止莊家及參與者之間的欺詐行為時，與文獻(xiàn)[25]一樣，別需要執(zhí)行復(fù)雜的交互式協(xié)議，僅經(jīng)過雙線性對的雙線性性質(zhì)就能夠?qū)崿F(xiàn)，幸免了以往非常多方案為了實現(xiàn)可驗證行而需要交互大量信及隱秘分發(fā)者計算量大的缺點。性能分析表明該方案具有較小的計算量和通信量，提高了隱秘共享方案的效率。

2預(yù)備知識

2.1雙線性對

定義1設(shè)

1

G、

2

G是2個相同素數(shù)階為q的加

法群和乘法群，q是一大素數(shù)。設(shè)P為

1

G的任一生

成元。aP記為a個P相加。假設(shè)在群

1

G和

2

G上的離散對數(shù)咨詢題（DLP）基本上困難的。映射112

:eGGG

×→滿腳如下性質(zhì)①~③被稱為密碼學(xué)上的雙線性映射。

①雙線性：對

1

,PQG

?∈和*

,,

q

abZ

∈(,)

eaPbQ=(,)ab

ePQ；或者對

1

,,

PQRG

?∈,(,)

ePQR

+=(,)(,)

ePReQR和(,)(,)(,)

ePQRePQePR

+=。

②非退化性：假如P是

1

G的生成元，則(,)

ePP

是

2

G的生成元，也即(,)1

ePP≠。

③可計算性：對

1

,PQG

?∈，都存在有效的算法來計算(,)

ePQ。

·98·通信學(xué)報第32卷

2.2Diffie-Hellman咨詢題

Diffie-Hellman咨詢題定義如下：思考加法群G=，

G的2個元素g1:=ag和g2:=bg，同時懂生成元g，但別懂a(chǎn)和b。咨詢題是：計算g3=(ab)g。有如下相關(guān)定義。

定義2設(shè)G是有限循環(huán)群，g是G的生成元。1)離散對數(shù)咨詢題(DLP)：給定(,)gag，對任意的*||

GaZ∈，求a。

2)計算性Diffie-Hellman咨詢題(CDHP)：給定

(,,)gagbg，對任意的*||,GabZ∈，計算()abg。3)判定性Diffie-Hellman咨詢題(DDHP)：給定(,,)gagbg，對任意的*||,GabZ∈，推斷()abgcg=是否成立。

在群G上，DDHP是易解的，即DDHP在多項式時刻內(nèi)可以被解決；而CDHP是難解的，即沒有任何也許的算法能夠解決CDHP。此刻稱群G為GDH群。

2.3雙線性Diffie-Hellman咨詢題

有許多密碼體制（如基于身份的加密體制、短簽名方案等）的安全性是基于雙線性對的相關(guān)Diffie-Hellman咨詢題的。雙線性Diffie-Hellman咨詢題首先是在文獻(xiàn)[17]中被提出的。思考G1是素數(shù)階的加法群，其階為q，同時P是它的生成元。設(shè)q階乘法群G2且它們之間存在雙線性映射e：G1×G1→G2，能被有效計算。

定義3雙線性Diffie-Hellman咨詢題(BDHP)描述如下：在12(,,)GGe中，給定(,,,)PaPbPcP，對任

意的*

,,RqabcZ∈,計算2(,)abcePPG∈。

算法Α在解決BDH咨詢題被稱為有優(yōu)勢ε，假如

Pr[(,,,)(,)]abcPaPbPcPePPεΑ=≥

其中，*

,,Rq

abcZ∈,1PG∈。

BDH假設(shè)可描述為：在求解BDH咨詢題上，沒

有概率多項式時刻算法有別可忽略的優(yōu)勢。

3可驗證密碼共享方案

3.1方案描述

假設(shè)有莊家D需在n個參與者1{,,}nUUU=L間共享隱秘S，僅當(dāng)t個或t個以上的參與者聯(lián)合起來才干恢復(fù)共享隱秘，少于t個參與者的任何組合都無法得到對于隱秘的任何信息。具體方案由4個子協(xié)議組成：系統(tǒng)初始化、隱秘分發(fā)協(xié)議、子密鑰的驗證協(xié)議和隱秘重構(gòu)協(xié)議。

系統(tǒng)初始化。G1是素數(shù)階的加法群（這個地方為橢圓曲線群），其階為q；P和Q是它的2個生成元，

且任何人都別懂*

q

Zn∈，滿腳nPQ=；設(shè)q階乘法群G2且它們之間存在雙線性映射e：

G1×G1→G2，能被有效計算；G1和G2上的離散對數(shù)（G1上是橢圓曲線離散對數(shù)）基本上難解的；隱秘1SG∈。隱秘分發(fā)協(xié)議。分發(fā)協(xié)議分為以下5步。1)莊家D發(fā)布隱秘S的答應(yīng)：C0=C(S,r)=e(S+

rQ,P),*

q

RZr∈?。2)莊家D選取G1[x]上的次數(shù)最多為1t?的秘

密多項式111()ttFxSFxFx??=+++L滿腳S=)0(F(這個地方11ttFx??表示在橢圓曲線群1G上1tx?個

1tF?相加)，并計算)(iFSi=，ni,,1L=。

3)莊家D隨機選取*

11,,q

RtZgg∈?L，并廣播Ci=C(Fi,gi)=e(Fi+giQP），1,,1?=tiL。

4)設(shè)111()ttgxrrxrx??=+++L，D計算=ir

)(ig，ni,,1L=。

5)莊家D隱秘發(fā)送),(iirS給iU,ni,,1L=。子密鑰的驗證協(xié)議。iU同意到),(iirS后，可經(jīng)過式（1）驗證子密鑰的正確性：

∏

?==

+10

),(tjijiij

CPQrSe(1)

隱秘重構(gòu)協(xié)議當(dāng)至少t個成員iU(iB∈且||Bt≥)提供他們各自的子密鑰),(iirS后，即可利用

Lagrange插值函數(shù)來計算出隱秘S和r：

(())(())BiiiB

BiiiBSLiSrLir∈∈?=??

=??

∑∑(2)其中，()BiLi為插值系數(shù)，\{}()j

BijBiij

xxLxxx∈?=

?∏

。

隨后可利用公開信息0C驗證),(iirS的正確性：

C0=e(S+rQ,P)。

3.2安全性與正確性分析

首先證明式(1)的正確性。

證明因為()iSFi=和)(igri=，因此有:),(PQrSeii+=),(),(PQrePSeii=((),)((),)eFiPegiQP

而)),((PiFe=111(,)tteSiFiFP??+++L

=111(,)(,)(,)tteSPeiFPeiFP??L=1

),(),(),(11??ti

tiPFePFePSeL

第12期田有亮等：橢圓曲線上的信息論安全的可驗證隱秘共享方案

·99·

同理，((),)egiQP=1

),(),(),(11??titiPQgePQgePrQeL因此((),)((),)eFiPegiQP

=1

),(),(),(1111???+++tittiPQgFePQgFePrQSeL0

1

1

011ttiiiCCC??=L=

∏

?=10

tjijj

C證畢。

下面分析方案的安全性。

引理1上述VSS方案中，對在1G上的多項式

()Fx的系數(shù)011,,,tFFF?L答應(yīng)011,,,tCCC?L是安全的?BDH假設(shè)成立。

證明?用反證法。假設(shè)上述方案中的答應(yīng)算法是安全的，但BDH假設(shè)別成立。則由BDH假設(shè)別成立知，存在算法A：關(guān)于1G中給定的,,,PaPbPcP

*(,,)Rq

abcZ∈，算法A能以成功率ε計算出

(,)abcePP。如今證明，利用算法A能夠破解上述承

諾算法。要破解上述答應(yīng)算法，只需從iC中計算出

iF即可。為此，隨機選取元素*

',',',,,qRZ∈γβαγβα，

然后分不將(PPPPγβα,,,)和(PPPP',',',γβα)作為輸入提供給算法A。由于該輸入是隨機的，故算法A將以成功率ε分不輸出αβγ),(PPe和'''),(γβαPPe。又由于iC=αβγ),(PPe'''),(γβαPPe，則((),)ePPαβγ

=iC/'''),(γβαPPe,從而可求出iF。這與答應(yīng)算法是安全的相矛盾。所以，若上述方案中的答應(yīng)算法是安全的，則BDH假設(shè)必定成立。

?同樣用反證法。假設(shè)BDH假設(shè)成立，但上

述方案中的答應(yīng)算法是別安全的。這么由答應(yīng)算法

別安全知，存在算法B：將任何1G中的隨機元素1321,,GQQQR∈作為算法B的輸入時，算法B能以

成功率ε計算出iF，滿腳：iC=),(PPrFeii+=

),(321QQQe+。若設(shè)PFiα=，irPPβ=，*,qZ∈βα和PQ11α=，PQ22α=，PQ33α=，*

321,,,qRZ∈ααα，

則算法B能以成功率ε計算出iF滿腳：),)((321PPeααα+=),)((PPeβα+。由此我們可得

321)(),(ααα+PPe=)(),(βα+PPe?1

321)()(),(?++βααααPPe

=),(PPe。令)(21αα+=a，3α=b，1)(?+=βαc，這就表明算法B關(guān)于1G中給定的(,,,PaPbPcP)，算法B能以成功率ε計算出(,)abcePP。這與假設(shè)矛盾！所以，若假設(shè)BDH假設(shè)成立，則上述方案中的答應(yīng)算法算是安全的。

綜上所述，方案中的答應(yīng)算法算是安全的?BDH假設(shè)成立。證畢。

引理2上述VSS方案中，若BDH假設(shè)成立，

則任何1t?個成員聯(lián)合都別能恢復(fù)隱秘S。

證明用反證法。假設(shè)1t?個成員聯(lián)合可以恢復(fù)隱秘S。別失普通性，假設(shè)這1t?個成員就記為：11,,tUU?L?，F(xiàn)要證明，對任給的,,PPPαβγ，攻擊者I利用這1t?個成員作為預(yù)言機（Oracle），就能

計算出(,)ePPαβγ。

別妨設(shè),,αβγ是隨機元素，否則，就用3個隨機元素'''*

,,RqZαβγ∈對,,PPPαβγ舉行

隨機化。

如今來為攻擊者I設(shè)置一具模擬的VSS系統(tǒng)，使得當(dāng)11,,tUU?L作為預(yù)言機時，就能夠計算出(,)ePPαβγ。模擬系統(tǒng)的設(shè)置分為以下5步。

1)攻擊者I置),(0PPPeCγβα+=；如此，0C的設(shè)置就隱含地確定了PFαγ=)0(和PQgβγ=)0(。

2)隨機選取1t?組值：))1(),1((gF，L，

))1(),1((??tgtF*

1qRZG×∈；加上前面確定了的

)0(F和)0(g，如此就固定了函數(shù))(xF和)(xg。

3)I計算前1t?個),(PQrSeii+1,,1?=tiL的值。

4)由于(0)F和)0(g是隱含在0C中的，故I沒法計算))(),((tgtF,L,))(),((ngnF的值；然而，I可利用Lagrange插值公式計算出余下的),(PQrSeii+),,(ntiL=。

5)計算(1,2,,1)iCit=?L。由于)(xF=S1

1tiiixF?=+∑和∑

?=+=11

)(tiiixgrxg，故可得如下方程

組：

1

1

11

11

100111111111111(1)(1)1111(,)(,)(,)((0)(0),)(,)(,)(,)((1)(1),)

(,)(,)(,)((1)(1),)

ttttttttttteSrQPeFgQPeFgQPeFgQPeSrQPeFgQPeFgQPeFgQPeSrQPeFgQPeFgQPeFtgtQP????????????+++?

=+??+++??=+??

?

+++=?+??LLLL??

?在上述方程組中，敵手I只懂))1(),1((gF，L，

))1(),1((??tgtF的值，別懂))0(),0((gF的值。所以，I別能解出11,,,?tFFSL和11,,,?tggrL的值。但是I懂0C，故I利用0C和方程組就能夠計算出(1,,1)jCjt=?L。

如此，一具模擬的VSS系統(tǒng)就設(shè)置完成了。當(dāng)攻擊者I將這一系統(tǒng)的相關(guān)信息提供給這1t?個成員11,,tUU?L時，他們的個人觀看（privateview）

·100·通信學(xué)報第32卷

是相互一致的。這么依照假設(shè)，這1t?個成員11,,tUU?L就能夠計算出隱秘(0)F滿腳：(,)ePPPαβγ+((0)(0),)eFgQP=+?αβγ),(PPe=1(((0)eFβ?+1

(0)),)(,)gQPePPγ?。由于系統(tǒng)中的雙線性對是能

被有效計算的，這就表明這1t?個成員能求解BDH咨詢題。這與BDH假設(shè)成立相矛盾，從而命題成立。證畢。

利用引理1和定理2，有如下定理。定理3VSS方案是信息論安全的，也算是講，任何t個成員聯(lián)合都能夠重構(gòu)莊家分發(fā)的隱秘S，而任何1t?個成員構(gòu)成的子集都別能得到該隱秘的任何信息。

證明

設(shè)任意的},,{1nUUBL?，且1||?=tB。

B的觀看Bview01(,,;(,))tiiiB

CCST?∈L，則命題需證明：]|Pr[BiviewSgetsU=]Pr[SgetsUi<ε，BUi∈?。

依照引理1懂，對任意的1GSR∈，若

*

qRZr∈是隨機、均勻選取的，則),(rSC=

),(PrQSe+均勻分布于2G中。若BDH假設(shè)成立，則

莊家D別能用2種方式打開),(rSC。由于),(rSC具有良好的隨機性，故有]|secPr[BviewSrethasD=

]secPr[SrethasD。

由引理2有，若BDH假設(shè)成立，關(guān)于BUi∈?，

]Pr[SgetsUi=]|Pr[BiviewSgetsU=

||||2GC=

q

1

；另

一方面，關(guān)于BUi∈?，]Pr[SgetsUi=|||

|1GS=

q

1。

所以，]Pr[SgetsUi=]|Pr[BiviewSgetsU=

q1

。

從而命題得證。3.3信息率

本節(jié)要緊思考方案的信息率(informationrate)。

在本文方案中，其共享隱秘1GS∈，

因此||2||qS=；方案中其共享子密鑰為),(iirS，而1GSi∈，*

qiZr∈。

所以，|||||),(|iiiirSrS+==||3q。依照信息率的定義知，其信息率為

share

ofsizeretofsizesec=

|||||

|iirSS+=||3||2qq=3

2

文獻(xiàn)[11]和文獻(xiàn)[24]中方案的信息率基本上1/2；

文獻(xiàn)[23]中方案的信息率是1/5；而本文方案的信息率為2/3?？梢?，在相同安全等級下（基本上信息論安全的），本文方案有較高的信息率。3.4性能分析

本節(jié)經(jīng)過與現(xiàn)有方案舉行比較來簡單分析本文方案的性能。為了便于與現(xiàn)有方案的比較，要緊選取基于離散對數(shù)咨詢題及其相應(yīng)困難性假設(shè)的隱秘共享方案舉行類比。例如，基于離散對數(shù)咨詢題(DLP)的方案選取文獻(xiàn)[14]為代表，基于橢圓曲線離散對數(shù)咨詢題(ECDLP)及相應(yīng)假設(shè)的選取文獻(xiàn)[22]和文獻(xiàn)[24]為代表。這個地方，要緊思考方案的計算、通信等方面性能比較。眾所周知，基于DLP的方案，其最為耗時的運就是冪模運算，用pT表示；基于

ECDLP的方案，其最為耗時的運就是點乘運算，用

aT表示；基于雙線性對技術(shù)的方案，最耗時的運算包括：群1G(設(shè)其為有限域上的橢圓曲線群)上的點乘運算(aT)、群2G(設(shè)其為有限域)上的冪模運算(pT)及之間的對運算(記為eT)；

其他計算開銷忽略別計。下面，經(jīng)過表1將本文方案與這些方案做一簡單比較。

經(jīng)過表1做如下兩方面的分析比較。

1)計算量方面。在系統(tǒng)建立過程中，本文方案的莊家D別需要為各位參與者計算相應(yīng)的密鑰，此刻的計算開銷能夠別加思考。而文獻(xiàn)[14]、文獻(xiàn)[22]和文獻(xiàn)[24]中均需為各參與者計算相應(yīng)的密鑰，這是本方案在計算上占優(yōu)的一具方面。在隱秘分發(fā)時期(因文獻(xiàn)[14]是一具多隱秘共享方案，為了與本方案具有可比性，表1中僅列出該方案共享子密鑰(())iSFi=及公開信息iC(0,,1)it=?L，所共享單個隱秘計算量及通信量等)，莊家D需要為每一位參與者計需要的群1G上的點乘運算次數(shù)及雙線性對計算次數(shù)分不為)1(+nt和t2次；從表1能夠看出

表1

本文方案與現(xiàn)有方案的性能比較

方案

可驗證性

計算量

通信量分發(fā)時期

子隱秘驗證

重構(gòu)時期分發(fā)時期

子隱秘驗證

重構(gòu)時期文獻(xiàn)[14]的方案Yes3nTp2nTp

2tTp

3n|q|2n|q|

t|q|文獻(xiàn)[21]的方案Yes(3n+t)Ta

tTp+Ta+(t+1)Te3tTa+2tTe(3n+1)|q|0

t|q|

文獻(xiàn)[23]的方案No(2n+1)Ta+Te/2tTe(n+2)|q|/4t|q|

本文方案

Yes

t(n+1)Ta+2tTe

Te+Ta+tTp

tTa(3n+3)|q|03t|q|

第12期田有亮等：橢圓曲線上的信息論安全的可驗證隱秘共享方案·101·

本文方案在這方面沒有明顯優(yōu)勢。在子隱秘驗證時期，共需要n次對運算、n次點乘運算和群2G上tn次指數(shù)運算，本文方案僅與文獻(xiàn)[24]中的方案有明顯優(yōu)勢。在隱秘重構(gòu)時期，計算代價能夠表示成群1G上t次點乘運算?？梢?，本文方案在這方面有明顯的計算優(yōu)勢。雖然這樣，但能夠發(fā)覺，本文方案的要緊運算開銷與參與者數(shù)目成線性關(guān)系；而且在隱秘分發(fā)時期有點計算能夠作預(yù)處理，如此能夠大大提高隱秘分發(fā)的效率。

2)通信量方面。本文方案在莊家分發(fā)子密鑰時，需要點對點通信。分發(fā)公開信息能夠采取廣播方式。在隱秘重構(gòu)時，亦需要點對點的單播通信。所以總通信次數(shù)為1nt++。本文方案的通信次數(shù)遠(yuǎn)遠(yuǎn)低于文獻(xiàn)[14]中方案的通信次數(shù)，要緊在子隱秘驗證通信方面具有很大的優(yōu)勢；與文獻(xiàn)[22]和文獻(xiàn)[24]中方案通信次數(shù)相同(但在子隱秘驗證的計算開銷方面本文方案有較大的優(yōu)勢)。從表1能夠看出，在總體通信開銷上本文方案具有很明顯的優(yōu)勢。

綜合以上兩方面的分析表明，本文方案具有相對較小的計算開銷及通信開銷，具有更好的實際應(yīng)用價值。并且，方案具有線性性質(zhì)，非常容易推廣到無可信中心(無莊家)的事情，第4節(jié)的無可信中心的隱秘共享方案也具有這些優(yōu)點。

4無可信中心的隱秘共享方案

不管在普通的隱秘共享，依然在可驗證的隱秘

共享方案中，都需要有一具莊家D（或者叫可信第三方：TTP）來分發(fā)隱秘。普通假設(shè)莊家D是老實的同時各參與者都信任D。然而，在現(xiàn)實中非常難找到如此的一具可信中心；這就成為了隱秘共享方案進(jìn)展中的一具瓶頸。本節(jié)將上節(jié)的方案推廣到無可信第三方的事情。

為了方便，記上節(jié)的隱秘共享方案為：)))(),(();,(,);,((xgxFrSCrSBDHVSSiii，其中，S：共享隱秘，r：隨機數(shù)；iC：公共信息；),(iirS：iU的分享子密鑰；))(),((xgxF：莊家D選取的兩隨機函數(shù)。顯然，本文方案是線性的，所以有如下結(jié)論。

定理2給定2個執(zhí)行實例：Instance1：)))(),(();,(,);,((xgxFrSCrSBDHVSSiii和Instance2：)))('),('();','(,');','((xgxFrSCrSBDHVSSiii?一具執(zhí)行實例Instance3：((',BDHVSSSS+

');',iirrCC+(',');('()'(),()iiiiSSrrFxFxgx++++

'()))gx。

證明因隱秘共享方案具有線性性質(zhì)，因此該定理顯然成立。

下面設(shè)計無可信中心的可驗證隱秘共享方案。假設(shè)隱秘1SG∈要在n個成員間共享。所有假設(shè)同上節(jié)，則其無可信中心的隱秘共享方案如下。

方案包括3步：隱秘的分發(fā)、計算子密鑰和隱秘的重構(gòu)。

隱秘的分發(fā)。成員iU),,1(niL=執(zhí)行協(xié)議：

)))(),(();,(,);,((xgxFrSCrSBDHVSSiiijijijii

計算子密鑰。所有的成員成功分發(fā)了他們的子密鑰后，參與者),,1(niL=iU經(jīng)過下式計算他的共享份額),(iirS：

∑

==

njjiiSS1

，∑

==

n

jji

irr1

隱秘的重構(gòu)。當(dāng)至少t個成員iU(iB∈且||Bt≥)提供他們各自的子密鑰),(iirS后，即可利用

Lagrange插值函數(shù)來計算出隱秘(S,r)。

記上述無可信中心的可驗證隱秘共享方案為：

)))(),(();,(,);,((xgxFrSCrSNDVSSiiijijijii。非常容易得到如下定理。

定理3設(shè)

S

1n

i

iS=∑

，

r

1n

i

ir=∑

；

i

C1n

ji

jC=∏

；i

S1n

ji

jS=∑

,

ir1n

ji

jr=∑

；()

Fx

1()n

j

jFx=∑

,(

)gx1

()n

jjgx=∑

；這么有：

)))(),(();,(,);,((xgxFrSCrSNDVSSiiijijijii?

)))(),(();,(,);,((xgxFrSCrSBDHVSSiii

證明該結(jié)論是定理2的自然推廣，證明略。

5結(jié)束語

橢圓曲線上的雙線性對是構(gòu)造諸多密碼算法的重要工具。本文基于該技術(shù)研究可驗證隱秘共享方案，構(gòu)造了通信效率高、安全性更好的可驗證及無可信中心的可驗證隱秘共享方案。利用雙線性對的雙線性性質(zhì)，提高了方案中子隱秘驗證的有效性。再者，經(jīng)過對方案的有效性和安全行分析顯示，所提方案均滿腳可驗證隱秘共享方案的特性，并且在BDH困難性假設(shè)下本文方案是信息論安全的。與已有方案的對照顯示，所提方案具有較小的計算開銷和通信開銷，并提高了信息率。

·102·通信學(xué)報第32卷

田有亮（1982-），男，貴州盤縣人，

西安電子科技大學(xué)博士生，要緊研究方向為博弈論、安全協(xié)議分析等。

參考文獻(xiàn)：

[1]SHAMIRA.Howtoshareasecret[J].CommunicationsoftheACM,

1979,22(11):612-613.

[2]BLAKLEYG.Safeguardingcryptographickeys[A].Proceedingsof

theNationalComputerConference[C].AFIPS,1979.313-317.[3]STADLERM.Publiclyverifiablesecretsharing[A].Cryptology-

EUROCRYPT’96[C].Berlin,1996.190-199.

[4]ASMUTHC,BLOOMJ.Amodularapproachtokeysafeguarding[J].

IEEETransonInformationTheory,1983,29(2):208-210.

[5]HWANGRJ,CHANGCC.Animprovedthresholdschemebasedon

modulararithmetic[J].JournalofInformationScienceandEngineering,1999,15(5):691-699.

[6]AHO,ULLMANJ.TheDesignandAnalysisofComputerAlgo-rithms[R].Reading,MA:Addison-Wesley,1974.

[7]CHANCW,CHANGCC.Aschemeforthresholdmulti-secretshar-ing[J].AppliedMathematicsandComputation,2005,166(1):1-14.[8]CHANGTY,HWANGMS,etal.AnimprovementontheLinWu(t,

n)thresholdverifiablemulti-secretsharingscheme[J].AppliedMa-thematicsandComputation,2005,163(1):169-178.

[9]CHORB,DOLDWASSERS,MICALIS,etal.Verifiablesecret

sharingandachievingsimultaneityinthepresenceoffaults[A].Proc26thIEEESymposiumonFoundationsofComputerSciences(FOCS'85)[C].LosAngeles,1985.383-395.

[10]FELDMANP.Apracticalschemefornon-interactiveverifiablesecret

sharing[A].Proc28thIEEESymposiumonFoundationsofComputerScience(FOCS’87)[C].1987.427-437.

[11]PEDERSONTP.Non-interactiveandinformation-theoreticsecure

verifiablesecretsharing[A].Cryptology-CRYPTO’91[C].Berlin:Springer-Verlag,1992.129-140.

[12]PEDERSONTP.DistributedProversandVerifiableSecretSharing

BasedontheDiscreteLogarithmProblem[D].Aarhus,DeXXXark:AarhusUniversity,ComputerScienceDepartment,1992.

[13]MTOPAH.Howtoshareasecretwithcheaters[J].JournalofCryp-tology,1988,1(2):133-138.

[14]HARML.Efficientsharing(broadcasting)ofmultiplesecrets[J].IEEE

ProcComputDigitalTech,1995,142(3):237-240.

[15]HWANGRJ,CHANGCC.Anon-linesecretsharingschemefor

multi-secrets[J].ComputerCommunications,1998,21(13):1170-1176.

[16]JOUX.AoneroundprotocolfortripartiteDiffie-Hellman[A].Pro-ceedingsofANTS4[C].2000.385-394.

[17]BONEHD,FRANKLINM.IdentitybasedencryptionfromtheWeil

pairing[A].ExtendedAbstractinCrypto2001[C].2001.XXX-615.[18]BONEHD,LYNNB,SHACHAMH.ShortsignaturesfromtheWeil

pairing[A].JournalofCryptology,2004,17:297-319.

[19]SHIRH,ZHONGH,HUANGLS.A(t,n)-thresholdverifiedmul-ti-secretsharingscheme