畢業(yè)論文《幾種秘密共享方案的研究》

1、分類號:tp391udc： 681密級：不保密 學校代碼：11065碩士學位論文幾種秘密共享方案的研究指導老師 學科專 業(yè)名稱 論文提交日期摘于佳副教授計算機軟件與理論2011 年 5 月 12 h秘密共享是保護信息和數(shù)據的重要手段，它主要用于保護重要信息和數(shù)據，以 防止重要信息的丟失、毀壞和篡改。秘密共享已經成為密碼學研究的一個重要分支, 同時也是信息安全方向的重要研究內容。本文首先介紹了秘密共享的研究現(xiàn)狀，然 后在此基礎上提出了幾種安全、有效的秘密共享方案。木文的主要工作表現(xiàn)在以下 幾個方面：可公開驗證秘密共享是一種特殊的秘密共享，由分發(fā)者分發(fā)的秘密份額不僅能 被份額持有者自己驗證，而且可

2、以被其他任何成員驗證。然而，對于一般的可公開 驗證秘密共享，敵手可能使用很長的時間，攻破門限個份額服務器，獲得秘密。為 了解決這個問題，提岀了第一個具有前攝能力的可公開驗證的秘密共享方案，不僅 能夠可公開驗證份額的正確性，而且具有份額定期更新的性質，這使得方案比其它 一般可公開驗證秘密共享方案更安全，能夠更好地滿足各種應用的安全需求?；邶R次線性遞歸提出了一個新的多秘密共享方案，然后，將其擴展成一個可 驗證的方案。在秘密分發(fā)過程中，只需公布很少的公開參數(shù)，在秘密重構過程中， 每個成員只需提供偽份額,不會暴露秘密份額，當秘密更改吋，不需重新分配秘密份 額，實現(xiàn)了秘密份額的多次使用。提出的方案具有

3、秘密份額可以多次使用、公開的 參數(shù)少以及所要重構多項式的次數(shù)小的優(yōu)點，這使得方案更高效，能夠更好地滿足 各種應用需求。基于元胞自動機原理提出了一種無可信任屮心的多秘密共享方案，它和一般的 基于元胞自動機的多秘密共享方案不同的是，份額的分發(fā)不需耍分發(fā)者的參與，能 夠滿足沒有分發(fā)者的情況下也能夠實現(xiàn)秘密份額的分發(fā)，這使得這種方案能得到更 廣的應用。關鍵詞：秘密共享；可公開驗證；齊次線性遞歸；元胞自動機abstractsecret sharing is an important tool for protecting the information and data. secret sharing

4、is used for protecting important information and data from being lost, destroyed or falsified secret sharing hasbeen one important branch of cryptography and one important research field of information security. this article illustrates the research advances of secret sharing technology, based on wh

5、ich several secure and efficent secret sharing schemes are proposed this article has finished the following work:a publicly verifiable secret sharing (pvss) scheme is a special secret sharing scheme in which the shares distributed by the dealer can be verified not only by shareholders themselves but

6、 also by any other party. however, in a normal publicly verifiable secret sharing scheme, an adversary may get the secret by attacking threshold shareholder servers for a long time. in order to deal with this problem, a publicly verifiable secret sharing scheme with proactive ability is newly propos

7、ed, which not only can publicly verify the validity of shares, but also has the property of periodically renewing shares. this makes the proposed scheme more secure than other common publicly verifiable secret sharing schemes, and makes it better satisfy security demand of various applications.a new

8、 multi-secret sharing scheme based on homogeneous linear recursion is proposed, and then it is converted into a verifiable scheme. in the distribution phase, very few of public values are needed to publish in the recovery phase, each participant only needs to submit a pseudo shadow instead of his se

9、cret shadow, and his secret shadow cannot be disclosed when secrets are changed, secret shadows don't need to be redistributed, which makes secret shadow able to be used multiple times. the proposed scheme has many advantages, for example, the secret shares can be used multiple times and the sch

10、eme publishes very few parameters as well as the reconstmcted polynomial has a low degree. this makes the proposed scheme more efficient. therefore, it better satisfies demands of various applications.a multi-secret sharing scheme without a trusred party based on cellular automata is proposed it is

11、different from the other multi-secret sharing scheme based on cellular automata, because share distribution does not need dealer. this scheme can also distribute share without dealer. this makes the proposed scheme apply widely.key words: secret sharing; publicly verifiable scheme ； homogeneous line

12、ar recursion ； cellular automata1.1秘密共享的研究意義1.2木文的研究內容和取得的成果11.3本文的組織2第二章 相關工作的研究現(xiàn)狀 32. 1秘密共享32.2可驗證秘密共享(vss) 42. 2. 1 feldman的可驗證秘密共享方案(vss) 42. 2.2 pedersen的可驗證秘密共享方案(vss) 52.3可公開驗證秘密共享(pvss) 72. 3. 1 schoenmakers的可公開驗證秘密共享方案72. 3.2 stadler的可公開驗證秘密共享方案92. 4 先應秘密共享(proactive secret sharing) 102.5多秘

