曹 陽，洪 歧，陳 勇，李 軍

(陜西理工學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，陜西漢中723000)

0 引言

基于Lagrange插值多項式(t，n)門限秘密共享方案是Shamir［1］在1979提出的，隨后學(xué)者對其進(jìn)行了大量研究。文獻(xiàn)［2］中各參與者的秘密份額是由分發(fā)者分發(fā)的，增加了通信、計算及存儲的復(fù)雜度;文獻(xiàn)［3］解決了參與者的子秘密更新問題，但更新不定期［4］;文獻(xiàn)［5］以時間為代價實現(xiàn)了共享秘密的定期動態(tài)更新;文獻(xiàn)［6］提出的是基于XTR的秘密共享方案;文獻(xiàn)［7］提出的秘密共享方案是在秘密分發(fā)者安全存儲各參與者秘密份額的前提下，參與者的加入與退出不改變其他參與者的秘密份額［8］;文獻(xiàn)［9］提出的是基于RSA可驗證的動態(tài)多重秘密共享方案;文獻(xiàn)［10］實現(xiàn)了參與者之間相互驗證子秘密，防止了參與者之間的欺詐行為。但以上文獻(xiàn)提出的秘密共享方案都具有一定的局限性，基于大數(shù)分解、離散對數(shù)的難解問題及Shamir的門限方案提出了具有時間限制的動態(tài)秘密共享方案。該方案實現(xiàn)了參與者秘密份額由自己生成，秘密更新不需要秘密分發(fā)者的參與，參與者只需要維護(hù)自己的一份秘密份額就可以共享任意多個秘密;秘密份額必須在有效時間范圍內(nèi)更新才有效，無需額外通信量;參與者的加入與退出不影響其他參與者秘密份額的改變;秘密恢復(fù)在有效期內(nèi)對秘密份額進(jìn)行驗證，防止欺騙行為。

1 相關(guān)知識

1.1 橢圓曲線

橢圓曲線［11］指的是由韋爾斯特拉斯(Weierstrass)方程

y2+a1xy+a3y=x3+a2x2+a4x+a6

所確定的平面曲線。系數(shù)ai(i=1，2，…，6)可以是有理數(shù)域、實數(shù)域、復(fù)數(shù)域，還可以是有限域E(Fp)，橢圓曲線密碼體制(elliptic curve cryptosystem，ECC)中用到的橢圓曲線都定義在有限域上的。

1.2 橢圓曲線離散對數(shù)問題

G是橢圓曲線E(Fp)上的基點，N為G的階(N為一個安全的大素數(shù))，如整數(shù)m(0＜m＜N－1)存在，Q=mG，則稱m為Q的以G為基的離散對數(shù)。對于E(Fp)上的一點G，對任意的Q，求整數(shù)m，使得Q=mG的問題稱為橢圓曲線上的離散對數(shù)問題(elliptic curve discrete logarithm problem，ECDLP)［11-12］，橢圓曲線密碼體制正是利用這個困難問題設(shè)計而來。

1.3 最小授權(quán)子集

設(shè)A={P1，P2，…，Pn}為用戶集P構(gòu)成的訪問結(jié)構(gòu)，Bj={P1j，P2j，…，Pij}(1 ≤ i≤m，1 ≤j≤n)是A的用戶子集，Bj∈A，若?a∈Bj，Bj－a?A，則稱Bj為A的最小授權(quán)子集［6］，A為授權(quán)集。令Pij∈ Bj，［T1i，T2i］為參與者 Pij的有效期 (1 ≤ i≤m)，稱［T1Bj，T2Bj］=［T11，T21］∩［T12，T22］∩…∩［T1m，T2m］=∩mi［T1i，T2i］為最小授權(quán)子集 Bj的有效期［6］。本文中提到的授權(quán)子集都指的是最小授權(quán)子集。

2 方案構(gòu)成

設(shè)SD為可信第三方秘密分發(fā)者，NB(notice board)為公告牌，SD通過公告牌將秘密k分為m個子秘密分發(fā)給授權(quán)子集Bj中的m個不同的參與者{P1j，P2j，…，Pij}(1 ≤i≤m)共享，當(dāng)且僅當(dāng)授權(quán)子集中的s個或s以上個參與者聯(lián)合才能恢復(fù)秘密k，而非授權(quán)子集中的參與者聯(lián)合不能恢復(fù)秘密k的任何信息。公告牌上的內(nèi)容只有SD才能更新和修改，其他人只能查看下載。本方案由初始化參數(shù)選取、注冊、秘密份額生成、秘密恢復(fù)、秘密份額及秘密的更新5部分組成。

