基于二元非對(duì)稱多項(xiàng)式的公平秘密共享方案1

楊文偉，邢玉清

（信息工程大學(xué)，河南 鄭州450001）

1 引言

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

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

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

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

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

2 預(yù)備知識(shí)

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

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

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

1) 秘密分發(fā)階段

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

2) 秘密重構(gòu)階段

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

2.2 欺騙識(shí)別秘密共享方案

欺騙識(shí)別秘密共享方案的模型也包括兩個(gè)階段。

1) 秘密分發(fā)階段

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

2) 秘密重構(gòu)階段

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

2.3 公平秘密共享

秘密重構(gòu)階段的欺騙者可以分為兩類：外部攻擊者和內(nèi)部攻擊者。

外部攻擊者：該類攻擊者其實(shí)并沒(méi)有從秘密分發(fā)者處獲取到共享份額，意圖偽裝成持有份額的參與者參與重構(gòu)。

內(nèi)部攻擊者：該類攻擊者本身?yè)碛姓鎸?shí)的份額，但會(huì)在重構(gòu)的某個(gè)階段選擇發(fā)布虛假的份額，內(nèi)部攻擊者不是完全誠(chéng)實(shí)的參與者，但也不是任意惡意的，可能只是期望除了其本人外越少人知道秘密越好的理性攻擊者。

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

1) 無(wú)攻擊者時(shí)，所有參與者都能重構(gòu)秘密；

2) 存在外部攻擊者時(shí)，誠(chéng)實(shí)參與者能夠重構(gòu)秘密而外部攻擊者無(wú)法重構(gòu)秘密；

3) 存在內(nèi)部攻擊者時(shí)，誠(chéng)實(shí)參與者與內(nèi)部攻擊者要么都恢復(fù)秘密，要么都無(wú)法恢復(fù)秘密，即內(nèi)部攻擊者無(wú)法獲得比誠(chéng)實(shí)者多的優(yōu)勢(shì)。

3 基于二元非對(duì)稱多項(xiàng)式的公平秘密共享方案

本節(jié)給出了基于二元非對(duì)稱多項(xiàng)式的具有未知重構(gòu)輪數(shù)的秘密共享方案，首先給出針對(duì)外部攻擊者的利用非對(duì)稱二元多項(xiàng)式構(gòu)建的方案 1，該方案能有效防范外部攻擊者，但不能有效解決內(nèi)部攻擊者的問(wèn)題。所以針對(duì)方案1進(jìn)行改進(jìn)，構(gòu)造具有未知輪數(shù)的方案 2，同時(shí)解決外部及內(nèi)部攻擊者的問(wèn)題。

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

3.1 方案1：針對(duì)外部攻擊者的方案

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

1) 秘密分發(fā)階段

輸入：秘密s

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

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

Step3秘密分發(fā)者D通過(guò)安全信道向Pi發(fā)送：

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

② 多項(xiàng)式ri(x)；

2) 秘密重構(gòu)階段

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

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

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

如果每個(gè)參與重構(gòu)者都得到m-1票，則轉(zhuǎn)入Step2；否則轉(zhuǎn)到Step3以識(shí)別攻擊者。

Step2所有參與重構(gòu)者Pi廣播多項(xiàng)式fi(x)，并使用秘密評(píng)估點(diǎn)驗(yàn)證接收到的多項(xiàng)式，若沒(méi)有發(fā)現(xiàn)錯(cuò)誤，則提取份額sj=fj(0)重構(gòu)秘密s，輸出(s,L)；若發(fā)現(xiàn)錯(cuò)誤則轉(zhuǎn)入Step4以識(shí)別攻擊者。

Step3所有重構(gòu)參與者Pi向未參與重構(gòu)的n-m個(gè)用戶Pm+1,… ,Pn廣播ci以及多項(xiàng)式

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

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

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

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

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

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

外部攻擊者并沒(méi)有從秘密分發(fā)者獲取到共享份額，所以在重構(gòu)階段只能猜測(cè)域F上的nk次共享多項(xiàng)式，成功的概率遠(yuǎn)低于但需要注意的是，如果協(xié)議只執(zhí)行一輪，該方案不能阻止內(nèi)部攻擊者取得相對(duì)于誠(chéng)實(shí)者的優(yōu)勢(shì)，內(nèi)部攻擊者可以在重構(gòu)的 Step1中誠(chéng)實(shí)發(fā)布多項(xiàng)式，但在Step2時(shí)選擇提交假的份額，雖然該行為依然可以被誠(chéng)實(shí)者發(fā)現(xiàn)，但該攻擊者已經(jīng)獲取到了足夠的份額以完成秘密重構(gòu)。所以在該方案的基礎(chǔ)上，本文針對(duì)內(nèi)部攻擊者引入未知重構(gòu)輪數(shù)的改進(jìn)，以同時(shí)防止外部和內(nèi)部攻擊者獲得相對(duì)于誠(chéng)實(shí)者的優(yōu)勢(shì)，達(dá)到公平性。

3.2 方案2：針對(duì)外部和內(nèi)部攻擊者的方案

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

1) 秘密分發(fā)階段

