基于單向散列鏈的可更新(t,n)門限秘密共享方案

李大偉，楊庚

（南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京210003）

1 引言

秘密共享方案是分布式安全協(xié)議的重要組成部分。典型的秘密共享方案是 Shamir(1979)提出的基于拉格朗日插值的秘密共享方案。其基本思想是通過秘密多項(xiàng)式將共享秘密S分成n份影子秘密分發(fā)給不同的參與者，當(dāng)且僅當(dāng)多于門限數(shù)量t個(gè)參與者合作才能重構(gòu)共享的秘密。

隨著研究的深入，秘密共享技術(shù)在安全多方計(jì)算、密鑰管理、電子商務(wù)以及群組密碼算法設(shè)計(jì)等方面均得到了廣泛的應(yīng)用[1]。在實(shí)際應(yīng)用中，共享秘密往往具有較長(zhǎng)的生命周期。通常情況下，攻擊者攻破合法節(jié)點(diǎn)的數(shù)量隨攻擊時(shí)間的延長(zhǎng)而增加，因此，當(dāng)秘密共享方案運(yùn)行足夠長(zhǎng)的時(shí)間后，攻擊者有較大的概率獲得足夠多的影子秘密重建共享秘密，系統(tǒng)安全性將受到威脅。

上述問題的一種簡(jiǎn)單解決思路是定期更新共享秘密，然而有些共享秘密如系統(tǒng)主密鑰、數(shù)據(jù)文件等更新代價(jià)較大。另一種思路是將共享秘密的生存周期分割為若干子周期，在每個(gè)子周期內(nèi)重新執(zhí)行秘密共享協(xié)議，其缺點(diǎn)是帶來了較高的計(jì)算和通信開銷。針對(duì)這個(gè)問題，Herzberg等[2]首先提出了可更新秘密共享，又稱前攝秘密共享（PSS,proactive secret sharing）的概念，在不改變共享秘密的前提下定期更新參與者持有的影子秘密，防止移動(dòng)攻擊者在整個(gè)密鑰生存周期內(nèi)竊取共享秘密。此后許多學(xué)者對(duì)PSS方案研究進(jìn)行了一系列有益的探索[3～5]。

目前已有方案多側(cè)重影子秘密更新的正確性以及防欺詐、防合謀等功能特性，而忽略更新過程中計(jì)算、存儲(chǔ)等性能需求，限制了其應(yīng)用范圍。因此，構(gòu)造一種安全高效的PSS方案是一個(gè)有意義的研究方向。單向散列鏈具有良好的計(jì)算性能和認(rèn)證性能，被廣泛應(yīng)用于各類安全協(xié)議中。本文將單向散列鏈引入PSS方案中，結(jié)合IBE公鑰算法提出了一種高效的可更新秘密共享方案。

本文組織結(jié)構(gòu)如下：第2節(jié)介紹相關(guān)研究工作；第3節(jié)介紹預(yù)備知識(shí)；第4節(jié)對(duì)所提方案進(jìn)行描述；第5節(jié)對(duì)方案的安全性和有效性進(jìn)行分析和仿真；第6節(jié)是結(jié)束語。

2 相關(guān)工作