13、密共享132. 5. 1 yang等的多秘密共享方案142. 5.2 shao等的可驗證多秘密共享方案162. 5.3 dehkordi等的可驗證多秘密共享方案172. 5.4 dehkordi等的基于齊次線性遞歸的多秘密共享方案182. 5.5龐遼軍等的多秘密共享方案202. 5.6 eslami提出的基于一維元胞自動機的可驗證多秘密共享方案212.6小結23第三章具有前攝能力的可公開驗證秘密共享243. 1預備知識243. 1. 1符號定義243. 1.2模型和假設243.2提出的具有前攝能力的可公開驗證秘密共享方案253. 2. 1 初始化(init) 263. 2.2私密鑰更新協(xié)議(p

14、ku) 263. 2.3秘密份額更新協(xié)議(sku) 273. 2.4指控核實協(xié)議(acc) 283. 2.5損壞秘密份額發(fā)現(xiàn)協(xié)議(bsd) 283. 2.6恢復損壞秘密的份額(ssr) 283.3安全性分析和相關工作比較303.4結論31第四章 基于齊次線性遞歸的可驗證多秘密共享方案324. 1齊次線性遞歸的定義324.2基于齊次線性遞歸的多秘密共享方案334. 3可驗證多秘密共享方案354.4安全分析384.5相關工作的比較394.6結論40第五章基于元胞自動機的無可信任中心的多秘密共享方案415.1 一維存儲元胞自動機415.2基于元胞自動機的無可信任中心的多秘密共享方案425. 2. 1

15、符號說明425. 2.2提出的方案425. 3安全分析445.4相關工作的比較445. 5結論45第六章 總結與展望46參考文獻47攻讀碩士學位期間的研究成果51致謝52學位論文獨創(chuàng)性聲明53第一章引言當今社會，隨著計算機網絡技術的快速發(fā)展，特別是internet的廣泛應用，人 們的日常生活發(fā)生了巨犬變化，人們利用網絡可以進行網上購物、發(fā)送電子郵件以 及進行遠程教育等。與此同時，網絡也給人們帶來了信息安全問題，如黑客攻擊等。 因此，如何保證信息的安全性已成為當今社會十分緊迫的問題，信息安全無疑已成 為信息科學領域的重要課題。從而對信息安全方面的研究會帶來廣泛的應用價值。 密碼學結合了信息科學、

16、計算機科學和數(shù)學等多門學科為一身，它實現(xiàn)了對信息保 密功能，保證了信息的完整性，有效地防止信息的篡改。秘密共享作為密碼體制的 基礎，已經吸引了很多學者進行研究。1.1秘密共享的研究意義秘密共享是把秘密進行分割，而分割后的毎一部分叫做份額（或者子密鑰），并 把這些份額分發(fā)給不同的成員，只有多于特定個成員一起合作才能計算出秘密，jflj 少于特定個成員合作時，得不到有關秘密的任何信息。所以，當有少于特定個成員 都提供秘密份額時，他們也不能得到真正的秘密。相反，當有某兒個成員的份額由 于某些原因損壞，只要剩余的成員個數(shù)多于特定個，剩余的成員也能夠得到秘密。 可見，把秘密分發(fā)給多個成員不僅有利于保護秘

17、密的安全性，而且還能夠保證秘密 的完整性，進一步提高了整個系統(tǒng)的安全性與健壯性。秘密共享技術在密鑰管理、銀行網絡管理以及數(shù)據安全方面有著非常廣泛的應 用。另外，秘密共享在數(shù)字簽名、身份認證等方面也有廣泛的應用。1.2本文的研究內容和取得的成果本篇論文主要研究了幾種秘密共享方案，并取得了以下成果：（1）提出了一個具有前攝能力的可公開驗證秘密共享方案，攻擊者不斷攻擊同一 個方案時，如何保證方案的安全性問題，提出的具有前攝能力的可公開驗證 秘密共享方案，不僅能夠可公開驗證份額的止確性，而且貝有份額定期更新（前攝）的性質，使得敵手在前一個時間段獲得的份額，在當前時間段中完 全失效，這使得方案比其它一般

18、可公開驗證秘密共享方案更安全，能夠更好 地滿足各種應用的安全需求。（2）基于齊次線性遞歸的思想，提出一種可驗證多秘密共享方案，只需公布很少 的公開參數(shù)，每個成員只需提供偽份額，而不需暴露秘密份額，當秘密更改 吋，不需重新分配秘密份額，實現(xiàn)了秘密份額的多次使用。這樣，秘密份額 可以多次使用、公開的參數(shù)少以及所耍重構多項式的次數(shù)小的優(yōu)點，這使得 方案比其它一般的可驗證多秘密共享方案更高效，能夠更好地滿足各種應用 需求。（3）提dr了基于元胞自動機的無可信任屮心的多秘密共享方案，由于使用了一維 元胞自動機的原理，所以在重構秘密時，不需耍計算拉格朗日多項式，這樣 就大大減少了運算量，另外，份額的分發(fā)不

