一種動態（ｔ，ｎ）門限多重秘密共享方案

摘要:針對現有的門限秘密共享方案在處理參與者集合動態變化時靈活性差和許多多重秘密共享方案不能一次恢復出多個秘密(需要進行很多輪的計算)這兩個缺點，提出了一個新的方案，給出了一個簡單實用的Lagrange插值的方法。該方案可以動態添加或刪除參與者，無須重新分發子秘密，參與者的子秘密由自己選取和保存，可以在不安全的環境中傳送;同時公開的只是子秘密的影子，子秘密可以重復再用，在秘密的恢復階段可以一次恢復多個秘密。

關鍵詞:秘密共享;多重; 動態; 拉格朗日插值多項式; 安全性

中圖分類號:TP309文獻標志碼:A

文章編號:1001－3695(2008)02－0516－02

自第一個(t，n)門限秘密共享方案在1979年被Shamir[1]和Blakely[2]分別獨立地提出以后，由于其廣泛的實際應用前景，眾多學者投入了許多精力，對其本身及相關問題進行了大量深入的研究，并取得了一大批研究成果。(t，n)門限秘密共享方案中，一個(或多個)秘密被分成n份，分別給n個參與者，當n個參與者中有t個或多于t個合作時，可以恢復出共享的秘密;而少于t個參與者，將他們的子秘密放在一起卻得不到有關秘密的任何信息。

許多學者對于秘密共享進行了大量的研究，提出了許多很好的秘密共享方案[3~12]，如有效的多秘密共享方案[5~7]#65380;可驗證的門限秘密共享方案[8~11]#65380;一般接入結構上的秘密共享方案[12]等。但這些方案的缺點是:a)子秘密分發階段和秘密恢復階段量子秘密的選擇是由分發者D一個人完成并發送給參與者，要求發送數據必須在安全信道中進行，這樣不利于子秘密的保管，也不能防止秘密分發者的欺騙[4]。b)當參與者集合動態變化時，必須重新分發子秘密，尤其是當參與者中有人離開時，處理比較麻煩。例如一個單位給每位員工分發一個子秘密，用于在該員工參加的項目組內共享秘密。當公司有新成員加入時，只需給新加入者分工分發一個子秘密，用于在該員工參加的項目組內共享秘密;但當某個員工中途從一個項目中撤出或從公司辭職時，公司面臨保換所有相關員工的子秘密，工作量太大，可操作性差[4，8]。c)在共享多個秘密時，不能一次恢復出來，需要多次重復秘密的分發和恢復過程[3]。d)在防止欺詐時，必須有一個專門的驗證協議[7~11]，增加了方案的復雜性。 這些問題可能在某一篇文章中得到了解決，但沒有全部都解決。基于一般接入結構上的秘密共享[12]可以解決參與者集合動態變化的問題，但其運算代價太大。為實現動態(t，n)門限秘密共享，需要重復Ctn次Lagrange插值，當n比較大時，計算量太大。

本文基于RSA體制的安全性[13]和離散對數問題的難解性[13]，提出一個動態的多重秘密共享方案。該方案可以抵御不誠實的參與者，無須專門的驗證協議，相對于一般接入結構上的方案計算量小#65380;便于實現。

1方案的構成

1.1初始化階段

1.1.1參數設置

設{K1，K2，…，Kk}為要共享的秘密， U={U1，U2，…，Un}為參與者集合。本方案需要一個公告牌發布消息，公告牌上的內容只有可信的秘密分發者D可以發布和修改，其他人只能閱讀和下載。可信的秘密分發者D選定兩個強的大素數p和q，計算乘積N=pq，對它們的要求同RSA體制的安全性要求，即攻擊者在知道N的情況下想要得出p和q在計算上是困難的，這是保證整個秘密共享體制安全性的關鍵。可信的秘密分發者D在[N1/2，N]中隨機選取一個g滿足g[p-1)(q-1)]/2]≡1 mod N，然后任意選取一個大于N的素數Q，在公告牌上公布{N，g，Q}。

1.1.2子秘密的選取

每個參與者Ui(i=1，2，…，n)從[2，N]中隨機選取Si作為自己的子秘密，計算Pi=gsi mod N。同時每個參與者Ui從[k+1，Q-1]中隨機選取ui作為自己的公開身份特征IDi(這里ui是公開的，所以每個參與者可以保證自己的公開身份特征ui與別人的不同)。Ui將Si妥善保存好，將Pi和ui發送給可信秘密分發者D。Si 將是整個系統中參與者需要保密的惟一信息。這時，分發者D需要判斷是否存在:當i≠ j時，Pi≠Pj是否成立。 若有某個Pi=Pj，分發者D通知Ui#65380;Uj重新選取子秘密Si和Sj，并計算和發送Pi#65380;Pj。在確認沒有沖突之后，分發者D將所有參與者的(ui，Pi)(i=1，2，…，n)對發布到公告牌上。

1.2秘密分發階段

在這一階段，可信分發者D將計算并公布一些信息，無須參與者交換任何秘密信息，即這一階段的工作由可信分發者D單獨完成。當參與者中≥t個合作就可以恢復個秘密，而