可更新的秘密共享方案自 Herzberg等提出后逐漸成為一個(gè)熱門的研究課題。Herzberg方案由可信分發(fā)者將 n個(gè)初始影子秘密分給不同參與者{P1,…,Pn}，通過更新影子秘密。該方案更新過程由參與者自動(dòng)完成，具有的計(jì)算復(fù)雜度和 O(n2+nt)的通信開銷。在Herzberg方案基礎(chǔ)上，國(guó)內(nèi)學(xué)者許春香等[6]基于離散對(duì)數(shù)問題(DLP)難解性，提出了一個(gè)防欺詐的 PSS方案。方案由可信第三方根據(jù)執(zhí)行更新，其優(yōu)點(diǎn)是具有良好的可驗(yàn)證性，但是使用較多指數(shù)操作降低了執(zhí)行效率，且集中式更新方式容易造成單點(diǎn)失敗。為了提高方案的靈活性，Wang等[7]提出了一個(gè)參數(shù)可調(diào)整的PSS方案，其更新機(jī)制是將前一周期的影子秘密與一個(gè)由k個(gè)節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)相加得到新影子秘密。其缺點(diǎn)是更新時(shí)需選取k個(gè)節(jié)點(diǎn)作為更新服務(wù)器，造成了較多的存儲(chǔ)需求和通信開銷，每個(gè)周期內(nèi)發(fā)送的交互信息量為2(k2+kn)。還有學(xué)者探討了基于公鑰密碼體制的PSS方案，如Sun等[8]提出的基于橢圓曲線密碼學(xué)的方案，Zhang等[9]提出的基于RSA數(shù)字簽名的方案。

針對(duì)多秘密共享的情況，Li等[10]提出的方案中參與者在每個(gè)周期開始執(zhí)行交互式更新協(xié)議。該方案使用廣播信道同步更新參數(shù)，利用可驗(yàn)證秘密共享技術(shù)防止參與者欺騙，其缺點(diǎn)是具有較大的通信開銷。針對(duì)更新同步問題，Zhou等[11]研究了異步系統(tǒng)的 PSS方案。Asaeda等[12]主要從更新一致性的角度研究PSS方案，提出了一個(gè)使用令牌機(jī)制的同步更新方案，具有良好的可控性。參與者j通過計(jì)算更新所持有的影子秘密，具有O(n)的計(jì)算復(fù)雜度，但是管理令牌帶來了額外的系統(tǒng)開銷。

PSS方案的假設(shè)前提是攻擊者在短時(shí)間內(nèi)竊取的影子秘密數(shù)量是有限的。若秘密共享門限為 t，攻擊者在一個(gè)周期內(nèi)攻破的合法節(jié)點(diǎn)數(shù)量小于 t，系統(tǒng)就是安全的。同時(shí)，攻擊者在周期T獲取的影子秘密在之后的周期T+i(i=1,2,…)中不再有效，因而在每個(gè)周期內(nèi)都要面臨攻破(t，n)門限秘密共享方案的難度。現(xiàn)有方案中，解決影子秘密更新的思路是在每次更新時(shí)更新服務(wù)器(可以是秘密分發(fā)者)重新生成一個(gè)秘密多項(xiàng)式，而更新時(shí)生成秘密多項(xiàng)式的復(fù)雜度等同于重新進(jìn)行秘密分發(fā)，代價(jià)較大。針對(duì)此問題，本文基于單向散列函數(shù)的安全特性，在影子秘密更新時(shí)簡(jiǎn)化秘密多項(xiàng)式結(jié)構(gòu)，同時(shí)使用基于IBE的門限秘密共享算法實(shí)現(xiàn)了一個(gè)可更新的秘密共享方案，并分析了方案的安全性和有效性。

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

3.1 單向散列鏈

單向散列鏈的概念最早由Lamport(1981)[13]提出，最初用來保護(hù)一次性口令避免竊聽和重放攻擊。散列鏈有類似公鑰密碼的性質(zhì)和很高的計(jì)算效率，被廣泛應(yīng)用于多種安全系統(tǒng)中。單向散列鏈的基礎(chǔ)是單向散列函數(shù)。單向散列函數(shù) H :{0,1}*?{0,1}k可以將任意長(zhǎng)度的消息M映射成固定長(zhǎng)度的散列值。單向散列函數(shù)具有下列特性：

1) 給定M，容易計(jì)算H(M)；

2) 給定H(M)，求M在計(jì)算上是不可行的；

3) 給定 H(M)，尋找另一消息 M≠M(fèi) '，滿足H(M)=H(M ')在計(jì)算上是不可行的。

