基于多項(xiàng)式插值的門限函數(shù)秘密分享方案①

羅景龍,林昌露,李朝珍,張 劍

(福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院,福州 350117)

(福建師范大學(xué) 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室,福州 350007)

1979年,Shamir[1]和Blakley[2]分別獨(dú)立提出了秘密分享(Secret Sharing,SS)概念并基于不同數(shù)學(xué)工具構(gòu)造了相應(yīng)方案.秘密分享一般包含一個(gè)發(fā)送者和多個(gè)參與者,在秘密分發(fā)階段發(fā)送者將秘密值分成多個(gè)子秘密,并將每個(gè)子秘密安全地發(fā)送給對應(yīng)的參與者.在重構(gòu)階段滿足條件的參與者集合中的參與者合作重構(gòu)出秘密值,不滿足條件的參與者集合中的參與者則不能得到關(guān)于秘密值的任何信息.作為重要的密碼技術(shù),秘密分享自提出以來一直受到研究者的持續(xù)關(guān)注.

函數(shù)秘密分享方案(Function Secret Sharing,FSS)與傳統(tǒng)的秘密分享方案[1,2]最主要的不同在于它分享的秘密為函數(shù)而不是具體數(shù)值.一個(gè)n方的FSS 方案可以簡單地描述如下,在分發(fā)階段發(fā)送者將秘密函數(shù)f:Df→Rf,其中Df,Rf分別表示秘密函數(shù)的定義域和值域,可加地分為n個(gè) 子函數(shù)f1,···,fn,并將子函數(shù)安全地發(fā)送給相應(yīng)的參與者.其正確性要求秘密函數(shù)可以通過計(jì)算被正確地重構(gòu),安全性要求子函數(shù)集合{f1,···,fn}的任何真子集完全掩蓋了秘密函數(shù)的全部信息.在FSS 方案中,子函數(shù)的長度與該FSS 方案的通信復(fù)雜度直接相關(guān),FSS 方案的通信復(fù)雜度為所有需要傳輸?shù)淖雍瘮?shù)的長度之和.FSS 在提高多服務(wù)器環(huán)境下的私密信息存取的效率,如:私密信息恢復(fù)[3],私密信息存儲[4]等方面有著重要的應(yīng)用.

針對于點(diǎn)函數(shù)fa,b(x):{0,1}l→{0,1}m,其中{0,1}l,{0,1}m分別表示點(diǎn)函數(shù)的定義域和值域,任意的x0∈{0,1}n,若x0=a有fa,b(x0)=b,否則有fa,b(x0)=0.Gilboa等[5]基于偽隨機(jī)生成器構(gòu)造了子函數(shù)長度為O (λllog32)的兩方FSS 方案,其中 λ為偽隨機(jī)生成器的種子長度,并將構(gòu)造的兩方FSS 方案應(yīng)用到了提高兩服務(wù)器的私密信息檢索協(xié)議的效率中,得到了通信復(fù)雜度為O(λllog32)的兩方私密信息檢索協(xié)議.之后Boyle 等[6]利用二叉樹技術(shù)降低了文獻(xiàn)[5]中兩方FSS 方案的通信復(fù)雜度,構(gòu)造了子函數(shù)長度為 O (λl)的兩方FSS 方案.此外Boyle 等[6]構(gòu)造了通信復(fù)雜度為 O(λ2l+n?1/2)的n(n≥3)方的FSS 方案.在此基礎(chǔ)上Boyle 等[6]提出了函數(shù)秘密分享概念并對其進(jìn)行了系統(tǒng)的介紹,指出FSS 與密碼學(xué)中的其他概念,例如:同態(tài)秘密分享(Homomorphic Secret Sharing,HSS)[7],完全同態(tài)加密(Fully Homomorphic Encryption,FHE)[8]等其他密碼學(xué)概念之間存在著密切的聯(lián)系.在文獻(xiàn)[9]中Boyle 等使用代數(shù)中的張量操作簡化了文獻(xiàn)[6]中的兩方的FSS方案的構(gòu)造并將其通信復(fù)雜度降低了4 倍.

