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

李大偉，楊庚

（南京郵電大學 計算機學院，江蘇 南京210003）

1 引言

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

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

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

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

本文組織結構如下：第2節介紹相關研究工作；第3節介紹預備知識；第4節對所提方案進行描述；第5節對方案的安全性和有效性進行分析和仿真；第6節是結束語。

2 相關工作

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

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

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

3 預備知識

3.1 單向散列鏈

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

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

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

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

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

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

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

3.2 IBE公鑰算法基礎

IBE公鑰加密算法的安全性建立在CDH困難問題的變形BDH問題之上[14]。記Zq為素數階q的群，G為加法群，F為乘法群。

定義2 （雙線性映射）對?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)可計算性：存在多項式時間算法計算e?。

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

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

(7)經濟性原則。電網運營在線監測系統的架構設計應滿足經濟性要求，充分利用現有技術手段，通過電力企業一體化信息平臺整合各類信息系統資源，進行綜合利用與再開發，有效節約投資成本。

4 方案描述

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

4.1 系統初始化階段

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

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

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

H3:G*? G*。

4.2 秘密分發階段

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

step1 隨 機 選 擇{ai|ai∈ G*;i=1,2,…,t-1;at-1≠ 0}構造t-1階多項式

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

0

參與者Pi收到影子秘密后，驗證

4.3 子秘密更新階段

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

1) 秘密分發者D執行的協議:

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

step2 計算參與者 Pi的影子秘密更新值

給Pi，公布 U(τ)。

2) 參與者Pi執行的協議:

若通過驗證，運行step2；否則返回錯誤信息；

有影子秘密。

4.4 秘密重構階段

需要解密C的參與者PD向P中成員發送解密申請，通過身份驗證后收到來自P中t個成員的影子秘密，其執行的操作如下(設t個成員組成的授權子集為Φ，秘密重構時所處的更新點為τ)。

step1 驗證收到的影子秘密合法性；

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

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

5 安全性分析和證明

5.1 正確性證明

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

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

證明 考慮初始狀態和更新后狀態2種情況。

1) 初始狀態。

已知接入結構中成員 Pi收到的影子秘密，廣播信道公布的驗證密鑰由于

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

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

根據 IBE公鑰算法，密文 C對應的明文為M=V ⊕ H2(kr)。

2) 影子秘密更新后。

不失一般性，假設系統處于τ(τ=1,2,…)次更新后的狀態。參與者Pi收到τ次影子秘密增量并通過式(4)驗證其正確性。這是因為

此時的秘密多項式為

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

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

5.2 安全性分析

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

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

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

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

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

5.3 方案性能分析和對比

5.3.1 性能分析

1) 運算量和復雜性方面。

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

表1 方案計算量

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

因而e?運算的計算復雜度為O(lbq)。

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

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

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

相對于e?運算和模指數運算，拉格朗日插值多項式的運算具有更高的計算復雜度，目前已知的構造經過 n個點的插值多項式需要 O(n lg2n)次乘法運算，拉格朗日插值算法的復雜度為 O(n lb2n)，插值的計算開銷與插值多項式的次數有關。

2) 存儲量方面。

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

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

3) 通信性能方面。

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

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

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

5.3.2 與現有方案的對比分析

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

表2 與現有方案對比分析

5.4 仿真分析

為了驗證所提方案的性能，使用MS VC6.0實現了所提方案，并部署在局域網環境下的計算機集群中。集群中計算機節點配置512MB內存，Windows XP（sp3）操作系統。由于集群計算機使用不同頻率的CPU，仿真實驗中使用CPU時間作為衡量指標。所有數據均為進行10次試驗結果的平均值。

圖1顯示了秘密分發執行時間隨網絡規模的變化情況。可以看出，執行時間隨節點數目增加呈線性關系。相同網絡規模下，系統門限值t的變化對執行時間影響不大。圖2顯示在同樣網絡規模下，增大t值沒有對計算性能帶來太大的影響。

圖3和圖4驗證了秘密重構階段方案執行時間跟網絡規模和t值之間的關系。結果顯示重構階段執行效率比分發階段有明顯降低，且時間復雜度受參數影響較小，因此方案有很好的可擴展性。

圖1 秘密分發計算量隨網絡規模變化曲線

圖2 秘密分發計算量隨t值變化曲線

圖3 秘密重構過程計算量隨網絡規模變化曲線

圖4 秘密重構過程計算量隨t值變化曲線

圖5驗證了密鑰更新過程的計算量，結果顯示更新計算量隨網絡節點增加呈線性關系，但從絕對值上看，50個節點更新的計算量僅相當于在30個節點中重新分發影子秘密的水平，故采用所提的更新算法能極大提高方案的計算效率。

圖5 更新過程計算量

6 結束語

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

[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] 許春香,魏仕民,肖國鎮.定期更新防欺詐的秘密共享方案[J].計算機學報,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] 楊庚,王江濤,程宏兵等.基于身份加密的無線傳感器網絡密鑰分配方法[J].電子學報,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.