一種基于二元多項式的多秘密共享方案

韓妍妍 謝定邦 郭 超 趙 洪

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

0 引 言

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

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

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

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

1 預備知識

1.1 Shamir秘密共享

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

秘密分發: 分發者隨機選擇一個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個秘密份額分別通過秘密通道發送給參與者Ui(i=1,2,…,n)。

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

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]。如果系數滿足ai,j=aj,i,那么稱其為二元對稱多項式;如果系數不滿足上述情況,那么稱其為二元非對稱多項式。在二元對稱多項式中,存在f(x,y)=f(y,x),所以分發者D可分配每個參與者秘密份額為f(vi,y)或f(x,vi),其中vi(1≤i≤n)為參與者公開的身份信息,任意參與者Ui和Uj(i≠j)間的會話密鑰即為f(vi,vj)=f(vj,vi)。在二元非對稱多項式中,分發者可分配每個參與者Ui(i=1,2,…,n)兩個秘密份額f(vi,y)和f(x,vi),任意參與者可通過獲得的秘密份額構造會話密鑰f(vi,vj)或f(vj,vi)。

1.3 秘密共享同態性

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

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

2 本文方案

2.1 動 機

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

2.2 符號定義

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

2.3 方案設計

2.3.1 秘密分發

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

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

Case1假如k

Step2D構造如下二元非對稱多項式:

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)中關于x項的系數{s1,s2,…,sk}是要共享的秘密集合。

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

Case2假如k≥t:

Step4構造如下二元非對稱多項式:

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)中關于x項的系數{s1,s2,…,sk}是要共享的秘密集合。

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

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

2.3.2 秘密重構

假設參與秘密重構的誠實重構者集合為{Pv1,Pv2,…,Pvm}。

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

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

Step5假設重構者Pvj收到m-1個其他重構者發來的cvi,vj,Pvj解密cvi,vj得到dvi,vj并分以下兩種情況進行秘密重構:

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)中系數集合{s1,s2,…,sk}即為重構的多個秘密。

3 方案分析

3.1 正確性分析

定理1本方案任意大于等于t個重構者可恢復秘密。

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

3.2 安全模型及安全性分析

3.2.1 安全模型

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

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

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

3.2.2 安全性分析

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

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

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

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

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

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

4 方案對比

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

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

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

表1 一次多密方案對比

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

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

5 未來工作

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

6 結 語

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