19、需要分發(fā)者的參與，所以能夠滿 足不需要分發(fā)者的情況下也能夠完成秘密共享的要求。1.3本文的組織本文的組織結構如下：第一章是引言部分，介紹了秘密共享的研究意義、研究內容、取得的成果以及 本文所做的工作等。第二章介紹了一些秘密共享的研究現(xiàn)狀，主要包括：秘密共享、可公開驗證秘 密共享、具冇前攝能力的秘密共享、多秘密共享、可驗證多秘密共享、基于元胞自 動機的多秘密共享等的一些基本思想及研究狀況。第三章捉出了一個具冇前攝能力的可公開驗證秘密共享方案。方案的基本思想 是能夠對子密鑰進行周期性的更新，當重構者成員利用這些更新后的子密鑰重構秘 密與利用更新前的子密鑰重構的秘密相同，方案還能夠對子密鑰正確性的進

20、行檢測, 一旦發(fā)現(xiàn)有錯誤的子密鑰還能夠對錯誤子密鑰進行恢復。第四章捉出了一種新的可驗證多秘密共享方案，該方案基于齊次線性遞歸，使 得在保證不增加多項式次數(shù)的情況下，公開的參數(shù)更少。第五章主要對基丁元胞自動機的無可信任屮心的多秘密共享方案進行研究，文 屮對方案的安全性進行了分析以及與相關工作進行了比較。第六章全文的總結與展望，概括全文的研究內容以及創(chuàng)新點，并對未來的工作 提出了一些設想。第二章 相關工作的研究現(xiàn)狀2.1秘密共享密鑰的安全關系著整個系統(tǒng)的安全，傳統(tǒng)的密鑰保存方法是把密鑰交給一個人 管理，這樣做存在很多缺陷：首先，當密鑰持有者不小心泄露了密鑰，那么就會對 整個系統(tǒng)帶來危害；其次，密鑰

21、持冇者丟失或損壞了密鑰，整個系統(tǒng)中的信息就無 法使用。為了解決上述問題，我們可以把密鑰分發(fā)給多個人共同持有，這樣人們就 提岀了秘密共享的思想。秘密共享是一種分發(fā)、保存密鑰的方法：將密鑰分成多個 相互關聯(lián)的秘密信息（稱為份額、影子或子密鑰）然后再分發(fā)給小組中的所有成員, 使得小組中的每個成員拿出他們的份額根據既定的方法就口j以重構出密鑰。每一個 根據既定方法都能計算出密鑰的小組稱為授權子集，而其他子集稱為非授權子集， 非授權子集不能恢復出秘密。如果對于每個非授權子集都不能恢復出秘密，那么就 稱為完美的秘密共享。可見，即使某幾個（少于特定個）份額持有者泄露了自己的 份額，曲于攻擊者不能得到特定個份

22、額，他也不能重構出秘密，另外，當某幾個（少 于特定個）份額持有者丟失或損壞了份額，仍然可以恢復出秘密。在實際應用中， 使用秘密共享方案可以防止密鑰的丟失、損壞或攻擊，能夠很好地保證密鑰的安全 性與完整性。秘密共享方案最早由shamir1和blakley提出，其中shamir提出的 基于拉格朗口插值的秘密共享方案是一種比較簡單、實用的方案，下面將簡單介紹 一下shamir的門限秘密共享方案。shamir的方案屬于（t,力）門限秘密共享方案,即刀個份額持有者成員中的任 意力個冇效成員都能重構出秘密，假設群體戶（丨円二/7）中的各成員記作p,（l<i<n）, 秘密份額分發(fā)者記作/（dea

23、ler）,要分發(fā)的秘密是s, q是大素數(shù)，z。是模q的域。秘密份額分發(fā)階段：首先,分發(fā)者在域乙上任意選擇一個次數(shù)最多是t-1次 的多項式/（x）=工cijxmod（7，使得a（=s ,而a, gr zq。然后,分發(fā)者d再隨機選j=0擇n個非零的、互不相同的數(shù)無，其屮兀<乙（1。匕力，對所有的f計算si = f（xj） mod<7 o最后，分發(fā)者將£秘密地傳送給成員pj,并公開兀，s就是成員pt 的秘密份額。秘密重構階段：任意廣個成員合作可以重構出秘密。假設由任意方個成員組成的集合b = a,&, (|b|=r),根據拉格朗日插值多項式計算出/(x):mod <

24、;7ieb其中g,(x)= f三乂 mog，于是秘密s就是jebi xj xj$ = /(0)=匸£ mod<7ieli其中 cbi = h modq。jebi xj _ xj2.2可驗證秘密共享(vss)為了解決分發(fā)者的誠實性問題和參與者成員的誠實性問題，提出了可驗證秘密 共享(vss)o文獻首先提出了可驗證秘密共享，而feldman<和pedersen提出的 可驗證方案受到了更多密碼研究者的青睞，他們的方案屮，分發(fā)者不僅要分發(fā)各成 員的份額，而且還公布對多項式系數(shù)的承諾，使得各成員在接收到份額吋，可以驗 證自己的份額正確與否，同樣，在秘密恢復階段，當秘密重構者接收到其

