基于二元非對稱多項式的公平秘密共享方案1

楊文偉，邢玉清

（信息工程大學，河南 鄭州450001）

1 引言

Shamir[1]和 Blakley[2]于 1979年分別提出了(t,n)門限秘密共享的概念，其主要思想是秘密分發者將一個秘密分成n份，并通過安全通道發送給用戶，t個或更多的參與者可以使用他們的共享份額來重構秘密；而任何少于t個的參與者則無法恢復秘密，在完備情況下得不到任何關于秘密的信息。

雖然Shamir方案的秘密重建階段非常簡單，但這一階段對于參與者都是合法份額擁有者的假設并不總是正確的。特別是在有m(m＞t)個參與者合作恢復秘密時，一個并無有效份額的欺騙者（外部攻擊者）可能獲取其他參與者的至少t個有效份額，恢復出正確的秘密。另外，擁有有效份額的欺騙者（內部攻擊者）在秘密重構過程中可能會提交虛假份額，即使這種攻擊行為被檢測到，但并不能阻止欺騙者獲得其他誠實參與者提交的真實份額并恢復出正確的秘密，而誠實的參與者利用獲得的虛假份額進行重構只能得到錯誤的秘密，欺騙者實現獨占真實秘密的意圖。

針對秘密共享方案中存在的欺騙問題，研究者提出了許多防范措施。Tompa和Woll[3]于1988年最先提出公平秘密共享方案，其構造的方案通過將秘密隱藏在一個很難分辨的序列中，內部欺騙者要想獨享秘密只有準確猜測出真實秘密的位置，但該方案無法抵抗異步環境下的攻擊。Tian等[4]于2013年構造了一種方案，該方案利用子秘密的一致性來檢測是否存在欺騙者，同樣將秘密隱藏在一個很難分辨的序列中，并基于3種攻擊模型（非合謀攻擊、同步合謀攻擊、異步合謀攻擊）證明方案的公平性。然而Harn[5]指出該方案對于外部攻擊者，只能適應于同步環境，而不適應異步環境。2015年，Harn等[6]提出一種公平秘密方案。該方案選擇k個多項式，利用線性組合的方式將秘密隱藏在線性組合中，并將秘密隱藏在一個隨機選擇的秘密序列中，從而實現在異步環境下秘密重構的公平性。但是該方案在欺騙者存在的情況下只能終止協議。

遇到欺騙即終止協議的策略過于嚴厲，將終止協議作為對欺騙者的懲罰，但同時也使誠實參與者不能恢復秘密，這就提出了欺騙者檢測識別的需求，研究者利用不同的數學工具提出了很多針對欺騙檢測的方案。Rabin等[7]的方案中引入了第一個作弊者檢測識別方案，文獻[8,9]方案基于線性糾錯碼和通用散列函數構造欺騙識別秘密共享方案，Roy等[10]的欺騙識別基于成對的共享認證密鑰。大多數秘密共享方案的欺騙識別是基于Shamir[1]的工作，所有的份額由t-1次多項式f(x)生成。然而，二元多項式F(x,y)也是構造功能性秘密共享方案的基本工具，但基于二元多項式的欺騙識別秘密共享方案很少。Liu等[11]提出了兩種基于對稱二元多項式的欺騙識別算法，欺騙識別僅基于二元多項式的對稱性和插值多項式的線性。但該方案在異步環境下無法識別外部欺騙者，在同步環境中雖然可以識別出內部欺騙者，但無法阻止內部欺騙者獨占真實秘密。

本文構造了基于非對稱二元多項式的具有未知重構輪數的秘密共享方案，在該方案中，使用非對稱多項式生成共享份額，利用非對稱多項式次數比較高的變量構造多項式份額。多項式份額次數遠高于t-1且不需要被重構，可以隨機選擇高次多項式上的點生成秘密評估點，通過簡單運算即可實現對攻擊者的檢測和識別。并且該方案在攻擊者存在時并不是選擇立即終止協議，在剔除識別出的欺騙者后，不少于t個誠實參與者依舊可以繼續合作完成秘密重構，有效保證誠實者的權利。而且該方案可有效防范同步及異步環境下內部及外部攻擊者的欺騙，有效保證了方案的安全性和公平性。

