基于二元對稱多項(xiàng)式的秘密共享方案

禹亮龍，杜偉章

長沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，長沙 410114

1 引言

秘密共享是數(shù)據(jù)加密中重要技術(shù)，也是信息安全中一個重要研究方向，它在密鑰管理、數(shù)字簽名和多方計(jì)算等領(lǐng)域起著關(guān)鍵作用。在1979年，由Shamir[1]和Blakely[2]提出兩種不同的(t,n)門限秘密共享方案，分別是基于Lagrange 插值法和射影幾何理論提出。在(t,n)門限秘密共享中，秘密S將被可信中心（即分發(fā)者）D分成n個份額，并且滿足以下條件：（1）恢復(fù)出秘密S需要任意t位或者t位以上的有效份額；（2）如果有效份額少于t個，則秘密S不能被計(jì)算出。

現(xiàn)有的許多的秘密共享基本都要求參與者一直誠實(shí)的情況下進(jìn)行的。但是，在恢復(fù)秘密的過程中，不可避免地存在著內(nèi)部欺騙者或者外部欺騙者，比如存在非法外部參與者加入到秘密恢復(fù)中，使得秘密泄露，也有可能存在內(nèi)部參與者進(jìn)行欺騙行為，使得只有自己能夠計(jì)算計(jì)算得出秘密，其他參與者得到錯誤的秘密。一種情況是，當(dāng)有m(m>t)位合法的參與者加入秘密恢復(fù)階段時，假設(shè)參與者交換份額不是同步的，那么就有可能有一個無效份額的持有者參與恢復(fù)，通過恢復(fù)時的安全信道，至少能夠獲得t個有效份額，那么外部欺騙者就能夠恢復(fù)正確的秘密，使得秘密泄露。另一種情況是，擁有有效份額的持有者與其他參與者交換份額時，使用的是錯誤的份額，但是欺騙者卻可以得到有效份額，那么就會造成只有內(nèi)部欺騙者才有可能計(jì)算出正確的秘密。針對上面的情況，要保證方案的公平性，即如何確保：（1）有且僅當(dāng)參與者提供的份額都為有效時，才可以計(jì)算出正確的秘密。（2）當(dāng)有錯誤的份額或者份額不全時，正確的秘密就不能被解出。目前，主要研究的方面是方案的公平性以及可驗(yàn)證性。

Chor[3]于1985 年首次提出了可驗(yàn)證秘密共享的概念，通過填加份額驗(yàn)證，來防止欺騙者。近幾年來，隨著信息安全技術(shù)的深入研究，越來越多的秘密共享方案[4-10]也被相繼提出。但是在大多數(shù)方案中，可信中心為參與者計(jì)算并分配秘密份額，并通過信道發(fā)送給他們，這會導(dǎo)致分發(fā)者持有的信息數(shù)大，權(quán)利過重等問題，這樣也導(dǎo)致分發(fā)者需要進(jìn)行的計(jì)算量大并容易遭受攻擊。1987年，F(xiàn)eldman[11]提出了一種新的秘密共享方案，在不需要可信中心的第三方參與的情況下，能夠抵抗(n-1)/2位內(nèi)部欺騙者或者外部欺騙者的合作欺騙。1994年，Harn[12]提出了一種不需要可信中心的門限群簽名方案。2003 年，王斌和李建華[13]對Harn 的簽名方案進(jìn)行分析，并指出其中的不足，并提出了一種新的無可信中心的門限簽名方案。2007年，龐遼軍等人[14]提出了一種不需要可信中心來分發(fā)份額的秘密共享方案，但還是需要可信中心來選擇份額的一些參數(shù)和計(jì)算一些公開信息。2016年，于佳等人[15]提出了一種可驗(yàn)證的多秘密共享方案，可以同時對多個秘密進(jìn)行分發(fā)。2017年，彭巧[16]的可驗(yàn)證方案；2018 年，張艷碩等人[17]的基于特征值的無可信中心的秘密共享方案研究等。

2 預(yù)備知識

2.1 Shamir(t,n)門限秘密共享方案

方案分為份額分發(fā)和秘密恢復(fù)兩個階段。

份額分發(fā)階段：分發(fā)者D隨機(jī)選擇一個t-1 次多項(xiàng)式，秘 密S=a0∈分發(fā)者D選擇{x1,且xi≠0 為每個份額持有者Ui的身份信息。D為Ui計(jì)算份額，并通過安全信道發(fā)送給Ui。

2.2 二元對稱多項(xiàng)式

在有限域GF(p)上，一個典型的t-1 階二元多項(xiàng)式為如下形式：

其中p為大素?cái)?shù)，其中根據(jù)二元多項(xiàng)式的特性，又可以將其分為兩大類：二元對稱多項(xiàng)式和和二元非對稱多項(xiàng)式。假如二元多項(xiàng)式的系數(shù)全部滿足ai,j=aj,i，則稱該二元多項(xiàng)式是對稱的；如果不能全部滿足，則是非對稱的。

