韓妍妍 謝定邦 郭 超 趙 洪

1(北京電子科技學(xué)院通信工程系 北京 100070) 2(西安電子科技大學(xué)通信工程學(xué)院 陜西 西安 710071)

0 引 言

Shamir[1]和Blakley[2]分別基于拉格朗日插值多項式和映射幾何首次提出秘密共享方案。此后,秘密共享作為現(xiàn)代密碼學(xué)的一個重要研究方向,在門限加密、門限簽名和安全多方計算等領(lǐng)域都有著很好的應(yīng)用。近年來,隨著大數(shù)據(jù)、云計算,尤其是區(qū)塊鏈技術(shù)迅速發(fā)展而引出的密鑰管理問題,秘密共享技術(shù)作為解決方法將發(fā)揮更加重要的作用。Shamir秘密共享方案[1]包括系統(tǒng)秘密分發(fā)和秘密重構(gòu)兩個算法。主要思想是將秘密S分割成若干份秘密份額,并且具有屬性:(1) 任意t或大于t份秘密份額即可恢復(fù)秘密S;(2) 任意少于t份秘密份額無法獲得秘密S的任何信息。秘密共享技術(shù)不僅可以防止由于單個保管者的權(quán)力過于集中而導(dǎo)致的權(quán)威欺騙,而且秘密的分布式管理能有效保證重要數(shù)據(jù)的安全和健壯性。

Shamir秘密共享方案中,單次秘密共享過程僅可共享單個秘密;方案一次性使用;若要共享一個新秘密,分發(fā)者必須重新計算和生成新的秘密份額,并重新下發(fā)秘密份額給所有參與者。當(dāng)多個秘密需要共享時,分發(fā)者計算和傳輸秘密份額就會消耗大量資源導(dǎo)致方案效率低下。He等[3]針對上述問題提出多階段多秘密共享方案,使用公共移位技術(shù)和單向函數(shù)可按預(yù)定順序重構(gòu)多個秘密。此后,多秘密共享方案經(jīng)過不斷發(fā)展,多種方案被相繼提出:按預(yù)定順序重構(gòu)或任意次序異步重構(gòu)的多秘密共享方案[4-7],一次并行重構(gòu)多個秘密的多秘密共享方案[8-10]等。

二元多項式通常被用來構(gòu)造可驗(yàn)證的秘密共享方案[11-13]。近年來,基于二元多項式設(shè)計的秘密共享方案擴(kuò)展到了許多密碼學(xué)場景,例如: 多方量子密鑰交換協(xié)議[14]、秘密共享可欺騙識別方案[15]、異步多秘密共享方案[16]、圖像秘密共享方案[17]等。傳統(tǒng)秘密共享方案中,方案實(shí)際部署往往會受到非參與者的外部攻擊,秘密重構(gòu)的過程中必須要引入額外的密鑰協(xié)商機(jī)制,進(jìn)而建立重構(gòu)者之間的安全通道,這使得方案變得復(fù)雜。Harn等[18]基于二元非對稱多項式提出受保護(hù)的秘密共享方案(PSS),參與者收到的秘密份額不僅可以用于產(chǎn)生子秘密,還可產(chǎn)生任意參與者之間的會話密鑰,不用額外的密鑰協(xié)商機(jī)制就構(gòu)建了參與者間的安全通道。PSS方案與Shamir秘密共享方案相比有著近似的計算復(fù)雜度,并且該方案不基于任何計算性假設(shè),是信息論安全的,但是其方案沒有擴(kuò)展到多秘密共享場景。Harn等[16]第一次提出基于二元非對稱多項式的多秘密共享方案, 繼承了PSS方案參與者間安全通道的性質(zhì),并且是任意次序異步恢復(fù)的多秘密共享方案。Zhang等[19]指出文獻(xiàn)[16]的多秘密共享方案無法抵御t-1個參與者內(nèi)部合謀攻擊,當(dāng)參與者成功重構(gòu)一個秘密后,t-1個參與者即可通過獲得的秘密份額合謀計算未重構(gòu)的所有秘密;Zhang等[19]基于二元多項式構(gòu)造了多秘密共享方案,通過構(gòu)造額外的二元對稱多項式,生成會話密鑰保證參與者間安全通道,擴(kuò)展方案在滿足文獻(xiàn)[16]貢獻(xiàn)的同時,異步恢復(fù)多秘密。但是其方案會增加分發(fā)者計算和秘密份額傳輸開銷,而且不可抵抗半誠實(shí)參與者攻擊。