文獻(xiàn)[5,6,9]中的FSS 方案在重構(gòu)階段要求所有的參與者均參與重構(gòu).而在實(shí)際生活中往往存在參與者因?yàn)樽陨碓虿荒軈⑴c重構(gòu)的場景,例如某個(gè)參與者在方案運(yùn)行的過程中掉線,因此導(dǎo)致整個(gè)FSS 方案無法正常運(yùn)行.除此之外他們的FSS 方案都是基于偽隨機(jī)生成器構(gòu)造的,因此其安全性基于密碼學(xué)中單向函數(shù)存在性假設(shè)[10],這說明了他們的FSS 方案均為計(jì)算意義下安全的FSS 方案,即只可以抵抗計(jì)算能力有限的敵手.

為了使FSS 方案可以更加靈活地應(yīng)用于現(xiàn)實(shí)場景,以及具有更高級別的安全性,本文采用多項(xiàng)式技術(shù)構(gòu)造了信息論意義下安全的門限函數(shù)秘密分享(Threshold Function Secret Sharing,TFSS)方案,在重構(gòu)過程中可以容忍部分參與者不參與重構(gòu),因此可以更加靈活地應(yīng)用到實(shí)際場景中.對構(gòu)造的方案按照FSS 方案所定義的t-安全性(即任意t個(gè)參與者聯(lián)合不能得到秘密函數(shù)任何信息)進(jìn)行嚴(yán)格的安全性證明,證明結(jié)果表明本文構(gòu)造的TFSS 方案滿足信息論意義下的t-安全性,即可以抵抗具有無限計(jì)算能力的敵手,因此相對于文獻(xiàn)[5,6,9]中的FSS 方案本文構(gòu)造的TFSS 方案具有更高級別的安全性.除此之外當(dāng)分享的秘密函數(shù)為點(diǎn)函數(shù)fa,b(x):{0,1}l→{0,1}m時(shí),本文構(gòu)造的TFSS 方案的通信復(fù)雜度為 O (l).低于文獻(xiàn)[5,6,9]中FSS 方案的通信復(fù)雜度.另外我們注意到Y(jié)uan 等[11]運(yùn)用多項(xiàng)式插值技術(shù)構(gòu)造了含有門限的FSS 方案,但是Yuan 等并沒有對其方案按照FSS 方案所定義的t-安全性進(jìn)行嚴(yán)格的安全性證明.經(jīng)過分析發(fā)現(xiàn),在他們的方案中任意一個(gè)參與者可以通過自己收到的子函數(shù)得到秘密函數(shù)的部分信息,進(jìn)而任意兩個(gè)參與者聯(lián)合就可以得到整個(gè)秘密函數(shù),因此其方案不能滿足t-安全性.本文對他們構(gòu)造不滿足t-安全性的原因進(jìn)行了具體分析和闡述.

1 相關(guān)概念

本節(jié)將給出本文所用到的一些概念和定義,包括點(diǎn)函數(shù)的定義,Shamir 門限秘密分享方案,函數(shù)秘密分享方案的定義及其安全模型.

定義1(點(diǎn)函數(shù)).設(shè){ 0,1}l為定義域,{ 0,1}m為值域,其中l(wèi),m為正整數(shù),則對任意的a∈{0,1}l,b∈{0,1}m,點(diǎn)函 數(shù)fa,b(x):{0,1}l→{0,1}m的定義 如 下:對任意 的x∈{0,1}l有,

定義2 (Shamir 門限秘密分享方案[1]).令GFq為q元有限域,D為發(fā)送者,P={P1,···,Pn}為n個(gè)參與者組成的集合且q>n,z1,···,zn為GFq上n個(gè)兩兩不同的非零公開值.若s∈GFq為秘密值,r為門限值,則(r,n)-Shamir 門限秘密分享方案包含以下兩個(gè)階段:

1)分發(fā)階段:發(fā)送者D從有限域GFq中隨機(jī)均勻地選取r?1個(gè) 值a1,···,ar?1,生成r?1次 多項(xiàng)式f(x)=s+a1x+···+ar?1xr?1,發(fā)送者D計(jì)算si=f(zi)(i=1,···,n),并將si安全地發(fā)送給每位參與者Pi.

2)重構(gòu)階段:對任意r個(gè)參與者{Pi1,···,Pir}?{P1,···,Pn},他們利用公開值z1,···,zn計(jì)算值插值系數(shù)cih=并通過多項(xiàng)式插值公式重構(gòu)出秘密

定義3 (函數(shù)秘密分享[5]).設(shè)1λ為安全參數(shù),Df為定義域,Rf為值域,秘密函數(shù)為f(x):Df→Rf,n為參與者個(gè)數(shù),r為重構(gòu)門限值,則t-安全 (t

(1)Gen(1λ,f)→(k1,···,kn):輸入安全參數(shù)和秘密函數(shù),輸出n個(gè)子函數(shù)k1,···,kn.

(2)Eval(i,ki,x0)→yi:任意的x0∈Df,參與者Pi(i=1,···,n)輸 入(i,ki,x0),輸出值yi.

(3)Dec(yi1,···,yir)→f(x0):輸入 (yi1,···,yir),輸出秘密函數(shù)在點(diǎn)x0處 的函數(shù)值f(x0).

上述方案滿足以下正確性和t-安全性:

正確性:若上述FSS 方案中的3 個(gè)算法(Gen,Eval,Dec)都能順利且正確的執(zhí)行,則任意r個(gè)參與者可以重構(gòu)出秘密函數(shù)f(x):Df→Rf在x0處的函數(shù)值f(x0).

t-安全:若存在受賄參與者集合T?{P1,···,Pn}且|T|=t,則不可區(qū)分性實(shí)驗(yàn)可描述如下:

1)敵手 A輸入安全參數(shù)1λ輸出(f0,f1),滿足Df0=Df1,并將產(chǎn)生的(f0,f1)發(fā)送給挑戰(zhàn)者C.

2)挑戰(zhàn)者 C收到(f0,f1)后,隨機(jī)地選取挑戰(zhàn)值c∈{0,1},執(zhí)行子函數(shù)生成算法輸入fc,輸出(k1c,···,kcn),并將{kic}i∈T發(fā)送給A.

3)敵手 A 收到{kic}i∈T后根據(jù)自己所掌握的信息給出關(guān)于挑戰(zhàn)值c的猜測.

對于任意概率多項(xiàng)式時(shí)間敵手A,若存在關(guān)于λ 的可忽略函數(shù)u(λ)[12]使得u(λ),則我們稱(Gen,Eval,Dec)為計(jì)算意義下t-安全的FSS 方案.

對任意擁有無限計(jì)算能力的敵手 A,若Adv(1λ,A,T)=則我們稱(Gen,Eval,Dec)為信息論意義下t-安全的FSS 方案.

2 門限FSS 方案TFSS(Gen,Eval,Dec)

本節(jié)采用了多項(xiàng)式技術(shù)構(gòu)造了TFSS 方案,按照FSS 定義的t-安全的安全模型證明了本文構(gòu)造的TFSS 方案具有信息論意義下的t-安全性,并對方案的通信復(fù)雜度進(jìn)行了具體的分析.

2.1 TFSS(Gen,Eval,Dec)