25、他成員的 份額吋，他也可以用同樣的方法驗證其他成員是否提供了正確的份額。若各成員在 驗證份額正確性吋，不需要和他人交換信息，這種驗證方案就是非交互的，反之， 就是交互的。下面主要介紹feldman-vss方案和pedersen-vss方案，前者在計算上是安全的, 后者在信息論上是安全的。2.2. 1 feldman的可驗證秘密共享方案(vss)參數(shù)設置：dq都是大素數(shù)且有引(礦1)，q是z；中唯一的q階乘法了群，秘 密是s,隨機選取gwgq。fel dman的可驗證方案:(1) 分發(fā)者d隨機選擇多項式f(x) = ylcijxj mod(7 ,滿足aq=se z(j ,；=oaj w zqlj

26、 = l,.,r-l) o(2) 分發(fā)者計算=(i = l町，并把®通過秘密通道發(fā)送給成員£。7=0(3)分發(fā)者計算承諾ej = q mod/?(y = o.r-l)并廣播。(4) 成員用接收到耳和廣播的色后，計算下式是否正確來確定份額的正確性:宀n(q mod p2-(1)j=0(5) 任意廣個成員的集合拿出他們的份額，利用拉格朗h插值計算s：s = si-cbj modg2-(2)iwb其中cb嚴丄 ,然后根據公開信息來驗證s的正確性: i-ieo = g s mod p o事實上，式2-(1)之所以成立是因為： ft©)" modp = y(gaj

27、y' modpj=oy=o=g工冃"mod p=g"' mod p o2. 2. 2 pedersen的可驗證秘密共享方案(vss)參數(shù)設置：p，a為大素數(shù)且引("1),記z；中唯一的q階乘法子群為q。秘密 swzg,隨機選取g.he kg(,任何人都不知道log'。承諾的實現(xiàn)：首先選取ke rz“然后計算承諾e(s,k) gshk modp ,公開e(s,t) o可驗證秘密共享方案如下:(1)分發(fā)者d隨機選擇多項式f(x) = yyajx，modq并口滿足ag = s ,；=od/w =,然后計算5； = /(/) (/ = !,.,/?

28、) o（2 ）分發(fā)者d隨機選擇多項式（x） = pf/?7x7 modg并且滿足b°=k , j=o巧 wzq（j = l,-1）,然后計算kt = g（i） （z = l,.,n） o（3）分發(fā)者秘密地將（環(huán)出）發(fā)送給成員用，并廣播對多項式系數(shù)的承諾ej =（丿=1,1） o2-（4）成員£接收到©水）后，可根據下式來驗證份額的止確性：gsi 臚三modp)=o（5）任意廣個成員的集合拿出他們的份額（巧心），可用拉格朗插值計算秘密s 和參數(shù)a：s =工（耳 gj mod g ,ieli2 =工（匕。）modgiwb/y.其中cbi = tj -mod <7

29、 ,通過下式來驗證s的正確性：林® 一斥e（s,k） = gshk mod p2-（4）事實上，式2-（3）z所以成立是因為：modp二modpy=0j=0=modp=g " 'hk, mod p o很顯然，以上兩種方案都是非交互式vss方案，在秘密分發(fā)過程屮，不需要分 發(fā)者和參與者成員的交互，以及各成員之間的交互，所以是一種比較高效的vss方 案，但是在實際應用屮，比如電子選舉和可撤銷匿名性的電子支付協(xié)議屮，各成員 不僅耍知道自己的份額是否正確，而h還耍知道其他成員的份額是否正確，可公開 驗證秘密共享解決了這一問題。2.3可公開驗證秘密共享（pvss）文獻心和文獻

30、分別是schoenmakers和stadler的可公開驗證的秘密共享方案, 下而分別介紹這兩種方案。2. 3. 1 schoenmakers的可公開驗證秘密共享方案參數(shù)設置：p，g為大素數(shù)且引（"1）,記z；中唯一的g階乘法了群為q,分發(fā) 者將一個形式為g，的秘密s （即s = g$）在門個成員屮分發(fā)，各成員收到其加密 子密鑰（也叫加密份額）g5）,其屮兀是成員用的私有信息，故只有成員用自己才 能從g"®中解密出g"）。初始化階段：設g, &是獨立選擇的群g“中的兩個生成元，所以沒有人知道呂相對于6、的離 散對數(shù)。各成員用隨機選擇一呂jz；作為其

31、私鑰，而將y產g勺mod/,作為其公鑰。秘密分發(fā)階段：分發(fā)者隨機選取ssz*并將sr作為秘密分發(fā)給刀個成員。分發(fā)者首先 構造一個次數(shù)最多為次的多項式/x兀）=£勺0 其中s = a0,a' e kz（/j=o分發(fā)者公開對系數(shù)的承諾和加密子密鑰：q = g“'modpj = 0,l,，/ 1 ,yi = y/0） modpj = 1,2,/?最后令xf =仃cj mod p o；=o分發(fā)者要用知識證明來證明x的有效性、一致性，即滿足：xj = gl）l） mod p ,乙=）/（/） mod p對于每個沱1,2,/,分發(fā)者隨機地選取mae rz（并計算:au = g呵

32、modp.a2i =)叮 modp,ie 1,2,/!利用hash函數(shù)計算c如b ：2-c = h(x| x x yn a其中“ ”是指兩個比特串的連接，ibsh函數(shù)具有單向性，即由結果c推不出x：,乙,9 2i °計算* = wj -p(i)c mod/? o分發(fā)者d公布所構造的證據proof。=2,斤迅,.,片j。子密鑰驗證階段：驗證者利用公開信息c.(0< 7<r-l)計算x=nc/ modp,然后再利用x，e，c(1gs)及c驗證各成員收到的加密子密鑰是否有效。首先計算dh = g"x： modp,a2i = modpje 1,2,/?然后代入2-(5)

33、式驗證是否成立。若成立，則說明分發(fā)者分發(fā)的加密子密鑰有 效，反z,則無效。秘密恢復階段：成員e利用私密鑰兀計算子密鑰modp,然后將s,和proof,公布以證明s確實是從匕中解密出來的，也就是說£向所有人說明他知道某個兀使得=gxi s；1 mod p , proof,的構造和 proof。的構造一樣。若至少有方個成員已恢復了密鑰sgb),利用拉格朗日插值函數(shù)計算s：2-事實上iis/ mod p = n（g（） ）5 mod pieb*=1=g z mod p=g" mod p=gs mod p=s其中。=11沖土。2.3.2 stadler的可公開驗證秘密共享方案參數(shù)設