本文提出基于二元非對稱多項式的多秘密共享方案,方案一次可重構(gòu)多個秘密,在大秘密分割共享和多秘密共享方面都有較好的應(yīng)用場景;繼承了文獻(xiàn)[16]多秘密和安全通道的特性,又解決了其受到的安全攻擊問題。方案可進(jìn)一步設(shè)計成門限加密和門限簽名算法,進(jìn)而可結(jié)合當(dāng)前區(qū)塊鏈、電子投票等應(yīng)用場景來推動技術(shù)發(fā)展。本文方案參與者獲得的秘密份額不僅可以產(chǎn)生子秘密,并且可以生成會話密鑰,用于保護(hù)在秘密重構(gòu)過程中重構(gòu)者間的信息交換。通過安全性分析,本文方案可抵抗內(nèi)部合謀攻擊和重構(gòu)過程中的外部攻擊。

1 預(yù)備知識

1.1 Shamir秘密共享

Shamir秘密共享方案包含兩個算法:秘密分發(fā)和秘密重構(gòu)。假設(shè)可信分發(fā)者為D,參與者集合U={U1,U2,…,Un},p是大素數(shù),所有計算都在p階有限域上。

秘密分發(fā): 分發(fā)者隨機(jī)選擇一個t-1次單變量多項式f(x)=a0+a1x+a2x2+…+at-1xt-1modp,其中秘密s=a0∈GF(p),ai∈GF(p),i=1,2,…,t-1。D計算n個秘密份額s1=f(1),s2=f(2),…,sn=f(n),并將n個秘密份額分別通過秘密通道發(fā)送給參與者Ui(i=1,2,…,n)。

秘密重構(gòu): 任意大于或等于t個份額即可恢復(fù)秘密,假設(shè)有m(t≤m≤n)個參與者恢復(fù)秘密,參與者相互之間交換份額,獲得t個份額的參與者可通過拉格朗日插值公式來重構(gòu)秘密:

1.2 二元多項式

f(x,y)=a0,0+a1,0x+a0,1y+a1,1xy+…+at-1,t-1xt-1yt-1modp是一般二元多項式形式,其中ai,j∈GF(p),?i,j∈[0,t-1]。如果系數(shù)滿足ai,j=aj,i,那么稱其為二元對稱多項式;如果系數(shù)不滿足上述情況,那么稱其為二元非對稱多項式。在二元對稱多項式中,存在f(x,y)=f(y,x),所以分發(fā)者D可分配每個參與者秘密份額為f(vi,y)或f(x,vi),其中vi(1≤i≤n)為參與者公開的身份信息,任意參與者Ui和Uj(i≠j)間的會話密鑰即為f(vi,vj)=f(vj,vi)。在二元非對稱多項式中,分發(fā)者可分配每個參與者Ui(i=1,2,…,n)兩個秘密份額f(vi,y)和f(x,vi),任意參與者可通過獲得的秘密份額構(gòu)造會話密鑰f(vi,vj)或f(vj,vi)。

1.3 秘密共享同態(tài)性

Benaloh[20]首次引入秘密共享同態(tài)性的概念。定義秘密群為S,相應(yīng)的秘密份額群為T。函數(shù)F為(t,n)秘密共享中T到S的映射函數(shù),函數(shù)F將基于任意t個秘密份額{si1,sit,…,sit}的秘密S定義為S=FI{si1,sit,…,sit},其中任意t個秘密份額集合表示為I={si1,si2,…,sit}。