2.1 初始化參數(shù)的選取

1)在橢圓曲線E(Fp)上選取基點G，N(N為一個安全的大素數(shù))，N為G的階，SD在NB上發(fā)布G，N;

2)參與者Pij隨機(jī)選擇一個整數(shù)ri(1＜ri＜N)，計算Gi=riG，Pij保密ri，將Gi發(fā)送給SD;

3)SD選取整數(shù)r0(1＜r0＜N)，計算G0=r0G;

4)SD與Pij共同協(xié)商一個哈希函數(shù)H()，要求沖突的概率足夠小;

5)SD在NB上公布參數(shù)Gi，G0，H()。

2.2 注 冊

設(shè)有β個授權(quán)子集參與秘密共享。

1)SD 選取 β 個不同的數(shù)d1，d2，…，dβ∈［1，N－1］來標(biāo)識A中的每個授權(quán)子集;

2)SD將時間劃分成一些小區(qū)間，時間的長度可以小時、天、日期、月等為單位，如 1，2，3，…，L，L表示系統(tǒng)中存在的最長時間;

3)SD為每個授權(quán)子集Bj中的秘密共享成員設(shè)定有效期［T1ij，T2ij］，并在 NB 上發(fā)布;

4)SD根據(jù)各成員的有效期，計算出每個授權(quán)子集的有效期，并在NB上發(fā)布;

5)SD隨機(jī)選取2m個不同的數(shù)ai，bi(1≤i≤m)，計算HT1ij(ai)，HL－T2ij(bi)，通過安全信道分別發(fā)送給對應(yīng)的參與者，同時銷毀ai，bi。

2.3 秘密份額生成

秘密份額生成的過程由秘密分發(fā)者SD和參與者共同完成，生成過程如下。

1)SD隨機(jī)選取一整數(shù)l(1＜l＜N)，l必須與其他秘密分發(fā)選取的隨機(jī)數(shù)不同，計算s=lG，并將s在公告牌上公布;

2)A 中的每個一授權(quán)子集 Bj={P1j，P2j，…，Pij}(1≤i≤m)，參與者Pij隨機(jī)選取一整數(shù)j(1＜j＜ N)，計算eij=jG，e'ij=jG0，令c0ij=sri⊕e'ij。并將c0ij，eij發(fā)送給秘密分發(fā)者SD，如果一個參與者同時在多個授權(quán)子集中，則該參與者只發(fā)送一個c0ij，eij給 SD;

3)SD檢查收到的c0ij，eij，保證不同的參與者有不同的c0ij，eij，以免不同的參與者擁有相同的秘密份額。如果相同，參與者就必須重新選取初始秘密份額，直到各參與者都擁有不同的秘密份額，并將參與者的信息c0ij，eij在公告牌上公布;

4)SD計算e'ij=r0eij=r0jG ，sri=cij⊕e'ij，令x0ij=sr，利用公告信息驗證sriG是否等于sGi，若相等，則接收x0ij;

5)SD從［1，N －1］中任選整數(shù)b，q，生成Lagrange多項式f(x)=(bx+k)mod q，計算f(1)，將(1，f(1))在公告牌上公布;

6)SD為每個授權(quán)子集Bj計算Xj=H(d1x01j⊕d2x02j⊕…⊕djx0ij)，f(Xj)，并將f(Xj)，dj在公告牌上公布。

2.4 秘密恢復(fù)

秘密恢復(fù)是由秘密生成者SG(secret generator)來完成的，SG可以是Bj中的參與者，也可以是非Bj中的其他成員。秘密恢復(fù)工作是在t+1次更新前，t次更新后進(jìn)行的。

1)Bj中的參與者Pij隨機(jī)選取一整數(shù)(1＜j＜N)，計算eij=jG，e'ij=jG0，令ctij=sri⊕ e'ij，將ctij，eij發(fā)送給 SG;

2)SG從公告牌上下載((1，f(1))，f(Xj))和dj的有效期;

3)SG判斷dj是否在有效期內(nèi)，如果在，則繼續(xù)第4)步，如果不在，則向Bj中的每一個參與者發(fā)送一個報怨;