34、置：p，q為大素數(shù)且引（"1）,記z；屮唯一的q階乘法子群為q,設刃力是獨立選擇的群q中的兩個生成元，所以沒有人知道g相對于力的離散對數(shù)。分發(fā)階段：（1 ）分發(fā)者d隨機選取多項式/（x） = £°x mod<7 ,滿足a0=se z（f , j=oaj.e z（/（j =,然后計算=/（7）。（2）各個成員£任意選取自己的私密鑰 gzq并且公開他的公共密鑰yi - h：l mod p 0（3）分發(fā)者任意選取grzq計算仏即=理,家艸）。令匕=曠mod p ,那么v, =于是（a,鄧）=（護,gk）,若示證者給出的色是錯誤的,那么他構造的數(shù)v能寫成廠

35、咱的形式的概率是很小的。示證驗證階段：（1）分發(fā)者任意選取 g r z（/，計算 tfli=hw, mod/?, q = gvj = 1,./,計算r=（斤，山）=側-cm% -q,，叫-c：0）,其中c;表示下式中的第i比特位,c = hn(y % k a b b2 . b“ f )2-（2）驗證者利用已知的計算:th = hr,aci mod p ,將他們代入式2-（7）驗證是否成立，若成立，說明分發(fā)者分發(fā)的份額是正確，反之, 則說明分發(fā)的份額是錯誤的。其中叫modp_ gy；ii當q=0時獲取份額階段：成員用利用已知的（a,bj和口己的私密鑰&計算份額:川仏廿/（于*）2. 4

36、先應秘密共享（proactive secret shar ing）秘密共享、可驗證秘密共享和可公開驗證秘密共享都能很好的提高密鑰的安全 性。但有些長期使用的密鑰（如&的密鑰），如果受到敵手長期不斷的攻擊，敵手 就有可能逐-的攻破多個服務器成員，那么就有可能重構出密鑰。先應秘密共享很 好地解決了上述問題，它是通過周期性的更新所有成員的份額，如果敵手在一個時 間段內沒有攻破足夠多（多于門限）的份額，那么在下一個時間段他得到的份額信 息完全失效，使得秘密信息更加安全。一個吋間段一般都是比較短的吋間，而利用 新份額重構重構出密鑰保持不變。ostrovsky第一次在語境安全系統(tǒng)屮提出了動態(tài)敵手模