其中二元對稱多項(xiàng)式有著明顯的對稱性，假設(shè)二元多項(xiàng)式f(x,y) 是二元對稱多項(xiàng)式，那么對于有限域GF(p) 中的任意兩個整數(shù)xi和xj，f(x,y) 一定滿足f(xi,xj)=f(xj,xi)。利用二元對稱多項(xiàng)式實(shí)現(xiàn)秘密共享的方案主要有文獻(xiàn)[18-20]等。在上述方案中，都需要一個可靠的分發(fā)者來構(gòu)造多項(xiàng)式和分發(fā)份額，使得分發(fā)者計(jì)算量大，掌握數(shù)據(jù)過多。

3 方案構(gòu)成

3.1 初始化階段

設(shè)S是共享秘密，是n位參與者的集合。Pi選擇自己的身份標(biāo)識IDi，并公開；然后構(gòu)建t次的對稱二元多項(xiàng)式：

p為大素?cái)?shù)，GF(p)為p階有限域。參與者共同選出隨機(jī)數(shù)Pi計(jì)算并公布。

3.2 秘密分發(fā)

參與秘密共享的人，共同選出驗(yàn)證參數(shù)e1和e2(e1,，Pi計(jì)算和，并發(fā)送給。

3.3 恢復(fù)階段

參與恢復(fù)的m位Pi做如下操作：

Pi接收Pj發(fā)送的內(nèi)容后，計(jì)算份額，和：

Pi在與參與者交換份額，先進(jìn)行交換驗(yàn)證，判斷Pi發(fā)送的是否等于Pl發(fā)送的，如果不相等，則Pl為欺騙者，通過廣播公布欺騙者并停止發(fā)送份額。如果相等，則發(fā)送份額和：

Pi在接受Pj傳遞的和后，通過Lagrange 插值公式計(jì)算出和：

并將e1,e2,0 代入比較，如果，和都同時成立，則計(jì)算S'=F0( 0)=，檢驗(yàn)結(jié)果的正確性，參與者Pi計(jì)算和，并比較是否相等：

4 分析與比較

4.1 正確性分析

在本文方案中，當(dāng)m(t≤m≤n)位合法且誠實(shí)的份額持有者能夠恢復(fù)出真實(shí)秘密S。

證明首先m位參與者在分發(fā)階段結(jié)束后，Pi可計(jì)算得出各自份額，以及和：

在份額交換前的驗(yàn)證，能盡可能的保證Pi獲得的份額是正確的，根據(jù)Lagrange 插值公式公式可知，至少需要t個因子可恢復(fù)t-1 階多項(xiàng)式，才能解出S。保證了有效的參與者能夠恢復(fù)出秘密S：

4.2 安全性分析

當(dāng)參與恢復(fù)的人中存在內(nèi)部欺騙者時：

假設(shè)內(nèi)部欺騙者Pi提供了不真實(shí)的份額F'( )IDi,0 ，在計(jì)算出S'后的檢驗(yàn)結(jié)果正確性時，會被檢測檢測會出，而在Pi提供的a'i0,i0階段，如果提供真實(shí)的ai0,i0，通過檢測后，其他參與者可以計(jì)算出很正確的S，即

如果Pi提供不真實(shí)的a'i0,i0，則其他參與者可以計(jì)算，并與Pi初始化階段公布的Ai比較來判斷正確性。

當(dāng)有外部欺騙者Di存在時：

首先如果Di是在秘密恢復(fù)恢復(fù)階段才參與的，那么他是沒有其他份額持有者發(fā)送的，和，在交換驗(yàn)證階段只有的概率能全部通過；假設(shè)Di通過了交換驗(yàn)證，并獲得了初始階段分發(fā)的和，沒有正確的，計(jì)算出。

4.3 方案分析比較

近幾年基于二元多項(xiàng)式的秘密共享方案，大多是要求有一個安全的可信中心來構(gòu)造多項(xiàng)式和分發(fā)份額的，而本文方案是一個無可信中心的秘密共享方案，即消除了可信中心可能帶來的風(fēng)險(xiǎn)，增加了方案的安全性。

高效性：與張艷碩的方案相比，本文在初始化和恢復(fù)階段的效率高很多，張艷碩的方案在初始化階段，分發(fā)者需要計(jì)算k對序列，并找出一個最小值?；謴?fù)階段，參與者需要從第一隊(duì)序列開始查找，每次查找都需要計(jì)算新的份額，并進(jìn)行驗(yàn)證，直到找出轉(zhuǎn)折點(diǎn)，即秘密S才結(jié)束，最壞的情況是需要重復(fù)恢復(fù)k-1 次；而本文方案，分發(fā)結(jié)束后，參與者就可以計(jì)算出唯一的份額，如果份額正確，技能得出正確的秘密S。

異步性：與Liu 的方案相比[20]，本文方案中，任意兩名參與者擁有私有的通話密鑰，防止外部欺騙者獲得有效份額，并不需要所有參與者同時交換信息和驗(yàn)證；而Liu的方案，由于份額是在恢復(fù)前，參與者會廣播一些份額信息，如果人在人數(shù)超過門限值時，有外部欺騙者進(jìn)入，并獲得了其他t個份額，則有可能得出秘密。

5 結(jié)束語