定義1 （單向散列鏈）設(shè)單向散列函數(shù)為H，隨機(jī)選取種子 α∈，通過遞歸散列運(yùn)算得到一系列散列值 α,H(α) ,H2(α) ,…,HN(α)稱為單向散列鏈。其中HN(α)稱作散列鏈的根。單向散列鏈具有以下性質(zhì):

1) 不知道α的情況下，獲得HN(α)，無法得到 HN-1(α)；

2) 使用HN(α)容易驗(yàn)證HN-1(α)。

3.2 IBE公鑰算法基礎(chǔ)

IBE公鑰加密算法的安全性建立在CDH困難問題的變形BDH問題之上[14]。記Zq為素?cái)?shù)階q的群，G為加法群，F(xiàn)為乘法群。

定義2 （雙線性映射）對(duì)?x、y、z∈G；a、b∈Z映射e?: G×G→F稱為雙線性映射，滿足：

1)雙線性： e?(a x,b y)=e?(x,y)ab；

2)非退化性：?P、Q∈G，滿足e?(P,Q)≠1；

3)可計(jì)算性：存在多項(xiàng)式時(shí)間算法計(jì)算e?。

IBE算法由 4個(gè)函數(shù) Setup、Extract、Encrypt和Decrypt組成，分別完成系統(tǒng)參數(shù)建立、密鑰提取、加密和解密功能。若s為主密鑰，Ppub為系統(tǒng)公鑰，H1、H2為單向散列函數(shù)，M 為明文，身份ID對(duì)應(yīng)的公私鑰分別為 QID=H1(I D),DID=sQID。

解密：M=V ⊕ H2(e?(DID,U ))。

(7)經(jīng)濟(jì)性原則。電網(wǎng)運(yùn)營(yíng)在線監(jiān)測(cè)系統(tǒng)的架構(gòu)設(shè)計(jì)應(yīng)滿足經(jīng)濟(jì)性要求，充分利用現(xiàn)有技術(shù)手段，通過電力企業(yè)一體化信息平臺(tái)整合各類信息系統(tǒng)資源，進(jìn)行綜合利用與再開發(fā)，有效節(jié)約投資成本。

4 方案描述

基于IBE公鑰算法和單向散列鏈，本節(jié)給出子秘密可更新的秘密共享方案。方案由秘密分發(fā)者D(兼有IBE算法中PKG功能)，參與者集合P={P1，P2，…，Pn}組成。設(shè)C為以特定ID為參數(shù)的IBE算法所產(chǎn)生的密文。秘密分發(fā)者通過(t，n)門限方法將IBE私鑰DID作為共享秘密分發(fā)給P中參與者。P中任意成員數(shù)大于t的子集可以重構(gòu)共享的DID，進(jìn)而具有解密密文C的能力。秘密分發(fā)者D同時(shí)維護(hù)一條單向散列鏈L，每個(gè)運(yùn)行周期分發(fā)者D通過私有信道發(fā)送更新參數(shù)給參與者Pi，Pi更新所持有的影子秘密Si。假設(shè)系統(tǒng)具有全局同步時(shí)鐘，將秘密生存周期分為若干更新周期。

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

給定一個(gè)安全參數(shù) k，選擇大素?cái)?shù)p(kbit)，選擇g∈，找一條滿足 CDH安全假設(shè)的超奇異橢圓曲線 E/GF(p)，生成 E/GF(p)上的 q(q ＞ 2k)階子群(G,+)和其生成元 P，雙線性映射e?: G×G?GF(P2)*。設(shè)l為明文長(zhǎng)度。單向散列函數(shù)H1、H2、H3定義為

H1:{0,1}*?G*;

H2,H3:GF(P2)*?{0,1}l;

H3:G*? G*。

4.2 秘密分發(fā)階段

秘密分發(fā)過程由可信的秘密分發(fā)者D完成。秘密分發(fā)者執(zhí)行Extract算法生成特定ID對(duì)應(yīng)的公私鑰對(duì) QID=H1(I D)和 DID=sQID。將DID作為共享秘密分發(fā)給參與者集合P中成員。

