1、基于Shamir秘密共享的可驗證多秘密共享模型摘要:多秘密共享技術影響著信息安全和密碼學在新型網絡應用中的發展。分析了兩種YCH改進和一種基于齊次線性遞歸的多秘密共享方案，基于Shamir秘密共享提出并實現了一種新的可驗證的多秘密共享模型，該模型在秘密合成階段的時間復雜度為O(kt2)，優于兩種YCH改進模型(O(t3)(tk) O(k3)(tk),O(k(n+k)2)，實際模擬中秘密合成時間則少于其他三種模型，并且分析了四種模型在時間復雜度、可驗證性和公開值等方面的優劣性。在nk時，新模型所需公開值小于其他三種模型，實驗結果表明，新模型在秘密分發時間和秘密合成時間方面均優于其他三種模型。關

2、鍵 詞: 多秘密共享；lagrange插值；齊次線性遞歸； Shamir秘密共享中圖分類號: TP393文獻標識碼: AVerifiable multi-secret sharing scheme based on Shamir secret sharingAbstract: The development of the information security and cryptography in the new network applications is influenced by multi-secret sharing technology. In this paper, we

3、analyse two kinds of improved YCH and a multi-secret sharing solution based on homogeneous linear recursion, and we propose and realize a new verifiable multi-secret sharing model based on Shamir secret sharing, the time complexity of this model in the phase of secrets recovery is O(kt2), which is s

4、uperior to other two kinds of improved YCH model (O(t3)(tk) O(k3)(tk) ,O(k(n+k)2), the time of secrets synthesis in the actual simulation is less than the other three models, and we also analyse the advantages and disadvantages of the four models on the time complexity ,verifiability and open values

5、. When n k, the open values which the new model needs are fewer than that of the other three models, the experimental results show that the new model is better than the other three models on the time of secrets distribution and secrets recovery.Key words: Multi-secret sharing;Lagrange interpolation

6、polynomial;Homogeneous linear recursion; Shamir secret sharing1 引言秘密共享在導彈發射、電子商務、電子選舉和安全多方計算等方面有著廣泛的應用。A.Shamir1和G.Blakley2分別在有限域的多項式插值和有限幾何的基礎之上提出了秘密共享的概念。由于Shamir的(t,n)門限秘密共享機制是最簡單、最有效也是最實用的一種秘密共享機制3，Shamir秘密共享機制成為秘密共享研究的主流。但傳統的秘密共享只能保護一個秘密信息，于是多秘密共享方案被Blundo4等人提出，在多秘密共享方案中，每個成員只需要分配一個秘密份額，便可以同時共享

7、多個秘密。在隨后的幾年中，多秘密共享得到了迅速發展。Jackson5等人將所有的多秘密共享模型分為一次性模型和可重復使用模型。所謂一次性模型，即在每次秘密恢復之后，成員的秘密份額泄露，必須給每個成員重新分配秘密份額。而可重用模型可以避免這個問題，在可重用模型中，每次秘密恢復之后，無需重新分配秘密份額，也能保證每個成員秘密份額的安全性和有效性。但是當時提出的大多數模型都是一次性模型。基于此問題， He等人6提出了一種多階段秘密共享方案，該方案期望通過運用單項函數來保護秘密份額并使得秘密按照一定次序順次恢復。方案需要k個插值函數，每個插值函數的常數項gi(0)為秘密pi，因此重復性工作很多。該方案

8、中需要的公開值個數為kt個。隨后Harn提出了一種改進模型7，改進后的模型需要的公開值個數為k(n-t)個，改進方案適用于t的數目近似于n的情況下。但實際上這兩種模型都是一次性模型，并不適合實際應用8，并且公開值的個數也沒明顯的減少。Chien等人9提出了一種基于分組碼的多秘密共享模型，模型中運用單向雙值函數保護秘密份額，保證了該模型的可重用性，在秘密恢復階段通過解n+p-t個方程，秘密可被同時恢復出來。該方案將公開值降低到n+p-t+1個。Yang等人10認為Chien提出的模型雖然減少了公開值的個數，但并非建立在Shamir模型基礎之上。于是他們給出一種基于Shamir模型的改進模型YCH

9、模型，該模型分為兩種情況考慮，當pt時，構建t-1次插值多項式，算法需要n+1個公開值，當pt時，構建p-1次插值多項式，算法需要n+p-t個公開值。此方案同樣利用了雙值單向函數，也同樣通過解方程組來同時恢復所有秘密，因此在秘密恢復階段的時間復雜度與9基本相同。顯然，當pk時，新模型所需的公開值個數少于其他三種模型。另外，新模型在秘密分發階段的時間復雜度小于H模型，而在秘密合成階段，新模型與D模型同為時間復雜度最小的模型。通過實驗進一步對四種模型在計算時間方面進行了分析，可以看出D模型和新模型都為計算時間較少，且穩定性較好的模型，新模型在秘密合成階段的計算時間少于D模型，在秘密合成階段，僅t值

10、很大時新模型的合成時間在小范圍內多于D模型，其他情況下均與D模型基本相同。本文其余部分結構如下：第2節介紹三種模型，給出本文提出的新模型，并對四種模型進行了理論分析；第3節給出實驗數據，并對四種模型在計算時間方面做進一步分析；最后為結論和展望。2 四種模型及其理論分析本文選擇實現的三種模型都利用離散對數的難解性實現秘密份額的保護和驗證，而用不同的方法實現了秘密分發和秘密恢復，因此能夠更好地分析出多秘密共享模型中，由于秘密分發與秘密恢復方法的不同，對整體方案在公開值、時間復雜度等方面的影響。2.1 Z模型此模型在YCH模型的基礎上進行改進，考慮到成員欺騙問題，添加了驗證，不需要單獨開設安全信道。

11、而秘密分發與秘密恢復方法與YCH模型中提出的方法基本相同。方案中p1,p2,pk為k個待保護的秘密。M1,M2,Mn 為n個參與秘密共享的成員。D為秘密分發者。具體方案如下：2.1.1 初始化階段D選擇兩個強素數p和q，計算N=pq；在N1/2,N中隨機選擇一個整數g(g與p,q互素)；發布g,N。每個Mi在2,N中隨機選擇一個整數si作為自己的秘密份額，計算Ri= gsi mod N，并將Ri 和標識號IDi 傳送給D。D必須保證RiRj(MiMj)，否則D要通知Mi重新選擇秘密份額，直到所有Ri都符合條件以后，發布(IDi ,Ri)。2.1.2 秘密分發階段1) D在2,N中隨機選擇一個整

12、數s0，s0與p-1和q-1互素。s0f = 1 mod (N)，計算f；2) 計算R0=gs0 mod N，計算Ii= Ris0mod N，(i=1,2,n)；3) 公布R0 ,f,當kt時隨機選擇素數Q，隨機在0,Q中選擇整數a1,a2,at-k 。用p1,p2,pk,a1 ,a2,at-k做系數，構造t-1階多項式如下：h(x)= p1+p2x+pkxk-1+a1xk+a2xk+1+at-kxt-1 mod Q 計算yi=h(Ii)modQ(i=1,2,n)；公布y1,y2,yn。當kt時隨機選擇大于N的素數Q，用p1,p2,pk 做系數構建k-1階多項式：h(x)= p1 + p2x

