秘密共享協議如何設計？

###秘密共享的思想


秘密共享的概念是由Shamir和Blakley於1979年分別獨立提出的。所謂秘密共享就是將一個密鑰分成許多部分，然後秘密地分配給一些有關人員，使得某些有關人員在同時給出他們的部分後可以重建密鑰，而另外一些人在給出他們的部分後不能重建密鑰。

**例如，**某銀行有三位出納，他們每天都要開啟保險柜，為防止每位出納可能出現的監守自盜行為，銀行規定至少有兩位出納在場才能開啟保險柜，銀行的這個開啟保險柜的問題可以利用秘密共享方案來實現。

假設你中了幾十億的彩票，而且你想把這些財產留給你的親戚。你的錢被鎖進了只有你知道的安全的地方，你並不想把這個秘密告訴你的5個孩子中的任何一個，因為他們並不可信。你想把秘密拆開來，從而讓他們中的任何3個拼在一起才能重建真實。那樣的話，如果有人想得到你的遺產，就必須同其餘的兩個孩子合作。

**秘密共享解決了兩個問題：**一是若密鑰偶然或有意地被暴露，整個系統就易受攻擊；二是若密鑰丟失或損壞，系統中的所有信息就不能用了。

秘密共享的基本思想是將密鑰k按下述方式分成n個分享k1,k2,…kn：

- 已知任意t個ki值易於計算出k。

- 已知任意t–1個或更少個ki，則由於信息短缺而不能計算出k。

**這種方案也稱為(t,n)門限方案**。將n個分享k1,k2,…kn分給n個用戶。由於重構密鑰至少需要t個分享，故暴露s(s≤t–1)個分享不會危及密鑰，從而少於t個用戶的共謀不能得到密鑰。同時，若一個分享被丟失或毀壞，仍可恢復密鑰（只要有至少t個有效的分享即可）。接下來，我們以Shamir提出的門限秘密共享方案為例介紹。

###Shamir門限秘密共享方案

Shamir於1979年提出了一個門限秘密共享方案，該方案是基於拉格朗日差值多項式構造的，具體演算法如下。

**初始化階段**

秘密分發者D隨機地從GF( q)（q為素數，且q>n）選取n個不同的非零元素x1,x2,…xn。D將xi分配給Ui (i=1,2,…,n)，且xi的值是公開的。

**秘密分發階段**

如果D打算讓n個參與者U1,U2,…Un共享秘密s∈GF(q)，D隨機地選取GF(q)中的t–1個元素a1,a2,…an-1，構造t–1次多項式

f(x)=s+a1x+a2x2+…+at-1xt-1

D計算yi=f(xi), 1≤i≤n，並將yi安全地分配給參與者Ui作為他的子秘密。

**秘密恢復階段**

n個參與者中的任意t個參與者，不妨設為U1,U2,…Ut，出示他們的子秘密，從而得到t個點對：(x1,y1), (x2,y2),…,(xt,yt)，這樣就可以重構多項式f(x)和共享的秘密s值如下：


---

推薦閱讀：