若秘密函數(shù)為點(diǎn)函數(shù)fa,b(x):{0,1}l→Fq,n為參與者個(gè)數(shù),r=2lt+1(r

(1)Gen(1λ,fa,b)→(k1,···,kn)

① 將a∈{0,1}l轉(zhuǎn)換為二進(jìn)制進(jìn)行表示,則a=(a1,···,al),其中aj∈{0,1}(j=1,···,l).

③ 發(fā)送者D從GFq中隨機(jī)均勻的選取lt個(gè)值rj,1,···,rj,t(j=1,···,l),并產(chǎn)生2l個(gè)關(guān)于z的2t次多項(xiàng)式

④D使用公開值z1,···,zn計(jì) 算并生成

⑤ 輸出(k1,···,kn).

(2)Eval(i,ki,x0)→yi

① 對于任意的x0∈{0,1}l,將x0用二進(jìn)制表示為x0=(x10,···,x0l).

②Pi計(jì) 算

③ 輸出yi.

(3)Dec(yi1,···,yir)→y

① 參與者Pih(h=1,···,r)通 過公開值z1,···,zn計(jì)算

正確性:在TFSS 方案中子函數(shù)ki=(g1,i,···,gl,i;,···,)(i=1,···,n),其中,為關(guān)于z的2t次多項(xiàng)式,且在子函數(shù)計(jì)算算法中每個(gè)參與者Pi(i=1,···,n)計(jì) 算yi=Eval(i,ki,x0)=因?yàn)?zi,yi)為關(guān)于z的2lt次多項(xiàng)式上的一點(diǎn),所以任意r=2lt+1個(gè) 參與者Pih(h=1,···,r)可通過子函數(shù)kih和公開值z1,···,zn計(jì)算得到的(zi1,yi1),···,(zir,yir)為 多項(xiàng)式f(z)上 的2lt+1個(gè)點(diǎn).此時(shí)參與者{Pi1,···,Pir}可以通過多項(xiàng)式插值公式計(jì)算:

2.2 TFSS 方案的安全性分析

定理1.若GFq為q元有限域,1λ為安全參數(shù),則TFSS (Gen,Eval,Dec)是 關(guān)于 秘密 函數(shù)fa,b(x):{0,1}l→{0,1}m的信息論意義下t-安全的FSS 方案.

證明:假設(shè) A為任意具有無限計(jì)算能力的敵手則關(guān)于敵手 A存在受賄參與者集合T?{P1,···,Pn},且|T|=t(為了簡便起見我們不妨取T={P1,···,Pt})的不可區(qū)分性實(shí)驗(yàn),描述如下:

(1)敵手 A輸入安全參數(shù)1λ輸出(fa0,b0,fa1,b1),滿足a0,a1∈{0,1}l,b0,b1∈{0,1}m,并將(fa0,b0,fa1,b1)發(fā)送給挑戰(zhàn)者 C.

(2)挑戰(zhàn)者 C 收到(fa0,b0,fa1,b1)后,隨機(jī)地產(chǎn)生挑戰(zhàn)值c∈{0,1},執(zhí)行子函數(shù)生成算法輸入fac,bc,輸出(kc1,···,knc),并將 {kic}i∈T發(fā)送給敵手 A.

(3)敵手 A 收到{kic}i∈T后,根據(jù)自己所掌握的信息給出一個(gè)關(guān)于挑戰(zhàn)值c的猜測.

此時(shí)敵手A 可以通過子函數(shù)kuc計(jì) 算wj,u=gcj,u+=bcj+rj,1·zu+···+rj,t·ztu,j=1,···,l,u=1,···,t,滿足以下等式關(guān)系:

因?yàn)閆為非退化矩陣,R為一個(gè)隨機(jī)矩陣,所以對于敵手 A 來說矩陣W為一個(gè)隨機(jī)矩陣,則敵手 A不能得到bcj(j=1,···,l)的任何信息.又因?yàn)?

則敵手 A不能得到acj,bcj,(c∈{0,1})的任何信息,進(jìn)而敵手 A不能得到關(guān)于挑戰(zhàn)值c的任何信息.所以Adv(1λ,A,T)=則定理1 得證.

2.3 TFSS 方案的通信復(fù)雜度分析