13、+pkxk-1 mod Q 計算yi=h(Ii) mod Q (i= 1,2,n),計算h(i)mod Q (i=1,2,k-t),公布 y1,y2,yn, h(1),h(2),h(k-t)。2.1.3 秘密恢復和驗證階段1) Mi計算Ii = R0si mod N，作為自己的子秘密；2) 每個參與秘密恢復的成員都可以驗證其他參與成員給出的子秘密是否有效，如果Ii f = Ri mod N 說明Ii為有效，否則Mi可能有欺騙行為。3) 當kt時，通過(Ii ,yi)構建插值函數如下： = p1+p2x+pkxk-1+a1xk+a2xk+1 + +at-kxt-1 mod Q 當kt時，通過(I

14、i ,yi)和(i,h(i)構造插值函數如下： = p1 + p2x +pkxk-1 mod Q2.2 H模型此模型秘密分發階段將秘密作為插值點構造n+k-t次lagrange插值多項式，秘密合成階段再次使用lagrange插值多項式將k個秘密恢復出來。模型子秘密驗證和安全信道問題的解決方法與Z模型相同。p1,p2,pk,M1,M2,Mn ,D的意義也同Z模型10。DC為秘密恢復者。2.2.1 初始化階段D選擇兩個強素數p和q，計算N=pq；隨機選擇一個大于N的素數Q；在N1/2,N中隨機選擇一個整數g(gp,gq)；發布g,N,Q。每個Mi 在2,N中隨機選擇一個整數si作為秘密份額，并計算

15、Ri=gsi mod N；在k,Q-1中隨機選取IDi作為身份標識，并把Ri 和IDi 發送給D。D要確保RiRj (MiMj)，否則D通知Mi 重新選擇秘密份額，發布Ri ,IDi。2.2.2 秘密分發階段1) D在2,N中隨機選取s0 ，s0與p-1和q-1互素，計算R0=gs0 mod N；2) s0f = 1 mod(N)，Ii = Ris0 mod N，D計算f和Ii，公布f,R0；3)用(0,p1),(1,p2),(k-1,pk),(ID1,I1), (ID2,I2),(IDn ,In)構造n+k-1階多項式：h(x) = a0 + a1x +an+k-1x n+k-1 mod Q