2方案分析

本方案具有動態處理參與者集合的變化能力，在不重新分發子秘密的情況下共享新的秘密，不影響安全性。

a)當某個參與者(不妨設為Uj)離開參與者集合時，在一般情況下往往需要重新選擇密碼和其他參與者的子秘密，工作量較大。但在本方案中，因在整個過程中，在公告牌上的內容除了可信分發者D選擇的信息外，只有每個參與者的公開身份特征和他們的子秘密的影子，只需讓可信分發者D更改公告牌上的{N，g，Q};在作Lagrange插值多項式時次數減少一次，公布的公開信息中減少f(dj)，其余n-1個參與者不必更新子秘密。這樣，在新的參與者集合U-{Ui}中重新形成了一個(t，n-1)門限方案。

b)當某個新的參與者(不妨設為Un+1)加入到參與者集合中時，Un+1補充初始化過程:選擇子秘密Sn+1計算并提供Pn+1。如果Pn+1與現有的某個Pi(i=1，2，…，n)相同，可信分發者D要讓Un+1重新選擇Sn+1計算并提供Pn+1。之后的過程與a)相類似，重新形成了一個(t，n+1)門限方案。

3方案的安全性分析

a)本方案是一個(t，n)門限方案。由秘密的分發過程和恢復過程中多項式的構造可以看出，n個參與者中t個或多于t個人合作可以恢復出k個秘密，且是一次可以恢復出個k秘密;少于t個人合作則恢復不出秘密(因為少于t個條件不能重構k+n-1次多項式)。

b)可以抵抗參與者的欺騙，并且無須專門的驗證協議。在1.3節的步驟b)，任何人均可以驗證S′hi≡?Pi(mod N)是否成立來判斷參與者是否存在欺騙行為。

c)從公開的h#65380;N，得到S0，進而計算PS0i mod N難度相當于破解RSA體制。

d)該方案中每個參與者Ui的子秘密Si是由參與者自己選取和保管的，秘密分發者和恢復者由公告牌中公開的信息不能得到每個參與者Ui的子秘密Si，只能得到子秘密的影子S′i=PSi0 mod N，由S′i和P0計算Si是離散對數問題。當參與者集合變化時，處理方便，無須重新分發子秘密，減少了分發者D的計算量;而且還可以保護子秘密。

e)由秘密分發和恢復過程可以看出，秘密分發者#65380;秘密恢復者以及參與者的數據傳送不一定要求在安全信道中進行，在不安全信道中也可以，所以本方案的實用性較好。

4結束語

本文針對以前門限共享方案在處理參與者集合動態變化時的不足，提出了一個多重門限秘密共享方案。與傳統的門限方案相比，該方案中參與者的子秘密是自己選取的，秘密分發者和恢復者得到的只是子秘密的影子信息。該影子公布在公告牌上，任何人不能由影子得到參與者的子秘密，可以更好地保護子秘密。而且該方案可以防止不誠實參與者的欺騙，在恢復多個秘密時，可以一次恢復。基于Lagrange插值多項式的算法，使方案有較強的實用性。

參考文獻:

[1]SHAMIR A.How to share a secret [J]. Communications of the ACM， 1979， 22(11): 612－613.

[2]BLAKLEY G R. Safeguarding cryptographic keys[C]//Proc of the National Computer Conference.New York: AFIPS Press， 1979: 313－317.

[3]黃東平，王華勇，黃連生，等. 動態門限秘密共享方案[J]. 清華大學學報:自然科學版，2006，46(1):102－105.

[4]PANG Liao－jun， WANG Yu－min.A new(t，n)multi－secret sharing scheme based on Shamir’s secret sharing[J]. AppliedMathematics and Computation， 2005，167:840－848.

[5]HARN L. Efficient sharing (broadcasting) of multiple secret [J].IEEE Proc Comput Digit Tech， 1995，142(3):237－240.

[6]HE J， DAWSON E. Multistage secret sharing based on one－way function [J]. Electron Lett，1994， 30(19): 1591－1592.

[7]許春香，肖國鎮.門限多秘密共享方案 [J]. 電子學報， 2004，32(10):1688－1689.

[8]劉鋒，張建中.一類新型的門限分享方案的設計與分析[J].計算機應用研究， 2006，23(1):96－97.

[9]劉鋒，張建中. 一個完善的可公開驗證秘密分享方案[J].計算機應用研究， 2006，23(6):96－97.

[10]CHOR B， GOLDWASSER S， MICALI S， et al. Verifiable secret sharing and achieving simultaneity in the presence of faults[C]//Proc of the 26th IEEE Symposium on the Foundations of Computer Science (FOCS).New York: IEEE Press， 1985: 383－395.

[11]STADLER M. Public verifiable secret sharing[C]//Proc of Advances in Cryptology－EuroCrypt’96.Berlin: Springer－Verlag， 1996:190－199.

[12]張福泰.可驗證秘密分享及其應用研究[D].西安:西安電子科技大學，2001.

[13]STINSON D R.密碼學理論與實踐 [M].馮登國，譯.2版.北京: 電子工業出版社， 2003.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”