在方案TFSS 中ki=(g1,i,···,gl,i;,···,)(i=1,···,n), 其gj,i=gj(zi),=(zi)∈Fq,因此|ki|=2l·logq2.因?yàn)閥i∈Fq,則|yi|=logq2.因此=(2nl+h)·logq2.因?yàn)?(n,r,logq2)為常數(shù),則 Ψ=O(l).

3 文獻(xiàn)[11]的方案及其分析

本節(jié)對文獻(xiàn)[11]構(gòu)造的方案進(jìn)行了具體的描述,并對其方案的不滿足方案所定義的t-安全性的原因進(jìn)行了具體的分析.

3.1 文獻(xiàn)[11]的方案

為了解決現(xiàn)有FSS 方案不具有門限的問題,文獻(xiàn)[11]給出了秘密函數(shù)為fa,b(x):{0,1}l→GFq,n為參與者的個(gè)數(shù),t(t=l+1,t

正確性:在文獻(xiàn)[11]方案中存在關(guān)于z的l次多項(xiàng)式f(z)=其常數(shù)項(xiàng)f(0)=對于任意的x0∈{0,1}l,若x0≠a,則存在x0j≠aj,因此有f(0)=0.若x0=a,則對任意的 (j=1,···,l)都有x0j=aj,因此有所以f(0)=因此關(guān)于z的l次 多項(xiàng)式f(z)的常數(shù)項(xiàng)f(0)=fa,b(x0).而每個(gè)參與者Pi通過ki(i=1,···,n)計(jì)算的值yi=因此任意t(t=l+1,t

通過分析發(fā)現(xiàn)文獻(xiàn)[11]的方案在保證方案正確重構(gòu)的前提下,其方案可以容忍n?t個(gè)參與者不參與重,因此其方案可以更加靈活地應(yīng)用到現(xiàn)實(shí)場景.

3.2 安全性分析

本小節(jié)對文獻(xiàn)[11]方案的安全性進(jìn)行分析.詳細(xì)分析了每個(gè)參與者如何通過自己的子函數(shù)來計(jì)算得到秘密函數(shù)fa,b中b的值,以及任意兩個(gè)參與者聯(lián)合如何計(jì)算得到整個(gè)秘密函數(shù)fa,b,具體過程如下:

1)參與者Pi(i=1,···,n),通過ki計(jì)算秘密函數(shù)fa,b中b的值.

2)任意兩個(gè)參與者(不妨設(shè)為P1,P2)聯(lián)合通過k1,k2計(jì)算出秘密函數(shù)fa,b.

參與者P1收 到子函數(shù)k1=參與者P2收 到子函數(shù)k2=由1)中的分析可知,參與者P1,P2分 別通過子函數(shù)k1,k2計(jì)算出bj(j=1,···,l).此時(shí)參與者P1利 用計(jì)算得到的bj,子函數(shù)k1,k2和 公開值z1,z2計(jì)算同樣參與者P2利用計(jì)算得到的bj,子函數(shù)k1,k2和公開值z1,z2計(jì)算隨后P1計(jì)算P2計(jì)算此時(shí)參與者P1,P2可以分別獨(dú)自計(jì)算出a=(a1,···,al).

基于上述分析可知,在文獻(xiàn)[11]方案中任意兩個(gè)參與者聯(lián)合可以通過子函數(shù)和公開值計(jì)算出a,b的值,從而得到秘密函數(shù)fa,b且任意參與者可以通過子函數(shù)計(jì)算得到秘密函數(shù)fa,b中b的值.所以其方案不能抵抗t個(gè)參與者的聯(lián)合,因此不滿足FSS 方案中所定義的t-安全性.

3.3 通信復(fù)雜度分析

在文獻(xiàn)[11]的方案中ki=(i=1,···,n),其gj,i=因 此|ki|=2l·logq2.因 為yi∈Fq,則|yi|=logq2.因 此Ψ=因?yàn)?n,t,logq2)為常數(shù),則Ψ=O(l).