37、型，文獻比較系統(tǒng)全 面的給出了如何解決密鑰的永久泄露問題，文獻塚是一個可公開驗證的先應秘密共 享方案。下面主要介紹一下herzberg的先應秘密共享方案。初始化階段：分發(fā)者把秘密x分成刀份召,兀,分發(fā)給每一個成員p），每個£持有忑，其中xi = /（，） =工勺卩，尤=兀（）=兔。bj（i = 1./）是記錄非法成員的集合，初始值 j=obi=e。成員片生成其公私鑰對(©,勺)，他自己隱藏厲，廣播公鑰勺。每個用都擁有(0)一個集合兒=g j modp,(j = l.m) o私密鑰更新協(xié)議：此協(xié)議在了密鑰更新協(xié)議和了密鑰重建協(xié)議z前運行，運行如2成員弓首先選擇新的公私鑰對(%

38、，甲)并廣播硏，然后用2)簽名労)并廣播, 其他成員用驗證p對羅)的簽名。子密鑰更新辦議：式子/(m)(0) = x中的l1表示在第l1個周期。我們可以構造一個次數(shù)是&的 多項式炎)，其中沢0) = 0,那么 嚴(0) = /(/-,)(0) + (0) = % + 0,每個成員的子密鑰 %,)=/(/)(?)=廠-|)+ 5(。mod0 o構造5()=() +萬() + +硏()mod p ,其中"()是每一位成員pj自己構造的次 數(shù)為斤的常數(shù)項為0的多項式，也即q(0) = 0 o在t時期可驗證子密鑰更新協(xié)議如下：(1) £任意構造多項式(2)= 憶1+莎2”+

39、 + "” 計算£im =g3im modp(2) 弓計算w,7=(j) mod/?, jg, 夠=encju,巧幻 表示對知加密。(3) 礦播ussy =(從,他仏“,他人“)，sqssf)及其(7 = 1.n) o(4) 對每個成員用接收到成員什發(fā)送的信息后，驗證下式是否成立：mod p2-z=i(5) 如果經成員弓驗證所有信息都是合法的，他就會向其他人廣播說“他得到的信 息是正確的”。若不正確執(zhí)行指控核實協(xié)議。(6) 如果所冇服務器收到的信息都是正確信息，那么他們會各自更新自己的份額兀二+(%+ + %)modg , 并計 算 y(j =ga，i modp , gh=

40、n吧gfq(g o乃)并銷毀兀及其它接收到的冇關信息。iwa-e(7) 若有成員發(fā)現(xiàn)某個成員給他發(fā)送的信息不正確，他將有兩種處理方法，其一： 不讓其參與第(6)步；其二：重啟他的服務器讓其重新生成多項式。指控核實協(xié)議：當成員£發(fā)出的消息錯誤時，第一種是錯誤的時間段、數(shù)據越界等；第二種是 同一服務器發(fā)送多條含有有效簽名的信息或根木就沒有發(fā)信息；第三種錯誤是等式 2-(8)不成立。第一種第二種錯誤任何其他成員都可以檢測。每個成員p丸豐力把丿放入“壞服 務器”集合中，即bkb5j,啟動“reboot ”操作，并調用了密鑰恢復協(xié)議。 對于第三種錯誤：當成員*發(fā)現(xiàn)號發(fā)出的信息不滿足2-(8)式

41、時，其他服務器需要 驗證誰在說謊。成員用公開竹其他成員驗證： qencz')和2 -是否成立。 若都成立則說明成員角在說謊，把丫放入壞服務器集合屮，即執(zhí)行操作 乞紋5"(心7),對用啟動reboot操作，并調用子密鑰恢復協(xié)議；若不成立， 對號進行以上操作。損壞子密鑰發(fā)現(xiàn)協(xié)議：當某些服務器沒冇參與子密鑰更新階段或更新被敵手攻擊但沒冇被發(fā)現(xiàn)，因此 需要定期地對所有服務器進行檢測。每個成員用都廣播川囘“和對其的簽名。當用得到所有的廣播，他檢測簽名 的正確性，再通過比較每一服務器和大多數(shù)服務器的不同決定哪個服務器是不誠實 的，并將這些服務器加入到色中，調用恢復損壞子密鑰協(xié)議進行恢復。

42、恢復損壞子密鑰：需要恢復的子密鑰xr9re b d=abo(1) 每個成員piwd在乙/上構造一個最高次項為£階的多項式爲()且滿足 40) = 0。構造方法:任取多項式系數(shù)4冃1.出uzq那么4o=-工囘modg(2) 對每個成員 piwd,廣播encb©(j)jwd o（3）對每個成員片，iw d ,令兀'=兀+丫崖加（丿）并把encd）發(fā)送給什。（4）£根據這些份額插值算出y。這是因為毎個匕構造的多項式臥）0（廠）=0那么工崖加（廠）=0成員匕根據這 些x： , iw d插值多項式g（x）,僅僅具g（r） = xr的性質與其余的旺沒有任何關系 （即得

43、不出毎個£）這保證了每個成員用子密鑰的秘密性。2.5多秘密共享在（木刀）門限秘密共享方案屮，由刀個人共享一個秘密，任意t個被授權人 就可以恢復出秘密。但是如果由刀個人共享多個秘密，就需要針對每一個所要共享 的秘密，分別進行多次秘密共享方案，很顯然，這種秘密共享方案的計算量和通信 量的開銷都很大。為了減少開銷，就產生了多秘密共享方案。在（廣，刀）門限多秘 密共享方案屮，在一次秘密分發(fā)過程屮，多個秘密同時進行分發(fā)，而在秘密重構時, 也是多個秘密同時進行重構。這樣，多秘密共享方案大大減少了系統(tǒng)的開銷，達到 t和共享單個秘密相同的系統(tǒng)開銷。1994年，jackson等人把多秘密共享方案分成兩

44、種類型：一次使用的多秘密 共享；多次使用的多秘密共享。同年，he和dawson問捉岀了一種基于單向函數(shù)的多 秘密共享方案，在他們的方案中，需要公開5?個公共參數(shù)。為了減少公共參數(shù)的個 數(shù)，harn13捉出了一個可替代方案，他們的方案需要公開的參數(shù)比he和dawson問 公開的參數(shù)少，僅需要公開pd 個公共參數(shù)。1995年，he和dawson1141提岀了基 于雙變量單向函數(shù)動態(tài)多秘密共享方案，雙變量單向函數(shù)的應用很好地解決了秘密 份額泄露的問題oharn1151提出了基于拉格朗fl插值多項式和dsa類型的數(shù)字簽名泌 的門限多秘密共享方案。2000年，chien等昭捉岀了基于系統(tǒng)塊編碼的多秘密共