16、 4) 在k,Q-1-IDi |i=1,2,n中依次選取n+k-t個最小的素數d1,d2,dn+k-t，計算并發布h(d1),h(d2),h(dn+k-t)。2.2.3 秘密恢復階段1) 每個參與秘密恢復的成員計算I i =R0si mod N,作為子秘密，并將I i 發送給DC；2) 子秘密驗證階段與Z模型11相同。3) DC用與秘密分發階段相同的方法選取n+k-t個最小的素數d1,d2,dn+k-t，利用(d1,h(d1),(d2,h(d2),(dn+k-t,h(dn+k-t),(ID1,I1),(ID2, I 2),(IDt ,I t)構造lagrange插值多項式如下： = a0 +

17、a1x +an+k-1x n+k-1 mod Q4) 計算pi =h(i-1) mod Q ( i=1,2,k)。2.3 D模型該模型在秘密分發階段運用齊次線性遞歸，將k個秘密與遞歸數列聯系在一起，在秘密合成階段通過lagrange插值得到輔助方程，將遞歸數列和k個秘密恢復出來。模型中驗證階段和安全信道問題同Z和H模型的解決方法相同，M1 ,M2 ,Mn ,D的意義也與Z和H模型相同。P1, P2,Pk 為k個秘密。2.3.1 初始化階段D選擇兩個強素數p1和p2，計算 p1, p2；在N1/2,N中選擇一個整數g ，g的階為素數p(pN)；選擇整數0，構造輔助方程：(x-)t = xt +

18、a1xt-1 + + at = 0 D選擇素數q(qpai (i=1,2,t)，發布N, g, q,。每個Mi 在2,N中隨機選擇整數si作為秘密份額，計算Ri=gsi mod N，并將(Ri ,i)傳送給D。D要確保RiRj (Miz Mj)，否則通知Mi重新選擇秘密份額，發布R1,R2,Rn 。2.3.2 秘密分發階段1) D隨機選擇一個整數f，f和(N)互素，計算s0使其 滿足s0f = 1 mod (N)。2) 計算R0=gs0 mod N，計算Ii=Ris0mod N (i=1,2,n)。3) 構造齊次線性遞歸方程組： 4) 計算ui (tin+k)。5) 計算yi=Ii - ui-

19、1 (tt)時間復雜度秘密分發O(nt) (kt)O(n+k-t)(n+k)2)O(n+k-t)t)O(n+k)t)O(n+k-t)k) (kt)秘密合成O(t3) (kt)O(k(n+k) 2)O(kt2)O(kt2)O(k3) (kt)通過表1可以看出當nk時，D模型和本文模型的公開值個數較少，且此時本文模型更優于D模型。D模型秘密分發階段的時間復雜度最小， H模型在秘密分發階段的時間復雜度最大。在秘密合成階段D模型和本文模型的時間復雜度最小。當t值很大時，Z模型的秘密合成時間復雜度最大，當n值和k值很大時，H模型秘密合成時間復雜度最大。3 實驗與討論實驗環境為Lenovo QiTianM