4)計算e'ij=r0eij=r0jG，則sri=ctij⊕ e'ij，令xtij=sr，利用公開信息，驗證sriG是否等于sGi，如ijiii果相等，接收xtij，驗證通過，否則放棄;

5)SG根據(jù)Xj=H(d1x1tj⊕d2x2tj⊕…⊕djxtij)和((1，f(1))，f(Xj))，利用Lagrange恢復(fù)多項式，從而恢復(fù)出秘密k。

2.5 秘密份額及秘密信息的更新

秘密分發(fā)者 SD 在時刻 t=1，2，3，…，L進(jìn)行如下工作。

1)Bj中的每一個參考者 Pij在 t時刻，若t∈ ［T1ij，T2ij］則 計 算utij= Ht(aij)HL－t(bij)=［Ht－T1ij(HT1ij(aij))］［HT2ij－t(HL－T2ij(bij))］;

2)Pij計算xtij=xtij－1+utij，更新所持有的秘密份額，銷毀 xtij－1;

3)如果需要更新秘密信息為k'，則SD從［1，N－1］中隨機(jī)選擇一個整數(shù) b'，q，計算f(x)=(k'+b'x)mod q，然后將f(1)公布在公告牌上，如果不需要更新秘密信息則執(zhí)行下一步;

4)SD為每個授權(quán)子集Bj計算Xj=H(d1x1tj⊕d2x2tj⊕…⊕djxtij)，f(Xj)，將f(Xj)，dj公布在公告牌上。

3 方案討論

3.1 多重秘密共享

方案中每個參與者Pij只需維護(hù)自己的秘密份額。如果m個參與者共享n個秘密k1，k2，…kn，當(dāng)且僅當(dāng)A中的每一個授權(quán)子集Bj中的參與者共同合作才能恢復(fù)出秘密，其他未被恢復(fù)的秘密的安全性并不會因為此秘密的恢復(fù)而受到影響。秘密分發(fā)時，分發(fā)者SD均隨機(jī)生成整數(shù)l(1＜l＜N)且與其他的隨機(jī)數(shù)不同，計算s=lG，參與者計算sri，根據(jù)橢圓曲線離散對數(shù)的難解性，攻擊者無法從sri計算出ri。公告牌上公布了f(1)，但在構(gòu)造多項式時，為每個秘密生成了一個參數(shù)b，并且為每個授權(quán)子集計算了f(Xj)。秘密共享時參與者之間并不會泄露私有秘密份額，加上秘密份額具有時間限制，攻擊者就無法利用本次秘密共享結(jié)果去計算恢復(fù)其他秘密，當(dāng)然也不會因為重復(fù)使用秘密份額而影響系統(tǒng)的安全性。

3.2 參與者的加入/退出

應(yīng)用中，參與者的加入/退出都會引起訪問結(jié)構(gòu)的改變，但并不影響其他參與者秘密份額的改變。當(dāng)增加一個新的參與者Pn+1時，SD為新增加的參與者Pn+1確定對秘密共享的有效期［T1n+1，T2n+1］，并發(fā)布在公告牌上。SD隨機(jī)選取2個不同的數(shù)an+1，bn+1，計算HT1(n+1)j(an+1)，HL－T2(n+1)j(bn+1)，通過安全信道分別發(fā)送給對應(yīng)的參與者，同時銷毀 an+1，bn+1。Pn+1從［1，N － 1］中隨機(jī)選取整數(shù) jn+1，rn+1，計算en+1=jn+1G，e'n+1=jG0，cn+1=srn+1⊕e'n+1，并將srn+1⊕e'n+1，en+1發(fā)送給SD。SD檢查驗證，保證不同的參與者有不同的秘密份額，即對任意的xi(i=1，…，n)，xi≠xi+1。如果參與者 Pn+1的加入導(dǎo)致授權(quán)子集的增加，SD需在［1，N－1］選取一個整數(shù)dn+1，標(biāo)識增加的授權(quán)子集，并按2.3中的5)和6)計算公布相關(guān)信息。當(dāng)刪除參與者Pij時，可能導(dǎo)致某些授權(quán)子集變成非授權(quán)子集，SD需在公告牌上刪除Pij的相關(guān)信息，及與Pij相關(guān)的授權(quán)子集信息、有效期標(biāo)識。為了安全起見，應(yīng)該更新共享秘密。

3.3 方案安全性分析

1)方案是安全的。