2 預備知識

本節簡要介紹 Shamir的(t,n)秘密共享方案（該方案也是基于二元多項式的(t,n)秘密共享方案的基礎）以及對攻擊者的定義分類及對秘密共享公平性的定義。

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

Shamir的(t,n)秘密共享方案利用拉格朗日插值公式構造，由兩階段組成：秘密分發階段和秘密重構階段。在秘密分發階段，秘密分發者D分發秘密s，生成共享份額s1,s2,… ,sn，并將份額si發送給參與者Pi；在秘密重構階段，t個及以上的參與者可以重建秘密，具體算法如下。

1) 秘密分發階段

秘密分發者D在GF(q)中隨機選擇一個t-1次多項式f(x)，使秘密s=f(0)∈GF(q)。秘密分發者D生成n個秘密份額 {s1,s2,… ,sn}，其中si=f(i),i= 1,…,n，并將si發送給相應的參與者Pi。

2) 秘密重構階段

任何m(≥t)個參與者（不妨假設為P1,P2,… ,Pm）發送他們的共享份額s1,s2,… ,sm，并使用拉格朗日插值公式計算秘密s=f(0)=

2.2 欺騙識別秘密共享方案

欺騙識別秘密共享方案的模型也包括兩個階段。

1) 秘密分發階段

在這一階段，秘密分發者D將秘密s劃分為n個共享份額s1,s2,… ,sn，并將每個共享發送給相應的用戶Pi。

2) 秘密重構階段

在該階段，至少有m(≥t)個用戶提交自己的共享，以重構秘密。但在這m個共享份額上設計欺騙識別算法來識別作弊者。令L為使用欺騙識別算法識別為欺騙者的用戶集。如果(m- |L|)≥t，則不在L中的用戶繼續使用共享份額重構秘密并輸出(s,L)。如果(m- |L|)＜t，則中止協議，并輸出(⊥,L)。

2.3 公平秘密共享

秘密重構階段的欺騙者可以分為兩類：外部攻擊者和內部攻擊者。

外部攻擊者：該類攻擊者其實并沒有從秘密分發者處獲取到共享份額，意圖偽裝成持有份額的參與者參與重構。

內部攻擊者：該類攻擊者本身擁有真實的份額，但會在重構的某個階段選擇發布虛假的份額，內部攻擊者不是完全誠實的參與者，但也不是任意惡意的，可能只是期望除了其本人外越少人知道秘密越好的理性攻擊者。

定義1一個秘密共享方案稱為公平的，如果滿足：

1) 無攻擊者時，所有參與者都能重構秘密；

2) 存在外部攻擊者時，誠實參與者能夠重構秘密而外部攻擊者無法重構秘密；

3) 存在內部攻擊者時，誠實參與者與內部攻擊者要么都恢復秘密，要么都無法恢復秘密，即內部攻擊者無法獲得比誠實者多的優勢。

3 基于二元非對稱多項式的公平秘密共享方案

本節給出了基于二元非對稱多項式的具有未知重構輪數的秘密共享方案，首先給出針對外部攻擊者的利用非對稱二元多項式構建的方案 1，該方案能有效防范外部攻擊者，但不能有效解決內部攻擊者的問題。所以針對方案1進行改進，構造具有未知輪數的方案 2，同時解決外部及內部攻擊者的問題。

給定一個安全參數k，假定協議使用有限域F=GF(q)中的值進行操作，其中q= 2k，即F的每個元素都可以用k個比特表示。

3.1 方案1：針對外部攻擊者的方案

為了在參與者P= {P1,P2,… ,Pn}中共享秘密s，分發者D利用二元多項式F(x,y)為每個參與者Pi生成共享份額，其中變量y的次數為t-1，變量x的次數為nk，秘密s=F(0,0)，對應的多項式份額fi(x) =F(x,i)，容易看出deg(fi(x) ) =nk?t-1，但這些多項式永遠不需要被重構，因此能夠給每一方提供這些多項式上的數量足夠多的計算點和相應值來作為秘密評估點。