20、6900；CPU：Inter Core 2 Duo，E7500 2.93GHz；內存：2038MB RAM；編程工具為Microsoft Visual Studio 2008。分別考察成員個數(n)、門限值(t)和秘密個數(k)對四種模型的秘密分發時間(TD)和秘密恢復時間(TR)的影響，并進一步分析四個模型在計算時間方面的性能。Fig.1 secret distrubiting time, t=5,k=5圖1 秘密分發時間，t=5 k=5Fig.2 secret recovering time, t=5 k=5圖2 秘密恢復時間，t=5 k=5首先，分析成員個數n對秘密分發時間和秘密合成時間

21、的影響。圖1給出了此情況下的四種模型的秘密分發時間曲線，可以看出隨著n的增加，Z模型、D模型和本文模型秘密分發時間緩慢增加。H模型的秘密分發時間迅速增加。Z模型、D模型和本文模型在此情況下秘密分發時間基本相同，且均好于H模型。圖2給出了成員個數n對秘密恢復時間的影響曲線。由于k和t不改變，Z模型、D模型和本文模型的秘密合成時間基本不變。此時，t和k的值相同，Z模型、D模型、本文模型的秘密合成時間大致相同，且均好于H模型。綜合對圖1和圖2的分析，在t和k不變且數值較小時，n變換時，Z模型，D模型，本文模型表現較好，H模型表現較差。Fig.3 secret distrubiting time,k=

22、5 n=50圖3 秘密分發時間，k=5 n=50Fig.4 secret recovering time,k=5 n=50圖4 秘密恢復時間，k=5 n=50其次，考察門限值t對秘密分發時間與秘密合成時間的影響。通過圖3可以看出，隨著t的增加，Z模型和本文模型秘密的分發時間緩慢增加，H模型的秘密分發時間迅速下降。開始時由于輔助計算的增多，D模型秘密分發時間緩慢上升，后來隨著t的增加又緩慢下降。當門限值t的值小于40時，D模型所用秘密分發時間最少，此后順次為本文模型、Z模型和H模型。由于H模型的秘密分發時間隨t的增加逐漸減少，當t值增加到40后，所用秘密分發時間逐漸少于Z模型，而t達到43左右，

23、所用秘密分發時間逐漸少于本文模型。圖4展示了門限值t對秘密恢復時間的影響。可見隨著t的增加，D模型和本文模型的秘密合成時間逐漸增加。此時tk，Z模型的時間復雜度為O(k3)，隨著t的增大，Z模型秘密合成時間增加。從時間復雜度分析，Z模型所用秘密合成時間的增加幅度應該與D模型和本文模型基本相同。但實際上Z模型的秘密合成時間隨著t的增加大幅度增加，原因是，Z模型在秘密合成階段需要求解方程組來得到k個秘密，而系數矩陣中有t組行向量為(0,Ii,Iit-1)，因此隨著t的增加需要求解的大數冪方增加，Z模型的秘密合成時間會大幅度增加。從時間復雜度分析，在n和k不變時，H模型的秘密和成時間應該保持不變，但

24、實際上隨著t的增加H模型的秘密合成時間也逐漸增加。其原因是，在秘密合成階段需要t個IDi和n+k-t個di作為插值點的x分量，x分量要進行大量的乘法運算，而ID的值要遠遠大于d的值，因此，t的增加使得H模型的秘密合成時間增加。當t25后合成時間少于D模型，在t45后合成時間少于本文模型。綜合對圖3和圖4的分析，在k和n不變，t變化時，D模型和本文模型表現較好，H模型和Z模型分別在秘密分發階段和秘密合成階段所用時間最多。Fig.5 secret distrubiting time,t=5 n=50圖5 秘密分發時間，t=5 n=50Fig.6 secret recovering time,t=5

25、 n=50圖6 秘密恢復時間，t=5 n=50最后，討論秘密個數k對秘密分發時間與秘密合成時間的影響，結果分別如圖5和圖6所示。從圖5可以看出，隨著k的增加，D模型和本文模型的秘密分發時間以極小的幅度增加。Z模型的分發時間相對前兩種模型，增加幅度較大。此時n值很大，H模型所用的分發時間在開始時就達到400ms左右，隨著k逐漸增加，H模型的秘密分發時間增加幅度非常大。從時間復雜度分析，當kt時，Z模型秘密分發的時間應該少與本文模型，但實際上本文模型所用的分發時間較少。原因是，在分發階段Z模型需要計算h(Ii)，屬于大數，計算開銷較大，而本文模型只需計算h(i)即可。從圖6中可以看出，隨著k的增加