輸入：秘密s

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

對(duì)于每一個(gè)秘密vr， 秘密發(fā)布方利用方案1中的份額生成算法生成共享份額并發(fā)送給相應(yīng)的參與者。

2) 秘密重構(gòu)階段

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

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

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

② 若成功重構(gòu)秘密vr,2 ≤r≤q+1，將vr與vr-1進(jìn)行比較，若vr＞vr-1，則秘密s=vr，并終止協(xié)議；否則，繼續(xù)下一輪重構(gòu)工作。

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

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

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

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

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

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

證明同步非合謀攻擊模型假設(shè)所有重構(gòu)參與者同時(shí)出示秘密共享份額且攻擊者之間沒(méi)有合作關(guān)系。

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

由同步條件可知，PI沒(méi)有任何關(guān)于gI的先驗(yàn)知識(shí)，只能隨意猜測(cè)一個(gè)域上的nk次多項(xiàng)式其正好為gI的概率遠(yuǎn)低于而當(dāng)時(shí)，多項(xiàng)式gI與gI最多有nk個(gè)點(diǎn)上重合，其正好包含αJ,1的概率最多為從而可得

所以，當(dāng)安全參數(shù)足夠大時(shí)，攻擊者偽裝為PI得到PJ投票的概率是可忽略的。又攻擊者之間不存在同謀，所以其得到別的攻擊者投票的概率為0?？芍粽叩玫絼e人投票的概率是可忽略的，該攻擊者將被識(shí)別出來(lái)，無(wú)法進(jìn)入下一輪。

下面考慮內(nèi)部攻擊者的情況，假設(shè)在第i輪內(nèi)部攻擊者PI發(fā)送偽造的共享多項(xiàng)式由上述分析可知，PI想要在投票階段獲得PJ投票的概率為同理，該攻擊者將被識(shí)別出來(lái)，無(wú)法進(jìn)入下一輪。

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

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

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

證明 異步非合謀攻擊模型假設(shè)所有重構(gòu)參與者先后出示秘密共享份額且攻擊者之間沒(méi)有合作關(guān)系。對(duì)于攻擊者而言，最理想的攻擊模式是最后出示信息，以獲得先前參與者出示的信息。

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

上式表明gJ∈[1,m],J≠I對(duì)PI構(gòu)造需要發(fā)送的多項(xiàng)式并沒(méi)有提供有用信息。如定理 1證明所示，攻擊者將被識(shí)別出來(lái)，無(wú)法進(jìn)入下一輪。掩護(hù)多項(xiàng)式rJ(x),J≠I的隨機(jī)選擇，同樣使PI無(wú)法從gJ,J≠I中還原出共享份額fJ,J≠I，從而保證方案是安全公平的。

對(duì)于內(nèi)部攻擊者而言，在第i輪重構(gòu)的 Step2中，可以利用后發(fā)優(yōu)勢(shì)，在獲取到足夠多的共享份額之后自行恢復(fù)本輪秘密vi，并將其與上一輪秘密vi-1進(jìn)行比較，若vi＜vi-1，則發(fā)放真實(shí)的份額進(jìn)入下一輪；若vi＞vi-1，則秘密s=vi-1，其選擇釋放假的份額。但此時(shí)所有的誠(chéng)實(shí)參與者都已經(jīng)獲得了這個(gè)秘密s，因?yàn)槊孛茉谇耙惠喴呀?jīng)被重建，也就是說(shuō)，對(duì)于內(nèi)部攻擊者而言其并沒(méi)有能夠獲得獨(dú)享秘密s的額外收益，但其一旦出示假的份額將被確認(rèn)為攻擊者。這就保證了方案是安全公平的。

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

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

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

當(dāng)內(nèi)部攻擊者數(shù)目γ≥t時(shí)，攻擊者可以通過(guò)合作掌握超過(guò)t的共享份額，從而恢復(fù)秘密s。所以為保證方案的安全公平性，首先要求攻擊者數(shù)目γ＜t。

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

同定理一證明類似，在重構(gòu)階段的Step2中，合謀攻擊者只有在準(zhǔn)確猜測(cè)到秘密s的位置，才可能達(dá)成獨(dú)享恢復(fù)秘密s的目的。

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

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

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

5 方案對(duì)比

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

Harn等[6]提出了一個(gè)對(duì)抗內(nèi)部和外部攻擊者的秘密共享方案，但該方案能有效防范外部攻擊者和內(nèi)部攻擊者，但該方案依賴于Hash函數(shù)是單向碰撞穩(wěn)固的這一密碼學(xué)假設(shè)來(lái)保證每一輪恢復(fù)的正確性，在發(fā)現(xiàn)有攻擊者時(shí)也無(wú)法對(duì)攻擊者進(jìn)行有效的檢測(cè)確認(rèn)，一旦有攻擊者存在則協(xié)議中止。本文方案能夠有效對(duì)攻擊者進(jìn)行檢測(cè)確認(rèn)，而且不依賴于任何的密碼學(xué)假設(shè)。

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

表1 欺騙識(shí)別方案比較

6 結(jié)束語(yǔ)

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