1) 秘密分發階段

輸入：秘密s

Step1秘密分發者D隨機選擇二元多項式F(x,y)，其中變量x的次數為nk次，變量y的最高次數為t-1次，且滿足F(0,0)=s。并計算fi(x) =F(x,i) ,1≤i≤n。

Step2秘密分發者D隨機選擇域F上的nk次多項式ri(x) ,1≤i≤n，以及nk個不同的隨機非零值αi,1,αi,2,… ,αi,k,1≤i≤n。

Step3秘密分發者D通過安全信道向Pi發送：

① 多項式份額fi(x)，以及秘密共享份額si=fi(0)；

② 多項式ri(x)；

2) 秘密重構階段

假設有m(m≥t)個參與者（不失一般性，記為P1,P2,… ,Pm）參與重構階段。欺騙者集合L=?。

Step1重構參與者Pi選擇域F上的隨機值ci，并向其余重構參與者廣播ci以及多項式gi(x) =fi( x) +ci r i(x)，必須滿足deg(gi(x))=nk。

所有重構參與者使用以下規則為彼此投票：如果對于任意的l∈[1,k],aj,i,l+c jbj,i,l=gj(αi,l)都成立，則Pi投票給Pj，否則Pi不給Pj投票。

如果每個參與重構者都得到m-1票，則轉入Step2；否則轉到Step3以識別攻擊者。

Step2所有參與重構者Pi廣播多項式fi(x)，并使用秘密評估點驗證接收到的多項式，若沒有發現錯誤，則提取份額sj=fj(0)重構秘密s，輸出(s,L)；若發現錯誤則轉入Step4以識別攻擊者。

Step3所有重構參與者Pi向未參與重構的n-m個用戶Pm+1,… ,Pn廣播ci以及多項式

每個未參與重構的Pj,j∈ [m+ 1,n]給P1,P2,… ,Pm投票，規則如下：如果 ?l∈ [1,k],ai,j,l+cibi,j,l=gi(αj,l)都成立 ， 則Pj投 票給Pi，其 中j∈ [m+ 1,n],i∈ [1,m]；否則Pj不會投票給Pi。

設Vi為Pi在 Step1和 Step3中的票數之和。如果可被認為是一個攻擊者，并將Pi歸入欺騙者集合L，給欺騙者投票的用戶也歸入欺騙者集合L。如果剩余的重構參與者數量大于t，則轉入Step2繼續完成秘密重構。否則中止協議并輸出(⊥,L)。

Step4所有重構參與者Pi向未參與重構的且不包含在欺騙者集合L中的用戶廣播多項式fi(x)。

每個不包含在欺騙者集合L中的Pi給這些重構參與者投票，規則如下：如果 ?l∈ [ 1,k],ai,j,l=fi(αj,l)都成立，則Pj投票給Pi；否則Pj不會投票給Pi。

設Vi為Pi的票數，如果可被認為是一個攻擊者，并將Pi歸入欺騙者集合L，給欺騙者投票的用戶也歸入欺騙者集合L。 如果剩余的重構參與者數量大于t，則轉入Step2繼續完成秘密重構，否則中止協議并輸出(⊥,L)。

可以看出方案1是一個好的(t,n)秘密共享方案。令h0(y) =F(0,y)，h0(y)是t-1次多項式，且秘密s=F(0,0) =h0(0)。此外，每個Pi都有一個秘密共享份額si=fi(0) =F(0,i),i= 1,2,… ,n。很容易看出，秘密份額si可以看成是h0(y)產生的份額，即si=F(0,i) =h0(i)，這與Shamir (t,n)秘密共享方案一致。因此，方案1是一個好的(t,n)秘密共享方案，如果參與者都誠實地發布共享份額，則可以成功地恢復秘密。