step1 隨 機(jī) 選 擇{ai|ai∈ G*;i=1,2,…,t-1;at-1≠ 0}構(gòu)造t-1階多項(xiàng)式

step3 計(jì)算驗(yàn)證密鑰 Uj=gaj(0≤j≤t-1)，其中 U=gDID；

0

參與者Pi收到影子秘密后，驗(yàn)證

4.3 子秘密更新階段

系統(tǒng)將共享秘密生存周期劃分為若干個(gè)子秘密更新周期(長(zhǎng)度為 T)。當(dāng)每個(gè)更新周期開始或多個(gè)參與者受到惡意攻擊后，激活子秘密更新算法。在區(qū)間[Γi-1,Γi]中，第i個(gè)更新點(diǎn) Γi=Γ0+ iT(i=0,1,2,…)。子秘密更新算法可以由秘密分發(fā)者D執(zhí)行，也可以由一個(gè)可信的秘密更新服務(wù)器執(zhí)行。本文方案由D執(zhí)行秘密更新算法。

1) 秘密分發(fā)者D執(zhí)行的協(xié)議:

step1 在第τ(τ=1,2,…)次更新，秘密分發(fā)者D從單向散列鏈L上提取散列值(α) ,構(gòu)造多項(xiàng)式

step2 計(jì)算參與者 Pi的影子秘密更新值

給Pi，公布 U(τ)。

2) 參與者Pi執(zhí)行的協(xié)議:

若通過驗(yàn)證，運(yùn)行step2；否則返回錯(cuò)誤信息；

有影子秘密。

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

需要解密C的參與者PD向P中成員發(fā)送解密申請(qǐng)，通過身份驗(yàn)證后收到來自P中t個(gè)成員的影子秘密，其執(zhí)行的操作如下(設(shè)t個(gè)成員組成的授權(quán)子集為Φ，秘密重構(gòu)時(shí)所處的更新點(diǎn)為τ)。

step1 驗(yàn)證收到的影子秘密合法性；

集合Φ?{1,2,…,n},Φ ≥t 。

于是參與者PD得到解密算子k，根據(jù)IBE公鑰加密算法，明文 M=V ⊕ H2(kr)。

5 安全性分析和證明

5.1 正確性證明

本方案基于IBE公鑰加密算法，下面通過定理1證明方案的正確性。

定理1 若參與者數(shù)量為n，門限值為t(n≥t)，接入結(jié)構(gòu)中存在一個(gè)授權(quán)子集Φ滿足，則任何合法解密請(qǐng)求者獲得Φ中成員提供的影子秘密可以解密C得到明文M。

證明 考慮初始狀態(tài)和更新后狀態(tài)2種情況。

1) 初始狀態(tài)。

已知接入結(jié)構(gòu)中成員 Pi收到的影子秘密，廣播信道公布的驗(yàn)證密鑰由于

故通過式(2)的正確性驗(yàn)證后，Pi確定收到了正確的影子秘密。

需要解密C的參與者PD得到來自Φ的秘密份額后，根據(jù)拉格朗日插值定理，有

根據(jù) IBE公鑰算法，密文 C對(duì)應(yīng)的明文為M=V ⊕ H2(kr)。

2) 影子秘密更新后。

不失一般性，假設(shè)系統(tǒng)處于τ(τ=1,2,…)次更新后的狀態(tài)。參與者Pi收到τ次影子秘密增量并通過式(4)驗(yàn)證其正確性。這是因?yàn)?/p>

此時(shí)的秘密多項(xiàng)式為

此時(shí)對(duì)于參與者Pi持有的秘密份額，由于、分別為多項(xiàng)式F(0)(x)和G(τ)(x)在i點(diǎn)的值，易知也是多項(xiàng)式F(τ)(x)在 i點(diǎn)的值。根據(jù)拉格朗日插值定理，可以得到 k，進(jìn)而解密密文C，得到明文 M=V ⊕ H2(kr)。