證明:t時刻，攻擊者將要根據(jù)公開信息 (1，f(1))以及各授權(quán)子集的信息f(Xj)，dj獲取秘密k，必須得到 Xj，由 Xj=H(d1x1tj⊕d2x2tj⊕…⊕dxt)可知，要獲得X還必須同時獲得授權(quán)子集中的所有參與者Pij的有效期限和秘密份額xtij。假設(shè)攻擊者截取ctij，eij，試圖計算出秘密份額xtij，由于e'ij=rteij=rtjG，sri=ctij⊕ e'ij，xtij=sri，但要計算出正確的秘密份額還必須獲得參與者與秘密分發(fā)者的秘密數(shù)，由橢圓曲線離散對數(shù)問題知，攻擊者無法計算出xtij，也就無法獲取秘密k，因此方案是安全的。

2)秘密份額及秘密更新是安全的。

證明:時 刻 t=1，2，3，…，L，若 t ∈［T1ij，T2ij］，參與者Pij需要更新自己的秘密份額。秘密份額的更新是通過SD和參與者Pij在秘密生成過程中共同擁有的哈希函數(shù) HT1ij(ai)，HL－T2ij(bi)，計算utij= Ht(aij)HL－t(bij)=［Ht－T1ij(HT1ij(aij))］×［HT2ij－t(HL－T2ij(bij))］來更新秘密份額 xtij=xtij－1+utij。

①當(dāng)T1ij≤ T2ij＜t時，只能求出 Ht(aij)=［Ht－T1ij(HT1ij(aij))］，但無法求出 HL－t(bij);

②當(dāng)t＜ T1ij≤ T2ij時，只能求出 HL－t(bij)=［HT2ij－t(HL－T2ij(bij))］，但無法求出 Ht(aij);

③當(dāng)且僅當(dāng)T1ij≤t≤T2ij時，才能同時求出Ht(aij)，HL－t(bij)。

綜上所述，只有參與者在有效期內(nèi)，才能更新自己的秘密份額。由于參與者與分發(fā)者之間不存在通信，加上哈希函數(shù)的單向性及求解的困難性知，Pij以外的參與者是無法得到Pij的秘密份額，所以秘密份額更新是安全的。

通過計算f(x)=(k'+b'x)mod q可將秘密k更新為k'，b'，q是SD從［1，N－1］中隨機(jī)選擇一個整數(shù)。

3)方案防止參與者的欺騙。

證明:秘密恢復(fù)過程第4)步，計算e'ij=r0eij=r0jG，則sri=ctij⊕e'ij，SG驗證sriG是否等于sGi，若相等，說明參與者Pij提供了正確的信息，繼續(xù)進(jìn)行秘密恢復(fù)工作，否則參與者可能存在欺騙行為，放棄秘密恢復(fù)。

4)方案具有前向安全性。

證明:秘密份額生成過程中，參與者Pij在公開信道上向SD發(fā)送的c0ij，eij，攻擊者截取 c0ij，eij也無法計算出sri，因為e'ij=r0eij=r0jG，sri=c0ij⊕ e'ij，其安全性是建立在橢圓曲線離散對數(shù)的安全性之上。

3.4 同類方案相比

下面主要從安全性能、通信復(fù)雜度、計算復(fù)雜度、運(yùn)算量四方面與引言中提到的文獻(xiàn)［2］方案相比。

安全性能方面:秘密更新必須在有效期內(nèi)完成，參與者和秘密分發(fā)者之間不存在通信，加上哈希函數(shù)的單向性及離散對數(shù)求解的困難性知，秘密更新的安全性進(jìn)一步加強(qiáng)。

通信復(fù)雜度:參與者秘密份額是由參與者自己生成，且只需維護(hù)自己的一份秘密份額就可以共享任意多個秘密，降低了通信的復(fù)雜度，進(jìn)而減少存儲空間。

計算復(fù)雜度:由文獻(xiàn)［8］知Lagrange多項式的計算復(fù)雜度比高次多項式的計算復(fù)雜度低，加之秘密份額的更新是通過哈希函數(shù)完成，秘密分發(fā)者與參與者之間不需要同步更新，也不存在傳輸量問題，所以方案降低了通信、計算的復(fù)雜度，提高了更新效率。

運(yùn)算量:增加授權(quán)子集時，秘密分發(fā)者SD增加的計算量主要是哈希運(yùn)算，因而運(yùn)算量不會大幅度增加。

4 總結(jié)