外部攻擊者并沒有從秘密分發者獲取到共享份額，所以在重構階段只能猜測域F上的nk次共享多項式，成功的概率遠低于但需要注意的是，如果協議只執行一輪，該方案不能阻止內部攻擊者取得相對于誠實者的優勢，內部攻擊者可以在重構的 Step1中誠實發布多項式，但在Step2時選擇提交假的份額，雖然該行為依然可以被誠實者發現，但該攻擊者已經獲取到了足夠的份額以完成秘密重構。所以在該方案的基礎上，本文針對內部攻擊者引入未知重構輪數的改進，以同時防止外部和內部攻擊者獲得相對于誠實者的優勢，達到公平性。

3.2 方案2：針對外部和內部攻擊者的方案

防止內部攻擊者獲得優勢的基本思想是構造具有未知重構輪數的方案，秘密發布方在最開始時通過選擇隨機數的方式確定正確的秘密在秘密序列中的位置，從而將秘密s隱藏在一個長度為k的秘密序列 {v1,v2,…,vq-1,vq,vq+1,…,vk}中，其中，vq+1用來指示真實秘密位置的“標志”。發布方為所有參與者選擇k個秘密（真實的和虛假的），并按照方案1產生秘密共享份額。秘密重構參與者共同工作，逐個完成秘密重構。如果過程中存在攻擊者，則對攻擊者進行檢測并剔除。直到在沒有攻擊者的情況下重構出標志vq+1。當該標志被重構時，所有的重構者都已經獲得了真實的秘密，秘密就是之前重構的vq。

1) 秘密分發階段

輸入：秘密s

秘密發布方隨機選擇q∈ [2,k- 1]以確定s在秘密序列中的位置，并隨機選擇域F上的k個秘密v1,v2,… ,vk， 滿足v1＞v2＞ … ＞vq-1＞vq＜vq+1,s=vq。

對于每一個秘密vr， 秘密發布方利用方案1中的份額生成算法生成共享份額并發送給相應的參與者。

2) 秘密重構階段

假設有m(m≥t)個參與者（記為P1,P2,… ,Pm）參與重構階段。

重構參與者一起合作重構秘密 {v1,v2,…vk}，按照v1→v2→…→vq+1的順序每次重建一個，依次執行：

① 對于每一輪秘密vr,1 ≤r≤q+1，重構參與者按照方案1秘密重構階段的算法將其重構；

② 若成功重構秘密vr,2 ≤r≤q+1，將vr與vr-1進行比較，若vr＞vr-1，則秘密s=vr，并終止協議；否則，繼續下一輪重構工作。

4 方案2的公平性與安全性分析

當所有的重構參與者每一輪都出示真實的秘密共享份額時，即攻擊者總數γ=0時，由之前的分析可知方案1是一個好的(t,n)秘密共享方案，即每一輪中任何少于t個秘密共享份額的集合不會泄露關于共享秘密的信息，大于等于t個秘密共享份額的集合可以重構出共享秘密。那么在第q+1輪重構完成后經檢驗發現vq+1＞vq，從而確認秘密就在之前一輪，得到秘密s=vq。

如果存在攻擊者，即攻擊者總數γ≥1時，研究方案在同步非合謀攻擊、異步非合謀攻擊、同步合謀攻擊及異步合謀攻擊模型下的安全性與公平性。

引理1在方案2中任一重構參與者能正確猜出秘密在序列中的位置的概率是1，其中是k序列中的秘密數。

證明在方案2中，秘密s=vq在構建過程中被秘密分發者隨機隱藏在序列 {v1,…,vq-1,vq,vq+1,…,vk}中，而重構參與者不知道s的確切位置，只能通過猜測，其成功的概率為

定理 1在同步非合謀攻擊模型下，方案是安全公平的。

證明同步非合謀攻擊模型假設所有重構參與者同時出示秘密共享份額且攻擊者之間沒有合作關系。

首先考慮外部攻擊者，假定其希望通過偽裝成PI參與到重構中，下面考慮其通過偽造共享多項式獲得PJ投票的概率，由投票規則可知其獲得PJ投票的概率等于