綜合以上2種情況，任何合法解密請(qǐng)求者獲得Φ中成員提供的影子秘密可以解密C得到明文M。(證畢)

5.2 安全性分析

方案的安全性基于IBE公鑰密碼體制和離散對(duì)數(shù)難解問題。傳統(tǒng)的RSA算法使用1024bit作為密碼長(zhǎng)度時(shí)能提供目前可接受的安全水準(zhǔn)。而達(dá)到同樣的安全水準(zhǔn)，基于橢圓曲線的 IBE算法只需160bit 的密碼長(zhǎng)度。210bit密碼長(zhǎng)度的IBE算法則與2048bit的RSA 具有相同的安全強(qiáng)度。本方案采用IBE算法可以用更較小的存儲(chǔ)代價(jià)在最大程度上保證系統(tǒng)安全性。本方案在秘密分發(fā)、影子秘密更新、共享秘密重構(gòu)過程中使用多種安全機(jī)制避免惡意參與者的攻擊和來自內(nèi)部的合謀、欺騙。下面從影子秘密傳遞和更新2個(gè)角度分析方案的安全性。

1) 影子秘密分發(fā)和傳遞過程的安全性。

方案中影子秘密分發(fā)的同時(shí)公布驗(yàn)證密鑰Uj=gaj(0≤j≤t-1)，集合P中的參與者很容易通過等式(2)驗(yàn)證影子秘密的正確性，從而有效防止傳輸過程中受到惡意更改或秘密分發(fā)者欺騙。基于離散對(duì)數(shù)難解問題，惡意攻擊者通過公開信息 Uj無法獲得aj(0≤j≤t-1)，因而無法得到插值多項(xiàng)式的任何信息，保證了共享秘密的安全。

2) 影子秘密更新的安全性。

本方案采用靈活的更新方式，即所謂的雙重更新。更新可以由周期觸發(fā)器激活或者由管理員激活。也可以設(shè)定當(dāng)c個(gè)子秘密泄露時(shí)進(jìn)行更新，確保共享秘密的安全。在周期τ，插值多項(xiàng)式為F(τ)(x)，攻擊者必須得到至少t個(gè)影子秘密才能得到共享秘密信息。適當(dāng)設(shè)置更新頻率便可降低攻擊者成功的概率。因?yàn)椋總€(gè)參與者在影子秘密更新后銷毀原有影子秘密，攻擊者在上個(gè)周期獲得的k(k ＜t)個(gè)影子秘密在當(dāng)前周期已經(jīng)失效。注意到，秘密更新不改變(t，n)秘密共享方案的門限值，在任何周期內(nèi)攻擊者都面臨攻破 Shamir門限秘密共享方案的難度。

5.3 方案性能分析和對(duì)比

5.3.1 性能分析

1) 運(yùn)算量和復(fù)雜性方面。

方案主要由共享秘密的分發(fā)、影子秘密更新和共享秘密重構(gòu)3個(gè)協(xié)議組成。其中共享秘密的分發(fā)和重構(gòu)使用基于IBE的門限算法，影子秘密更新使用單向散列鏈和拉格朗日插值算法。從計(jì)算復(fù)雜度方面分析，計(jì)算量主要集中在雙線性對(duì)?e的計(jì)算、模指數(shù)運(yùn)算等方面（見表1）。

表1 方案計(jì)算量

目前求解雙線性映射的可行算法是 Boneh-Franklin 提出的基于有限域內(nèi)超奇異橢圓曲線上的Weil Pairing 的算法[15]。借助于Weil Pairing，雙線性映射e?可以表示為2個(gè)具有相同計(jì)算復(fù)雜度O(lbq)的函數(shù)的比值

因而e?運(yùn)算的計(jì)算復(fù)雜度為O(lbq)。

模指數(shù)運(yùn)算通常采用快速求冪的方法求解。其主要思想是把指數(shù)當(dāng)作μ bit的二進(jìn)制數(shù)來處理。如計(jì)算 y=axmod n ，記