根據(jù)定義可知,Shamir門限秘密共享方案滿足秘密共享(++) 同態(tài)性,即兩個多項式f(x)、g(x)的秘密份額之和等于多項式(f(x)+g(x))之和的秘密份額。

2 本文方案

2.1 動 機(jī)

首先,考慮現(xiàn)有秘密共享方案在秘密重構(gòu)階段存在外部敵手時,雖然構(gòu)造額外密鑰協(xié)商機(jī)制可抵抗外部攻擊,但其復(fù)雜性與參與重構(gòu)者數(shù)量存在二次關(guān)系,在實(shí)際環(huán)境中方案復(fù)雜性高,系統(tǒng)運(yùn)行效率低。其次,文獻(xiàn)[18]提出的PSS方案有著單秘密共享的局限性;文獻(xiàn)[16]雖然是PSS方案的多秘密共享擴(kuò)展,但當(dāng)存在t-1個重構(gòu)者合謀攻擊時,僅需要重構(gòu)一個秘密,即可重構(gòu)所有未重構(gòu)的秘密;文獻(xiàn)[19]通過額外構(gòu)造二元多項式保證安全通道,增加了方案的復(fù)雜性。針對上述問題,本文提出一種新的基于二元非對稱多項式的多秘密共享方案。

2.2 符號定義

p為大素數(shù),GF(p)為p階有限域。U={Uv1,Uv2,…,Uvn}是參與者集合,P={Pv1,Pv2,…,Pvn}是重構(gòu)者集合,其中t≤m≤n。D為誠實(shí)的分發(fā)者,vi(1≤i≤n)是n個參與者公開的身份信息。{s1,s2,…,sk}為要共享的秘密集合。f(x,y)為二元非對稱多項式,t為門限值。參與者獲得的秘密份額為gvi(y)=f(vi,y)modp,構(gòu)造會話密鑰多項式為fvi(x)=f(x,vi)modp。任意參與者間的會話密鑰為Ki,j=f(vi,vj)。

2.3 方案設(shè)計

2.3.1 秘密分發(fā)

遵循2.2節(jié)定義,方案初始化大素數(shù)p、GF(p)、n、t、{s1,s2,…,sk}的值。

Step1D選擇vi(1≤i≤n),vi∈GF(p)作為每個參與者公開的身份信息,保證任意兩個參與者vi≠vj。

Case1假如k

Step2D構(gòu)造如下二元非對稱多項式:

f(x,y)=s1+s2x+…+skxk-1+a1,0xk+…+at-k-1xt-1+

a0,1y+a1,1xy+…+at-k-1xt-1y+…+a0,h-1yh-1+

a1,h-1xyh-1+…+at-k-1,h-1xt-1yh-1modp=

(s1+s2x+…+stxt-1)y0+(a0,1+a1,1x+…+at-k-1,1xt-1)y+

(a0,h-1+a1,h-1x+…+at-k-1,h-1xt-1)yh-1modp

其中f(x,y)中關(guān)于x項的系數(shù){s1,s2,…,sk}是要共享的秘密集合。

Step3D計算秘密份額gvi(y)=f(vi,y)modp,會話密鑰生成多項式fvi(x)=f(x,vi)modp,通過安全通道發(fā)送和給參與者Uvi(i=1,2,…,n)。

Case2假如k≥t:

Step4構(gòu)造如下二元非對稱多項式:

f(x,y)=s1+s2x+…+skxk-1+a0,1y+a1,1xy+…+ak-1,1xk-1y+

…+a0,h-1yh-1+a1,h-1xyh-1+…+ak-1,h-1xk-1yh-1modp=

(s1+s2x+…+skxk-1)y0+(a0,1+a1,1x+…+ak-1,1xk-1)y+