45、享 方案，在他們的方案中，他們指岀harn（l5的方案不適合一般的多秘密共享使用，而 他們捉出的方案冇以下幾個優(yōu)點：允許類似的秘密重構；秘密持冇者可以動態(tài)的決 定要分發(fā)秘密的個數(shù)；重構生成矩陣簡單高效；多次使用的方案；計算效率很高。 相比較方案皿來說，chien等的方案需要公開的公共參數(shù)更少。2004年，yang等 的利用拉格朗h插值構造出一種和chien等曲同效率的多秘密共享方案，shao1201利 用了 feldman的可驗證思想，將yang的方案改造成可驗證多秘密共享方案，此方 案解決了分發(fā)者和重構者成員的欺騙性問題，不過份額是通過秘密通道進行分發(fā)的。 龐遼軍丁 2005年和2006年捉

46、岀的基于shamir方案的多秘密共享方案和一個冇效 的（t, n）門限多重秘密共享休制兇在yang的基礎上進一步減少了公開參數(shù)的個數(shù)。2006年,zhao23提出的方案11',份額不需要通過秘密通進行分發(fā),2007年,dehkordi24 提出了另一種形式的不需耍通過秘密通道就可以分發(fā)份額的方案。2008年,dehkordi 等泗提出的基于齊次線性遞歸的多秘密共享方案，不僅減少了所需重構多項式的次 數(shù)，而且又進-步減少了公開參數(shù)的個數(shù)，是一種高效的方案。同年，他提出的基 于非齊次線性遞歸和橢圓曲線的多秘密共享方案測和文獻塚屮的方案具有同樣的高 效率。后來，有人基丁元胞自動機理論提出了多

47、秘密共享方案。2009年，等 人提出的方案屮，秘密定期改變，分發(fā)者定期公開增加系統(tǒng)健壯性的信息，此外， 參與者可以對接收到的信息進行驗證。每一個參與者僅僅持有一個永久的私密鑰， 參與者屮的某些成員可以在不同的階段，在不泄露他們的私密鑰的情況下重構秘密， 因為一些公開信息是不斷更新的，而i口的信息對于下一階段秘密的重構沒有任何幫 助。2010年，elsami基于雙線性映射提出了可驗證多秘密共享方案曲，不需要安全 通道，垂構階段參與者可以驗證參與重構的份額，提出的方案是多次使用的秘密共 享，并且更新公開信息時是高效的，因此，提出的方案具有wang的所有優(yōu)點。此 外，還有兩處改進，第一，史改秘密時，

48、公開的公共參數(shù)更少，第二，一次共享秘 密的個數(shù)不受限制。同年，das基于單向沖突抵抗哈希函數(shù)提出了可更新多次使用 多秘密共享方案呦，當同吋受到攻擊吋，即使成員的偽份額被泄鋸，方案也是安全 的。2011年，hsu提出了理想的線性多秘密共享方案測，每一個授權子集都有不同 的目標秘密，特別地，他們利用單調生成程序提出了構建這種方案的一般方法。而 在他提出的基于單調生成程序提出的理想的線性多秘密共享方案屮，參與者集合 的每一個子集都有聯(lián)合的秘密。2.5.1 yang等的多秘密共享方案參數(shù)選擇：假設是&個秘密，卩衛(wèi),.尺是刀個成員，f(r,s)是一個雙變量單向函數(shù)。分發(fā)者任意選擇門個秘密份額町宀