其中 xi∈{0,1}(i=0,1,…,μ-1)。于是y可以表示為μ項(xiàng)的乘積：

易知μ=lbn，所以快速求冪算法的計(jì)算復(fù)雜度為O(lbn)。

相對(duì)于e?運(yùn)算和模指數(shù)運(yùn)算，拉格朗日插值多項(xiàng)式的運(yùn)算具有更高的計(jì)算復(fù)雜度，目前已知的構(gòu)造經(jīng)過 n個(gè)點(diǎn)的插值多項(xiàng)式需要 O(n lg2n)次乘法運(yùn)算，拉格朗日插值算法的復(fù)雜度為 O(n lb2n)，插值的計(jì)算開銷與插值多項(xiàng)式的次數(shù)有關(guān)。

2) 存儲(chǔ)量方面。

系統(tǒng)存儲(chǔ)的信息包括公開的信息和參與者自身保存的秘密信息。秘密分發(fā)者D需要維護(hù)一條單向散列鏈L，占用存儲(chǔ)空間為lN+1。同時(shí)D需要保存的秘密信息為主密鑰s和共享秘密S。對(duì)每個(gè)參與者來說，僅需保存當(dāng)前周期(τ)的影子秘密

。公開的信息包括系統(tǒng)參數(shù)psys，驗(yàn)證密鑰Uj=gaj(0≤j≤t-1)，U(τ)等，這些信息可以通過廣播方式發(fā)送，也可存儲(chǔ)于共享存儲(chǔ)空間(如系統(tǒng)公告牌)。由于采用 IBE公鑰算法，公開這些信息不會(huì)對(duì)系統(tǒng)的安全性造成影響，因而可以根據(jù)系統(tǒng)配置靈活選擇存儲(chǔ)資源。

3) 通信性能方面。

方案通信主要包括廣播和單播。眾所周知，廣播通信是最有效、最節(jié)省能量的通信方式。本文方案的各個(gè)階段較多的使用了廣播通信，如公布公共參數(shù)和驗(yàn)證信息以及系統(tǒng)同步等。相對(duì)于廣播通信，方案中只有在分發(fā)初始影子秘密和更新影子秘密時(shí)使用安全信道的點(diǎn)對(duì)點(diǎn)單播，通信數(shù)據(jù)量較小。此外，本方案使用單向散列鏈生成更新多項(xiàng)式參數(shù)，使驗(yàn)證信息較傳統(tǒng)方案大幅度減少，從而進(jìn)一步提高通信性能。

4) 影子秘密更新性能方面。

方案基于單向散列鏈構(gòu)造更新多項(xiàng)式，較傳統(tǒng)方案能大幅度提高更新性能。如文獻(xiàn)[6]中方案更新時(shí)需要重新生成k-1階秘密多項(xiàng)式進(jìn)行k-1次模指數(shù)運(yùn)算(i=1,2,…,k-1)。可見其復(fù)雜度等同于重新執(zhí)行秘密分發(fā)協(xié)議，系統(tǒng)開銷較大。本文方案使用單向散列鏈，避免了更新時(shí)秘密多項(xiàng)式生成的計(jì)算開銷，同時(shí)使模指數(shù)運(yùn)算次數(shù)降低為1次，從而大幅度降低系統(tǒng)開銷，提高更新性能。

5.3.2 與現(xiàn)有方案的對(duì)比分析

下面從算法的計(jì)算復(fù)雜度、空間復(fù)雜度、通信開銷以及更新效率等方面將本方案同現(xiàn)有方案進(jìn)行對(duì)比分析(見表2)。通過對(duì)比可以看出，本方案同所有使用拉格朗日插值的方案一樣具有 O(n lb2n)的計(jì)算復(fù)雜度。在空間復(fù)雜度方面，本方案僅使用必要的存儲(chǔ)空間和保存長(zhǎng)度為 N(N ＜n)的單向散列鏈所占用的空間。在通信量方面，本方案僅與系統(tǒng)規(guī)模相關(guān)。綜上可知，本方案與已有方案相比，在保持較低的計(jì)算復(fù)雜度和空間復(fù)雜度的同時(shí)，降低了通信開銷并提高了更新效率。