由同步條件可知，PI沒有任何關于gI的先驗知識，只能隨意猜測一個域上的nk次多項式其正好為gI的概率遠低于而當時，多項式gI與gI最多有nk個點上重合，其正好包含αJ,1的概率最多為從而可得

所以，當安全參數足夠大時，攻擊者偽裝為PI得到PJ投票的概率是可忽略的。又攻擊者之間不存在同謀，所以其得到別的攻擊者投票的概率為0。可知攻擊者得到別人投票的概率是可忽略的，該攻擊者將被識別出來，無法進入下一輪。

下面考慮內部攻擊者的情況，假設在第i輪內部攻擊者PI發送偽造的共享多項式由上述分析可知，PI想要在投票階段獲得PJ投票的概率為同理，該攻擊者將被識別出來，無法進入下一輪。

假設在第i輪內部攻擊者PI發送真實的共享多項式通過檢測，但在重構的步驟2中發送偽造欺騙別的參與者，希望能夠獲得獨享重構秘密s的額外收益，這要求其能夠準確猜中秘密s=vq所在的輪數，由引理1可知，任一重構參與者能正確猜出秘密在序列中的位置的概率是當安全參數k足夠大時，可有效保證方案的安全公平。

綜上所述，在同步非合謀攻擊模型下，方案是安全公平的。

定理 2在異步非合謀攻擊模型下，方案是安全公平的。

證明 異步非合謀攻擊模型假設所有重構參與者先后出示秘密共享份額且攻擊者之間沒有合作關系。對于攻擊者而言，最理想的攻擊模式是最后出示信息，以獲得先前參與者出示的信息。

對于攻擊者IP（外部和內部）而言，在重構過程的步驟1中，與定理1中不同地方在于IP可以選擇最后發布信息，從而獲得之前所有參與者出示的多項式gJ(x),J≠I，則PI通過偽造共享多項式獲得PJ投票的概率可表述為。但由于掩護多項式rJ(x),J≠I是隨機選擇的且相互獨立的，所以gJ(x),J≠I是相互獨立的，有

上式表明gJ∈[1,m],J≠I對PI構造需要發送的多項式并沒有提供有用信息。如定理 1證明所示，攻擊者將被識別出來，無法進入下一輪。掩護多項式rJ(x),J≠I的隨機選擇，同樣使PI無法從gJ,J≠I中還原出共享份額fJ,J≠I，從而保證方案是安全公平的。

對于內部攻擊者而言，在第i輪重構的 Step2中，可以利用后發優勢，在獲取到足夠多的共享份額之后自行恢復本輪秘密vi，并將其與上一輪秘密vi-1進行比較，若vi＜vi-1，則發放真實的份額進入下一輪；若vi＞vi-1，則秘密s=vi-1，其選擇釋放假的份額。但此時所有的誠實參與者都已經獲得了這個秘密s，因為秘密在前一輪已經被重建，也就是說，對于內部攻擊者而言其并沒有能夠獲得獨享秘密s的額外收益，但其一旦出示假的份額將被確認為攻擊者。這就保證了方案是安全公平的。

綜上所述，在異步非合謀攻擊模型下，方案是安全公平的。