26、，D模型和本文模型的秘密合成時間都增加的非常緩慢，僅由輔助計算的增加引起了合成時間的增加。H模型的增加幅度略比D模型和本文模明顯。由于此時kt，Z模型的時間復雜度為O(k3)，隨著k的增大，Z模型秘密合成時間大幅度增加。從時間復雜度分析，Z模型在此情況下的合成時間曲線應該與僅t變化時秘密合成時間曲線相同。但實際上，顯然當前情況下秘密合成時間較少。原因同樣是Ii 的冪方的計算引起的，在此情況下由于t值很小，大數冪方的計算相對較少，因此所用的合成時間與t變化時相比明顯減少。綜合對圖5和圖6的分析，此情況下D模型和本文模型表現較好。H模型和Z模型分別在秘密分發和秘密合成階段所用時間最多。從以上分析中

27、不難看出，H模型和Z模型都不穩定，都會出現計算時間最多的情況，不是適合于實際應用的模型。在任何情況下，D模型和本文模型下的秘密分發時間和合成時間都相對較少，屬于穩定性較好的模型。在秘分發階段，D模型和本文模型所用時間基本相同，僅當t值很大時，本文模型的秘密分發時間大于D模型，但在實驗范圍內，穩定在200ms之內，仍然好于其他兩種模型。而在秘密合成階段，本文模型所用時間均少于D模型。在秘密分發階段，由于有秘密分發者參與，硬件配置較好，而在秘密合成階段秘密分發者無法參與，考慮到成員組件本身的硬件制約以及秘密恢復的緊急性要求，秘密恢復階段的計算時間應為考慮的重點。因此從計算時間上考慮，在上述四種模型

28、中，本文模型為最優模型。4 結束語隨著多秘密共享的迅速發展，亟需對原有模型在公開值、可驗證性、計算時間等方面進行對比分析，并提出一種更適合于實際應用的優質模型。本文實現了三種已有的可驗證多秘密共享模型，基于Shamir秘密共享提出并實現了一個新的(t,n)可驗證多秘密共享模型。對四種模型在公開值、可驗證性、時間復雜度等方面進行了理論分析，新模型在nk時需要的公開值最少，且秘密合成階段的時間復雜度僅為O(kt2)，好于H模型和Z模型。通過實驗模擬對四種模型，并分析四種模型秘密分發時間與秘密恢復時間隨著n、t和k的改變而變化的情況。分析結果表明新模型在秘密恢復階段所用計算時間最少，在實驗范圍內秘密

29、分發時間也能穩定在200ms之內，僅在t值很大時，秘密分發時間多于D模型。實驗驗證了新模型在計算時間方面優于其他三種模型。下一步將研究動態的多秘密共享方案，即參與者集合可以動態變化，而無需重新分配秘密份額仍能保證秘密共享模型的可用性和安全性的方案。參考文獻:1 A.Shamir, How to share a secret, Communications of the ACM 22 (11) (1979) 612-613.2 G.Blakley, Safeguarding cryptographic keys, Proc.AFIPS 1979 National Computer Confere

30、nce, AFIPS Press, New York, 1979,pp. 313-317.3 劉木蘭，張志芳著。 秘密共享體制和安全多方計算。電子工業出版社2008年2月第一版。4 Blundo C.,De Santis A.,Di Crescenzo G.,Giorgio Gaggia A.,Vaccaro U. Multi-secret sharing schemes, Advances in Cryptology CRYPTO94,Y.G.Desmedt,ed.,Lecture Noters in Comuputer Science 839, pp.(1994),150-163.5 W.

31、-A.Jackson, K.M. Martin, C.M. OKeefe, On sharing many secrets, Asiacrypt94 917 (1994) 42-54.6 J. He, E. Dawson, Multistage secret sharing based on one-way function, Electronics Letters 30 (19) (1994) 1591-1592.7 L. Harn, Comment: Multistage secret sharing based on one-way function, Electronics Letters 31 (4) (1995) 262.8 T.-Y.Chang, M.-S.HWang, W.-P.Yang, A new multi-stage secret sh