橢圓曲線(xiàn)上的信息論安全的可驗(yàn)證隱秘共享方案

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

田有亮1,3，馬建峰2，彭長(zhǎng)根3，陳曦1

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

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

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

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

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

中圖分類(lèi)號(hào)：TP309文獻(xiàn)標(biāo)識(shí)碼：B文章編號(hào)：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ā)給團(tuán)體中的成員舉行治理，以分散加/解密、簽名和驗(yàn)證權(quán)利。1979年，Shamir[1]和Blakley[2]分不基于Lagrange插值多項(xiàng)式和射影幾何理論提出門(mén)限隱秘共享方案，算是為了解決此類(lèi)咨詢(xún)題。Stadler[3]提出在線(xiàn)隱秘共享機(jī)制，引入公告牌（NB）公布一些輔

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

基金項(xiàng)目：國(guó)家科技部重大專(zhuān)項(xiàng)基金資助項(xiàng)目（2011ZX03005-002）；國(guó)家自然科學(xué)基金資助項(xiàng)目（60872041,61072066,60963023,60970143,61100230,61100233）；中央高校基本科研業(yè)務(wù)費(fèi)基金資助項(xiàng)目（JY10000903001,JY10000901034）FoundationItems:TheMajorNationalScienceandTechnologyProgram(2011ZX03005-002);TheNationalNaturalScienceFoun-dationofChina(60872041,61072066,60963023,60970143,61100230,61100233);TheFundamentalResearchFundsfortheCen-tralUniversities(JY10000903001,JY10000901034)

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

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

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

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

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

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

2.1雙線(xiàn)性對(duì)

定義1設(shè)

1

G、

2

G是2個(gè)相同素?cái)?shù)階為q的加

法群和乘法群，q是一大素?cái)?shù)。設(shè)P為

1

G的任一生

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

1

G和

2

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

:eGGG

×→滿(mǎn)腳如下性質(zhì)①~③被稱(chēng)為密碼學(xué)上的雙線(xiàn)性映射。

①雙線(xiàn)性：對(duì)

1

,PQG

?∈和*

,,

q

abZ

∈(,)

eaPbQ=(,)ab

ePQ；或者對(duì)

1

,,

PQRG

?∈,(,)

ePQR

+=(,)(,)

ePReQR和(,)(,)(,)

ePQRePQePR

+=。

②非退化性：假如P是

1

G的生成元，則(,)

ePP

是

2

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

ePP≠。

③可計(jì)算性：對(duì)

1

,PQG

?∈，都存在有效的算法來(lái)計(jì)算(,)

ePQ。

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

2.2Diffie-Hellman咨詢(xún)題

Diffie-Hellman咨詢(xún)題定義如下：思考加法群G=，

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

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

GaZ∈，求a。

2)計(jì)算性Diffie-Hellman咨詢(xún)題(CDHP)：給定

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

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

2.3雙線(xiàn)性Diffie-Hellman咨詢(xún)題

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

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

意的*

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

算法Α在解決BDH咨詢(xún)題被稱(chēng)為有優(yōu)勢(shì)ε，假如

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

其中，*

,,Rq

abcZ∈,1PG∈。

BDH假設(shè)可描述為：在求解BDH咨詢(xún)題上，沒(méi)

有概率多項(xiàng)式時(shí)刻算法有別可忽略的優(yōu)勢(shì)。

3可驗(yàn)證密碼共享方案

3.1方案描述

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

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

且任何人都別懂*

q

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

G1×G1→G2，能被有效計(jì)算；G1和G2上的離散對(duì)數(shù)（G1上是橢圓曲線(xiàn)離散對(duì)數(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?的秘

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

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

3)莊家D隨機(jī)選取*

11,,q

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

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

)(ig，ni,,1L=。

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

∏

?==

+10

),(tjijiij

CPQrSe(1)

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

Lagrange插值函數(shù)來(lái)計(jì)算出隱秘S和r：

(())(())BiiiB

BiiiBSLiSrLir∈∈?=??

=??

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

BijBiij

xxLxxx∈?=

?∏

。

隨后可利用公開(kāi)信息0C驗(yàn)證),(iirS的正確性：

C0=e(S+rQ,P)。

3.2安全性與正確性分析

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

證明因?yàn)?)iSFi=和)(igri=，因此有:),(PQrSeii+=),(),(PQrePSeii=((),)((),)eFiPegiQP

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

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

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

tiPFePFePSeL

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

·99·

同理，((),)egiQP=1

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

=1

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

1

1

011ttiiiCCC??=L=

∏

?=10

tjijj

C證畢。

下面分析方案的安全性。

引理1上述VSS方案中，對(duì)在1G上的多項(xiàng)式

()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能以成功率ε計(jì)算出

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

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

iF即可。為此，隨機(jī)選取元素*

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

然后分不將(PPPPγβα,,,)和(PPPP',',',γβα)作為輸入提供給算法A。由于該輸入是隨機(jī)的，故算法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中的隨機(jī)元素1321,,GQQQR∈作為算法B的輸入時(shí)，算法B能以

成功率ε計(jì)算出iF，滿(mǎn)腳：iC=),(PPrFeii+=

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

321,,,qRZ∈ααα，

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

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

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

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

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

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

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

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

計(jì)算出(,)ePPαβγ。

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

,,RqZαβγ∈對(duì),,PPPαβγ舉行

隨機(jī)化。

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

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

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

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

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

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

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

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

5)計(jì)算(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和方程組就能夠計(jì)算出(1,,1)jCjt=?L。

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

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

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

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

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

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

證明

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

B的觀(guān)看Bview01(,,;(,))tiiiB

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

依照引理1懂，對(duì)任意的1GSR∈，若

*

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

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

莊家D別能用2種方式打開(kāi)),(rSC。由于),(rSC具有良好的隨機(jī)性，故有]|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?？梢?jiàn)，在相同安全等級(jí)下（基本上信息論安全的），本文方案有較高的信息率。3.4性能分析

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

ECDLP的方案，其最為耗時(shí)的運(yùn)就是點(diǎn)乘運(yùn)算，用

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

其他計(jì)算開(kāi)銷(xiāo)忽略別計(jì)。下面，經(jīng)過(guò)表1將本文方案與這些方案做一簡(jiǎn)單比較。

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

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

表1

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

方案

可驗(yàn)證性

計(jì)算量

通信量分發(fā)時(shí)期

子隱秘驗(yàn)證

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

子隱秘驗(yàn)證

重構(gòu)時(shí)期文獻(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期田有亮等：橢圓曲線(xiàn)上的信息論安全的可驗(yàn)證隱秘共享方案·101·

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

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

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

4無(wú)可信中心的隱秘共享方案

不管在普通的隱秘共享，依然在可驗(yàn)證的隱秘

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

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

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

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

'()))gx。

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

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

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

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

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

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

∑

==

njjiiSS1

，∑

==

n

jji

irr1

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

Lagrange插值函數(shù)來(lái)計(jì)算出隱秘(S,r)。

記上述無(wú)可信中心的可驗(yàn)證隱秘共享方案為：

)))(),(();,(,);,((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é)束語(yǔ)

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

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

田有亮（1982-），男，貴州盤(pán)縣人，

西安電子科技大學(xué)博士生，要緊研究方向?yàn)椴┺恼摗踩珔f(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