49、，罔，通過秘密通道分別分發(fā)給刀個成員。份額分發(fā)階段：當r5f吋，分發(fā)者執(zhí)行以下步驟完成秘密份額的分發(fā)：(1) 分發(fā)者選擇大素數(shù)q,然后選擇一個次數(shù)是z-1的多項式/2(兀)mod*hx)二 q + c2x 4卜 ckxk + axk + a2xk+ 4卜 ctt_kxl mod q其屮0 <5£,，5衛(wèi)42，44 <cl。(2) 計算 y. =h(f(r,si) mod(7 ,其中 i = l,，n。(3)公開(my,兒)。當時，分發(fā)者執(zhí)行以卜步驟完成秘密份額的分發(fā)：(1) 分發(fā)者選擇大素數(shù)g 然后選擇一個次數(shù)是心1的多項式/i(x) modq：/?(x) = q + c

50、2x hf ckxk mod q其中 0 vc,c2，.,q <q o(2) 計算 yj =/?(/(r,5；) mod,其中 z =0(3) 計算h(i) modq，其中 i = l,2,.,k。(3)公開億,%,，力伙一。,),兒)o秘密重構階段：當£"時至少廣個成員拿出他們的偽份額/(")，由已知的廣對(/(")，利用拉格cjj r插值重構多項式hx) mod q :2-a(x) = x x fl ke modl 1br + f i«=c，+ c2x hckx +qx +a2x hat-kx modg當kr時至少才個成員拿出他們的偽

51、份額/(“),由已知的廣對(于(廠,®),牙)和公開的&-廣h(x)-±ytlj=1 j#/對(/,/?(/),利用拉格朗日插值重構多項式力(兀)modq :兀ynr x j j z.x yrx f (r，s) pr x ja77 口+工汕)ii 77_ hmod® /(r,5f.)-/(r,sj罟 i-j /=1/(") /(/,sj) i-jq+c、2兀+ + q*t modg2-(10)他們的方案基于拉格朗日插值，是完美的門限秘密共享。不過他們的方案也存 在一下兩個問題：分發(fā)者的誠實性問題和重構者的誠實性問題。2.5.2 shao等的可驗證

52、多秘密共享方案sheio等販利用了 feldman的可驗證思想，將yang的方案改造成口j驗證多秘密 共享方案，參數(shù)選擇和yang的差不多，選擇一個大索數(shù)p,并且滿足(p-1), g 是ms)上的階為q的生成元。秘密分發(fā)階段：當rs/時，分發(fā)者執(zhí)行以下步驟完成秘密份額的分發(fā)：(1) 分發(fā)者選擇一個次數(shù)是的多項式力(兀)mod<7 :h(x) = c, +c2x' 4ckxk i +。1兀& +a2xk+ + + %_&兀't modq2-(11)其屮 0 vela，.,%。/?,.,。 <q o(2) 計算開=(/*(“)modq ,其中 f = l

53、,.,n o(3 )計算 gt = gcm modp ,其中 i = o,1,.,p-1 ,計算 g, = g(，i-k+ modp ,其中i =匕£ +1,f 1 o(4) 公開(廠,)2,，兒,go，gi，,g_)。(5) 成員乙通過計算下面的等式來驗證他的秘密份額是否成立：g” 二打(gj"" modp2仃2)7=0當(時，分發(fā)者執(zhí)行以下步驟完成秘密份額的分發(fā)：(1) 分發(fā)者選擇一個次數(shù)是41的多項式/2(x) mod<7 :h(x) = c 4-c2x* h云+一' modq其中 0 veg,.,- <q o(2) 計算 y =/?(/

54、(r,5z) mod,其中 i = l,.,n o(3) 計算處)modq,其中 i = ,2,.,k-t。(4) 計算g. = gc，/+l mod p ,其小 i = o,1,.,r-1。(5) 公開(材(1),力，,/i(r-r)，x，y2，y“，gog，,g-i)。(6) 成員用通過計算下面的等式來驗證他的秘密份額是否成立:g,什(g$e2-(12)mod p戶o秘密重構階段：(略)參考yang的多秘密共享方案。shao捉出的可驗證的多秘密共享方案，很好地解決了分發(fā)者和重構者成員的欺 騙性問題，不過份額是通過秘密通道進行分發(fā)的。zhao測和dehkordi匈的方案都解 決了這個問題。2

55、. 5. 3 dehkordi等的可驗證多秘密共享方案首先，份額分發(fā)者選擇兩個大素數(shù)"，計算n = pp2。然后，分發(fā)者選擇一 個和0(n)互素的整數(shù)e,并根據e計算d,使之滿足wd = lmod0(n)。選擇大素數(shù)q, 滿足在z；上計算離散對數(shù)是困難的，選擇gwz；,最后公開®w,g,p。初始化階段：每一個參與者成員都選擇自己的份額，并通過公共通道發(fā)送給分發(fā)者，具體步 驟如下：(1) 參與者成員用任意選擇®作為他的份額，計算7 = s： modn,然后把7；的值發(fā) 送給分發(fā)者d。(2) d 計算si=tf modn，其屮 j =(3) 分發(fā)者d必須確定對所有的s

56、嚴sj,否則，就讓成員耳或巧重新選擇他 們的份額，直到所有人的份額都不一樣。然后分發(fā)者選擇一個整數(shù)n并計算公開"產構建階段：當吋，分發(fā)者d執(zhí)行以下步驟：(1) 分發(fā)者選擇大素數(shù)q,然后選擇一個次數(shù)是z-1的多項式/7(對mod*/?(%)二 q + c2x hf ckxk + axk + a2xk+ hf 匕廠 mod q其屮 0 vc,.,"",%.,%o(2) 計算 y =/z(/(r,5/.) modg,其中 i = o(3) 公開(廠,必，旳,，兒)。當吋，分發(fā)者執(zhí)行以下步驟完成秘密份額的分發(fā)：(1) 分發(fā)者選擇大索數(shù)g 然后選擇一個次數(shù)是41的多項式力(

57、兀)modg：h(x) = q + c2x 4卜 ckxk mod q其中0 vc,c2，,q <q。(2) 計算 y. =h(f (r?) modq ,其中 i = o(3) 計算h(i) modq ,其中 i = ,2,k-t。(3)公開(m(1),/2(2),/z(k-/),),2,，兒)。驗證階段：重構者成員通過計算下面的等式來驗證參與者成員是否提供了止確的份額：gsj =g)mod”j = l,2,f,)幻2-(13)恢復階段:(略)。dehkordi的口j驗證方案和shao的方案不同之處就在于秘密份額分發(fā)方式的不 同，前者是成員自c選擇份額，而后者是分發(fā)者選擇份額并通過秘密通道發(fā)送給各 成員，這種情況