4 TFSS 方案與現(xiàn)有FSS 方案的比較

本節(jié)我們將本文構(gòu)造的基于多項(xiàng)式插值的門限函數(shù)秘密分享TFSS 方案與現(xiàn)存的文獻(xiàn)[5,6,9,11]中的FSS 方案在方案所基于的工具,有無門限值特性,方案的安全性的級別以及方案的通信復(fù)雜度4 個(gè)方面進(jìn)行全面的比較.為了比較的方便,假設(shè)所有FSS 方案分享的秘密函數(shù)均為點(diǎn)函數(shù)fa,b(x):{0,1}l→GFq,λ 表示偽隨機(jī)生成器種子的長度,t表示重構(gòu)門限值,n表示參與者的個(gè)數(shù).具體比較結(jié)果見表1.

表1 TFSS 方案與現(xiàn)有FSS 方案的比較

經(jīng)過比較發(fā)現(xiàn)本文構(gòu)造的TFSS 方案相對于文獻(xiàn)[5,6,9]中構(gòu)造的FSS 方案具有額外的門限特性,即在重構(gòu)的過程中可以容忍參(n?r)個(gè)參與者不參與,因此可以更加靈活地應(yīng)用于現(xiàn)實(shí)場景,且在安全性級別上由2.2 節(jié)中對TFSS 方案的安全性證明可得其為信息論意義下t-安全的,而文獻(xiàn)[5,6,9]中構(gòu)造的FSS 方案構(gòu)造均基于偽隨機(jī)生成器,所以其方案的安全性基于密碼學(xué)中單向函數(shù)的存在性假設(shè),進(jìn)而為計(jì)算意義下t-安全的.因此TFSS 方案相對于文獻(xiàn)[5,6,9]中構(gòu)造的FSS 方案具有更高級別的安全性.此外在分享的秘密函數(shù)均為fa,b(x):{0,1}l→GFq的前提下,由2.3 節(jié)對TFSS 方案的通信復(fù)雜的分析可得,TFSS 方案的通信復(fù)雜度為O (l),低于文獻(xiàn)[5,6,9]中構(gòu)造的FSS 方案的通信復(fù)雜度.在與文獻(xiàn)[11]中構(gòu)造的FSS 方案對比中可以發(fā)現(xiàn),雖然TFSS 方案與文獻(xiàn)[11]中構(gòu)造的FSS 方案均具有門限的特性,且具有相同級別的通信復(fù)雜度.但在安全性上經(jīng)過3.3 節(jié)對文獻(xiàn)[11]中構(gòu)造的FSS 方案的安全性分析可得,其方案不具有FSS 方案定義的t-安全性,而本文構(gòu)造的TFSS 方案具有信息論意義下t-安全性.

5 結(jié)語

本文針對現(xiàn)有的函數(shù)秘密分享方在重構(gòu)階段需要所有參與者參與不能靈活的適用于現(xiàn)實(shí)場景的問題,采用多項(xiàng)式技術(shù)構(gòu)造了門限函數(shù)秘密分享方案.并按照函數(shù)秘密分享方案定義的安全模型證明了新構(gòu)造的門限函數(shù)秘密分享方案為信息論意義下安全的.并對文獻(xiàn)[11]構(gòu)造了門限函數(shù)秘密分享方案進(jìn)行的分析,指出了其方案存在安全性漏洞.最后本文將新構(gòu)造的門限函數(shù)秘密分享方案與現(xiàn)有的函數(shù)秘密分享方案進(jìn)行了比較,發(fā)現(xiàn)其具有更高級別的安全性和更高的效率.但事實(shí)上,本文構(gòu)造的門限函數(shù)秘密分享方案的門限值r是受限的,要求r=2lt+1.因此在未來是否能構(gòu)造出門限值自由的函數(shù)秘密分享方案是一個(gè)值得繼續(xù)思考的問題.