定理3在同步合謀攻擊模型下，當 γ＜ min(t,時，方案是安全公平的。

證明：同步合謀攻擊模型假設此攻擊模型假設所有參與者同時出示共享份額且有多個攻擊者合謀攻擊方。

當內部攻擊者數目γ≥t時，攻擊者可以通過合作掌握超過t的共享份額，從而恢復秘密s。所以為保證方案的安全公平性，首先要求攻擊者數目γ＜t。

假設合謀的攻擊者（內部的或者外部的）為PI,1≤I≤γ，在重構開始前，攻擊者至多知道多項式 fi( x), ri( x), r + 1≤ i≤ n 上的kγ個點。由于kγ小于多項式 fi( x), ri( x)的次數 nk，從而保證了fi( x), ri( x)的安全性。攻擊者沒有辦法搜集到足夠多的 fi(0)完成秘密重構，只能出示多項式進入投票階段。如同定理1證明所示，攻擊者想要得到誠實者的投票的概率是可忽略的。所以投票階段攻擊者只能獲得同謀者的γ-1票，誠實者至少可以得到別的誠實者的n-γ-1票，為將誠實者與攻擊者區分開，只要保證 γ- 1 ＜ n -γ-1，即就可以保證沒有外部攻擊者能夠進入重構階段的Step2。

同定理一證明類似，在重構階段的Step2中，合謀攻擊者只有在準確猜測到秘密s的位置，才可能達成獨享恢復秘密s的目的。

定理4在異步合謀攻擊模型下，當 γ＜ min(t,方案是安全公平的。

證明異步合謀攻擊模型假設此攻擊模型假設所有參與者先后出示共享份額且有多個攻擊者合謀攻擊方。對于攻擊者而言，最理想的攻擊模式是最后出示信息， 他們可以獲得先前誠實參與者出示的信息。

與定理3證明類似，在重構之前，外部攻擊者無法偽造出合適的多項式以獲得誠實者的投票。與定理2證明類似，在重構階段的Step1中，即使攻擊者掌握之前所有參與者出示的多項式，由于掩護多項式的存在，攻擊既無法得到可以幫助構造多項式的有用信息，也無法從中推測出真實份額，從而阻止外部攻擊者進入Step2；在重構階段的Step2，盡管合謀的內部攻擊者可以借助后發優勢決定是否出示真實份額，但依然無法阻止誠實參與者獲得秘密s，從而保證了方案的安全公平性。

5 方案對比

Liu等[11]提出了兩種基于對稱二元多項式的欺騙識別算法，該算法并不能完全抵抗異步攻擊。例如，當t個或者更多個的誠實參與者先出示共享份額，外部攻擊者選擇之后出示份額，在出示之前他可以利用這t個真實共享份額進行拉格朗日插值計算得出正確的多項式，得到所有正確的共享份額，從而外部攻擊者可以偽裝成擁有真實份額的參與者通過檢測，并成功得到秘密 s。同時該方案也不能完全抵抗合謀同步攻擊，合謀的內部攻擊者在重構協議執行時出示錯誤的共享份額，即使攻擊行為被檢測到，但也不能阻止攻擊者獨享秘密 s。本文的安全性與公平性證明了所提方案在4種攻擊模式下的安全公平。

Harn等[6]提出了一個對抗內部和外部攻擊者的秘密共享方案，但該方案能有效防范外部攻擊者和內部攻擊者，但該方案依賴于Hash函數是單向碰撞穩固的這一密碼學假設來保證每一輪恢復的正確性，在發現有攻擊者時也無法對攻擊者進行有效的檢測確認，一旦有攻擊者存在則協議中止。本文方案能夠有效對攻擊者進行檢測確認，而且不依賴于任何的密碼學假設。

還有些方案采用其他數學工具來構造欺騙識別方案，如表 1所示。例如，文獻[8]利用Reed-Solomon編碼和正交測試法，可以識別的欺騙者；文獻[9]利用 Reed-Solomon編碼和強通用散列函數，可以識別的欺騙者;文獻[10]使用成對認證密鑰來識別的欺騙者，每一對用戶之間需要一個安全的通信通道。所有這些方案[8,9,10]都能夠識別m≥t用戶參與秘密重建的情況。本文方案可以識別的欺騙者，具有更強的識別能力，并且采用的是非對稱二元多項式及，計算簡便。

表1 欺騙識別方案比較

6 結束語

本文提出了基于非對稱二元多項式的未知重構輪數的(t,n)理性秘密共享方案，該方案可對欺騙者進行有效識別。方案使用非對稱多項式中生成多項式份額，利用多項式份額不需要被重構且次數較高的性質隨機生成秘密評估點，不依賴于任何密碼學假設，只需要簡單驗算就可實現對欺騙者的檢測與識別，并基于同步非合謀攻擊、異步非合謀攻擊、同步合謀攻擊、異步合謀攻擊證明了方案的安全公平。