表2 與現(xiàn)有方案對(duì)比分析

5.4 仿真分析

為了驗(yàn)證所提方案的性能，使用MS VC6.0實(shí)現(xiàn)了所提方案，并部署在局域網(wǎng)環(huán)境下的計(jì)算機(jī)集群中。集群中計(jì)算機(jī)節(jié)點(diǎn)配置512MB內(nèi)存，Windows XP（sp3）操作系統(tǒng)。由于集群計(jì)算機(jī)使用不同頻率的CPU，仿真實(shí)驗(yàn)中使用CPU時(shí)間作為衡量指標(biāo)。所有數(shù)據(jù)均為進(jìn)行10次試驗(yàn)結(jié)果的平均值。

圖1顯示了秘密分發(fā)執(zhí)行時(shí)間隨網(wǎng)絡(luò)規(guī)模的變化情況?？梢钥闯?，執(zhí)行時(shí)間隨節(jié)點(diǎn)數(shù)目增加呈線性關(guān)系。相同網(wǎng)絡(luò)規(guī)模下，系統(tǒng)門限值t的變化對(duì)執(zhí)行時(shí)間影響不大。圖2顯示在同樣網(wǎng)絡(luò)規(guī)模下，增大t值沒有對(duì)計(jì)算性能帶來太大的影響。

圖3和圖4驗(yàn)證了秘密重構(gòu)階段方案執(zhí)行時(shí)間跟網(wǎng)絡(luò)規(guī)模和t值之間的關(guān)系。結(jié)果顯示重構(gòu)階段執(zhí)行效率比分發(fā)階段有明顯降低，且時(shí)間復(fù)雜度受參數(shù)影響較小，因此方案有很好的可擴(kuò)展性。

圖1 秘密分發(fā)計(jì)算量隨網(wǎng)絡(luò)規(guī)模變化曲線

圖2 秘密分發(fā)計(jì)算量隨t值變化曲線

圖3 秘密重構(gòu)過程計(jì)算量隨網(wǎng)絡(luò)規(guī)模變化曲線

圖4 秘密重構(gòu)過程計(jì)算量隨t值變化曲線

圖5驗(yàn)證了密鑰更新過程的計(jì)算量，結(jié)果顯示更新計(jì)算量隨網(wǎng)絡(luò)節(jié)點(diǎn)增加呈線性關(guān)系，但從絕對(duì)值上看，50個(gè)節(jié)點(diǎn)更新的計(jì)算量?jī)H相當(dāng)于在30個(gè)節(jié)點(diǎn)中重新分發(fā)影子秘密的水平，故采用所提的更新算法能極大提高方案的計(jì)算效率。

圖5 更新過程計(jì)算量

6 結(jié)束語

本文基于單向散列鏈和IBE公鑰算法提出了一個(gè)可更新秘密共享方案，該方案具有以下3個(gè)特點(diǎn)：1)在影子秘密更新階段，采用單向散列鏈生成更新多項(xiàng)式，使更新過程計(jì)算量和通信代價(jià)顯著減小；2) 方案的安全性基于 IBE公鑰算法，具有密鑰長(zhǎng)度小，安全性高等優(yōu)點(diǎn)；3) 影子秘密交換基于雙線性映射 BDH難解問題，而正確性驗(yàn)證基于離散對(duì)數(shù)難解問題，可有效防止惡意竊聽、欺騙等攻擊。靈活設(shè)置更新周期T可滿足系統(tǒng)不同等級(jí)的安全需求。目前PSS方案的設(shè)計(jì)基礎(chǔ)是共享秘密空間和影子秘密空間具有加法結(jié)構(gòu)或線性結(jié)構(gòu)，即所謂的同態(tài)秘密共享。更新過程利用分配函數(shù)的可加性實(shí)現(xiàn)，使更新效率的提升空間受到限制。如何設(shè)計(jì)新型分配函數(shù)，構(gòu)造性能優(yōu)異的PSS方案是進(jìn)一步的研究方向。