(a0,h-1+a1,h-1x+…+ak-1,h-1xk-1)yh-1modp

其中f(x,y)中關(guān)于x項的系數(shù){s1,s2,…,sk}是要共享的秘密集合。

Step5D計算秘密份額gvi(y)=f(vi,y)modp,會話密鑰生成多項式fvi(x)=f(x,vi)modp,通過安全通道發(fā)送和給參與者Uvi(i=1,2,…,n)。

Step6計算h1=f(1,0),h2=f(2,0),…,hk-t=f(k-t,0),通過Shamir秘密共享方案分發(fā)給秘密重構(gòu)者。

2.3.2 秘密重構(gòu)

假設(shè)參與秘密重構(gòu)的誠實(shí)重構(gòu)者集合為{Pv1,Pv2,…,Pvm}。

Step1重構(gòu)者Pvi結(jié)合身份信息vj和gvi(y),重構(gòu)者Pvj結(jié)合身份信息vi和計算雙方會話密鑰Ki,j=f(vi,vj)。

Step2任意重構(gòu)者Pvi分別計算gvi(0)=f(vi,0)modp,此時結(jié)合Shamir秘密共享方案,重構(gòu)者Pvi隨機(jī)構(gòu)造t-1 階單變量多項式wvi(x),其中g(shù)vi(0)=wvi(0)。

Step5假設(shè)重構(gòu)者Pvj收到m-1個其他重構(gòu)者發(fā)來的cvi,vj,Pvj解密cvi,vj得到dvi,vj并分以下兩種情況進(jìn)行秘密重構(gòu):

Case1假如k

f(x,0)=s1+s2x+skxk-1+a1,0xk+…+at-k-1,0xt-1modp=

Case2假如k≥t:

f(x,0)=s1+s2x+…+skxk-1modp=

其中f(x,0)中系數(shù)集合{s1,s2,…,sk}即為重構(gòu)的多個秘密。

3 方案分析

3.1 正確性分析

定理1本方案任意大于等于t個重構(gòu)者可恢復(fù)秘密。

其中f(x,0)中系數(shù)集合{s1,s2,…,sk}即為重構(gòu)的多個秘密。

3.2 安全模型及安全性分析

3.2.1 安全模型

多秘密共享方案基本安全性包括: (1) 重構(gòu)過程中子秘密交換的安全性;(2) 未恢復(fù)秘密的泄露安全性。故本文方案主要針對兩種攻擊:內(nèi)部合謀攻擊和外部攻擊。

內(nèi)部敵手是擁有秘密份額的合法參與者,內(nèi)部合謀攻擊是指內(nèi)部敵手可單獨(dú)攻擊或者與其他內(nèi)部敵手合謀攻擊,與其他內(nèi)部敵手合謀時可迅速獲得一定量秘密份額進(jìn)而重構(gòu)秘密,通過合謀交換子秘密在不滿足門限值情況下重構(gòu)秘密。本文假設(shè)內(nèi)部敵手不會惡意泄露秘密份額給外部攻擊者?？紤]到內(nèi)部參與者竊取身份,本方案由于采用會話密鑰加密信息,內(nèi)部參與者想要冒充其他成員身份進(jìn)行攻擊必須擁有構(gòu)造會話密鑰的秘密份額多項式,而秘密份額多項式由安全通道分發(fā),攻擊者無法構(gòu)造滿足條件的秘密份額多項式發(fā)起攻擊,故本方案抵抗內(nèi)部參與者冒充身份攻擊。

外部攻擊是指外部敵手是沒有獲得合法秘密份額的外部參與者,通過偽裝成合法參與者欺騙誠實(shí)參與者,收集到滿足門限值的子秘密時即可成功重構(gòu)秘密。本文假設(shè)分發(fā)者與參與者間存在安全通道,僅考慮秘密重構(gòu)時的外部攻擊,不考慮子秘密分發(fā)時的外部攻擊。

3.2.2 安全性分析