本文基于大數(shù)分解、離散對數(shù)的難解問題及Shamir的門限方案提出了具有時間限制的動態(tài)秘密共享方案。方案實現(xiàn)了參與者Pij秘密份額的生成，更新不需要秘密分發(fā)者SD的參與，參與者只需要維護(hù)自己的一份秘密份額就可以共享任意多個秘密;秘密份額更新必須在有效的時間范圍內(nèi)更新才有效，參與者和秘密分發(fā)者無需同步更新，也不存在通信量的問題;參與者的加入/退出不影響其他參與者秘密份額的改變，當(dāng)引起授權(quán)子集的增加時，計算量主要是秘密分發(fā)者進(jìn)行的哈希運(yùn)算，參與者的計算量不會隨授權(quán)子集的增加而增加;秘密恢復(fù)在有效期對秘密份額進(jìn)行驗證，防止欺騙行為。方案的安全性基于大數(shù)分解、橢圓曲線離散對數(shù)問題的難解性及Shamir的門限方案的安全性。

［1］SHAMIR A.How to Share a Secret［J］.Communications of the ACM，1979，22(11):612-613.

［2］LIU Duo，HUANG Dongping，LUO Ping，et al.New Schemes for Sharing Points on an Elliptic Curve［J］.Computers and Mathematics with Applications，2008，56(6):1556-1561.

［3］LAIH C S，HAM L，LEE J Y，et al.Dynamic Threshod Schemes Based on the Definition of Cross Product in Dimensional Linear Space［J］.Joural of Information Science and Engineering，1991，7(1):13-23.

［4］肖立國，鐘誠.基于ECC的定期更新的可驗證秘密共享方案［J］.計算機(jī)工程與科學(xué)，2006，28(7):25-27.XIAO Liguo，ZHONG Cheng.A Periodically Renewed Verifiable Secret Sharing Scheme Based on the Elliptic Curve Cryptosystem［J］.Computer Engineering ＆ Science，2006，28(7):25-27.

［5］張建中，張艷麗.一種子秘密可更新的動態(tài)多秘密共享方案［J］.計算機(jī)工程，2011，37(20):117-119.ZHANG Jianzhong，ZHANG Yanli.Dynamic Multi-secret Sharing Scheme with Updatable Sub-secret［J］.Computer Engineering，2011，37(20):117-119.

［6］趙佳.可信認(rèn)證關(guān)鍵技術(shù)研究［D］.北京:北京交通大學(xué)，2008:59-67.ZHAO Jia.Research on Key Technology of Trusted Authentication［D］.Beijing:Beijing Jiaotong University，2008:59-67.

［7］PINCH R.On-line multiple secret sharing［J］.Electronics Letters，1996，32(12):1087-1088.

［8］龐遼軍，姜正濤.基于一般訪問結(jié)構(gòu)的多重秘密共享方案［J］.計算機(jī)研究與發(fā)展，2006，43(1):33-38.PANG Liaojun，JIANG Zhengtao.A Multi-Secret Sharing Scheme Based on the General Access Structure ［J］.Journal of Computer Research and Development，2006，43(1):33-38.

［9］王鋒，張建中.基于RSA的可驗證的動態(tài)多重秘密共享方案［J］.計算機(jī)應(yīng)用研究，2008，25(6):1806-1808.WANG Feng，ZHANG Jianzhong. Dynamicverified threshold multi-secret sharing scheme based on RSA cryptosystem［J］Application Research of Computers，2008，25(6):1806-1808.

［10］戴元軍，馬春光.一種改進(jìn)的基于拉格朗日插值的(t，n)門限秘密共享［J］.北京郵電大學(xué)學(xué)報，2004，27(2):24-28.DAI Yuanjun，MA Chunguang.An Kind of(t，n)Threshold Secret Sharing Based on Lagrange Insert Value［J］.Journal of Beijing University of Posts and Telecommunications，2004，27(2):24-28.

［11］曹陽，郝玉潔，洪歧.一種基于ECDLP有身份認(rèn)證的ECDH密鑰協(xié)商方案［J］.重慶郵電大學(xué)學(xué)報:自然科學(xué)版，2012，24(1):118-120.CAO Yang，HAO Yujie，HONG Qi.One ECDH key agreement scheme with authentication based on ECDLP［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2012，24(1):118-120.

［12］HANKERSON D，MENEZES A，VANSTONES S.Guide to Elliptic Curve Crypotography［M］.New York，USA:Springer-Verlag，2004.