[1] HARN L,LIN C L.Detection and identification of cheaters in(t,n)secret sharing scheme[J].Designs Codes and Cryptography,2009,52(1):15-24.

[2] HERZBERG A,JARECKI S,KRAWCZYK H,et al.Proactive secret sharing or: how to cope with perpetual leakage[A].Coppersmith Ded Advances in Cryptology CRYPTO’95[C].Berlin: Springer Verlag,1995.339-352.

[3] TANG C M,WU D O,CHRONOPOULOS A T,et al.Efficient multi-party digital signature using adaptive secret sharing for low-power devices in wireless networks[J].IEEE Transactions on Wireless Communications,2009,8(2): 882-889.

[4] QIU G,WANG H ,XIAO H,et al.Improvement on tzeng-tzeng's robust forward-secure signature schemes with proactive security[J].Chinese Journal of Electronics,2009,18(1) : 155-158.

[5] YANG J P,RHEE K H,SAKURAI K.A proactive secret sharing for server assisted threshold signatures[A].2nd International Conference on High Performance Computing and Communications(HPCC2006)[C].Munich Germany,Berlin: Springer,2006.250-259.

[6] 許春香,魏仕民,肖國(guó)鎮(zhèn).定期更新防欺詐的秘密共享方案[J].計(jì)算機(jī)學(xué)報(bào),2002,25(6): 657-660.XU C X,WEI S M,XIAO G Z.A secret sharing scheme with periodic renewing to identify cheaters[J].Chinese Journal of Computers,2002,25(6): 657-660.

[7] WANG S J,TSAI Y R,CHEN P Y.Proactive(k,n) threshold secret sharing scheme with variant k and n[A].IEEE-PROCEEDINGS,2007 International Conference on Intelligent Pervasive Computing[C].Jeju Island Korea,2007.117-120.

[8] SUN H,ZHENG X,YU Y.A proactive secret sharing scheme based on elliptic curve cryptography[A].Education Technology and Computer Science[C].2009.ETCS '09.First International Workshop,Wuhan China,2009.666 -669.

[9] ZHANG R S,CHEN K F.An efficient proactive RSA scheme for large-scale ad hoc networks[J].Journal of Shanghai University(English Edition),2007,11(1):64-67.

[10] LI F,SHANG J W,LI D X.A proactive secure multi-secret sharing threshold scheme[A].The 8th ACIS International Conference on Software Engineering,Artificial Intelligence,Networking and Parallel/Distributed Computing(SNPD2007)[C].Qingdao,China,2007.105-110.

[11] ZHOU L D,SCHNEIDER F B,RENESSE R V,et al.APSS: proactive secret sharing in asynchronous systems[J].ACM Transactions on Information and System Security,2005,8(3):259-286.

[12] ASAEDA H,RAHMAN M,TOYAMA Y.Structuring proactive secret sharing in mobile ad-hoc networks[A].1st International Symposium on Wireless Pervasive Computing,Phuket Thailand,International Symposium on Wireless Pervasive Computing[C].2006.342-347.

[13] LAMPORT L.Password authentication with insecure communication[J].Communications of the ACM,1981,24(11):770-772.

[14] 楊庚,王江濤,程宏兵等.基于身份加密的無線傳感器網(wǎng)絡(luò)密鑰分配方法[J].電子學(xué)報(bào),2007.35(1):180-184.YANG G,WANG J T,CHENG H B,et al.A key establish scheme for WSN based on IBE and diffie-hellman algorithms[J].Chinese Journal of Electronics,2007,35(1): 180-184.

[15] BONEH D,FRANKLIN M.Identity-based encryption from the weil pairing[A].Advances in Cryptology-CRYPTO 2001[C].Springer-Verlag,2001.213-229.