定理2當(dāng)保護(hù)的秘密數(shù)k(t+h+1)(t-1)或kh>(k+h+1)(t-1)條件時,本方案任意小于t個重構(gòu)者不可恢復(fù)秘密集,且無法獲得秘密任何信息。

證明:方案構(gòu)造的二元非對稱多項式f(x,y)包含th個不同的系數(shù),且x階為t-1,y階為h-1。秘密份額fvi(x)和gvi(y)分別是階為t-1關(guān)于x和h-1關(guān)于y的單變量多項式,每個參與者即可通過其構(gòu)造t+h個形如f(x,y)的線性獨(dú)立方程。當(dāng)t-1個參與者合謀攻擊時,可建立(t+h)(t-1)個線性獨(dú)立方程,此時合謀者通過gvi(y)計算還可得到t-1個gvi(0),因此合謀者總共可得到(t+h)(t-1)+(t-1)個方程,如果th>(t+h+1)(t-1),合謀者可恢復(fù)f(x,y)。故滿足條件th>(t+h+1)(t-1)可抵抗內(nèi)部合謀攻擊。

當(dāng)k≥t時,方案構(gòu)造的二元非對稱多項式f(x,y)包含kh個不同的系數(shù),且x階為k-1,y階為h-1。秘密份額fvi(x)和gvi(y)分別是階為k-1關(guān)于x和h-1關(guān)于y的單變量多項式,每個參與者即可通過其構(gòu)造k+h個形如f(x,y)的線性獨(dú)立方程。當(dāng)t-1個參與者合謀攻擊時,可建立(k+h)(t-1)個線性獨(dú)立方程,此時合謀者通過gvi(y)計算還可得到t-1個gvi(0),同時由于h1=f(1,0),h2=f(2,0),…,hk-t=f(k-t,0)由Shamir秘密共享方案保護(hù),t-1個參與者無法得到其信息,因此合謀者總共可得到(k+h)(t-1)+(t-1)個方程,滿足條件kh>(k+h+1)(t-1)可抵抗內(nèi)部合謀攻擊。

同時不失一般性,滿足條件th>(t+h+1)(t-1)下, 當(dāng)k

定理3本方案抵抗外部攻擊, 防止外部敵手獲得秘密的信息。

證明:方案可抵抗外部攻擊。假設(shè)分發(fā)者D與參與者間的通道是安全的,所以本方案只考慮秘密重構(gòu)過程中的外部攻擊。每個參與者獲得的秘密份額fvi(x)和gvi(y)即是安全的,任意參與者間的密鑰對Ki,j=f(vi,vj)由各自的秘密份額計算得出,且不同參與者對根據(jù)身份信息得到不同的Ki,j。在秘密重構(gòu)過程中,所有秘密份額全部通過密鑰Ki,j加密傳輸,假設(shè)外部敵手偽造身份信息參與秘密重構(gòu),但其缺少秘密份額而無法生成密鑰對,從而無法與誠實(shí)重構(gòu)者交換信息。因此,本方案可抵抗外部攻擊。

4 方案對比

文獻(xiàn)[19]中指出Harn等[16]方案不能抵抗t-1個參與者合謀攻擊,當(dāng)所有參與者通過秘密重構(gòu)過程恢復(fù)出首個秘密si=f(i,0)時,此時t-1個參與者已經(jīng)從分發(fā)者發(fā)送的秘密份額獲得了多項式f(x)=f(x,0)的t-1個因子,由于恢復(fù)的秘密si=f(i,0)也是f(x)的因子,進(jìn)而參與者可計算出f(x),獲得所有秘密s1=f(1,0),s2=f(2,0),…,sk=f(k,0)。本文方案可抵抗t-1個參與者內(nèi)部合謀攻擊,同時又具有文獻(xiàn)[16]方案多秘密共享和秘密通道的性質(zhì)。與文獻(xiàn)[16]相同,本文方案重構(gòu)階段通信復(fù)雜度和計算復(fù)雜度都是O(m),其中m為重構(gòu)者數(shù)。

Zhang等[19]構(gòu)造了基于二元多項式的多秘密共享方案,但是分發(fā)者需要額外構(gòu)造對稱二元多項式來滿足參與者安全通道的性質(zhì)。相比Zhang等[19]的方案, 本文方案首先無須構(gòu)建額外的二元多項式來滿足生成共享密鑰的條件,減少了分發(fā)者計算開銷。其次,方案在具有一次多秘密保護(hù)和構(gòu)建參與者安全通道的性質(zhì)外,還可以抵抗內(nèi)部合謀攻擊和秘密重構(gòu)過程中的外部攻擊。本文方案無文獻(xiàn)[16]中k

本文方案與文獻(xiàn)[8-10]相比,同樣是一次多秘密共享方案,本文方案不基于任何密碼學(xué)假設(shè),是無條件安全的。其次,在實(shí)際應(yīng)用中,文獻(xiàn)[8-10]秘密共享方案需要在參與者間加入密鑰協(xié)商機(jī)制,構(gòu)建安全通道。本文方案分發(fā)者所產(chǎn)生的秘密份額不僅可以用來產(chǎn)生子秘密,又可以構(gòu)建參與者間共享密鑰,提供參與者間安全通道,降低實(shí)際環(huán)境中方案部署的復(fù)雜性。同時,會話密鑰可抵抗秘密重構(gòu)時的外部攻擊。會話密鑰加密相比公鑰加密速度更快,整個流程會話密鑰一次性使用,保證安全性?，F(xiàn)有一次多密方案都需要一定程度的公開值更新,本文方案在k

表1 一次多密方案對比

本文方案與文獻(xiàn)[16]和文獻(xiàn)[19]重構(gòu)階段計算復(fù)雜度都為O(m),其中m為參與者數(shù),故只對比分發(fā)階段計算復(fù)雜度,假設(shè)構(gòu)造二元多項式時間為TD,秘密多項式計算時間為Tm。本文方案與文獻(xiàn)[16]和文獻(xiàn)[19]在秘密共享階段通信復(fù)雜度都為O(m)?，F(xiàn)有基于二元多項式多秘密共享方案對比如表2所示。

表2 二元多項式多秘密方案對比

5 未來工作

Tompa等[21]指出秘密共享方案存在秘密份額偽造攻擊,當(dāng)內(nèi)部欺騙者提供虛假秘密份額時,使得其他誠實(shí)重構(gòu)者恢復(fù)錯誤秘密,這就引出了秘密共享方案的公平性和欺騙識別的問題。此后多個方案通過構(gòu)造可驗(yàn)證屬性,對參與者收到的秘密份額進(jìn)行驗(yàn)證,進(jìn)而解決分發(fā)者與欺騙者的虛假秘密欺騙攻擊。近年來,基于二元多項式的欺騙識別方案[15-22]與可驗(yàn)證欺騙識別方案[23]被提出,更是體現(xiàn)出當(dāng)前秘密共享方案的一個重要方向。結(jié)合本文方案存在的欺騙攻擊問題,下一步針對欺騙攻擊對本文多秘密共享方案進(jìn)行優(yōu)化。

6 結(jié) 語

本文基于二元非對稱多項式提出一種新的多秘密共享方案,無須額外構(gòu)建二元多項式即可構(gòu)建參與者安全通道。與現(xiàn)有多秘密共享方案相比,無需額外的密鑰協(xié)商機(jī)制,參與者獲得的秘密份額既可以生成最終秘密多項式的秘密因子,又可生成任意參與者間共享密鑰。通過安全性分析,本文方案可抵抗內(nèi)部合謀攻擊和重構(gòu)過程中的外部攻擊。考慮秘密共享方案是否具有秘密份額可驗(yàn)證等其他額外屬性,是本文未來的研究與改進(jìn)方向。