基于多項式插值的門限函數秘密分享方案①

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

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

(福建師范大學 福建省網絡安全與密碼技術重點實驗室,福州 350007)

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

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

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

文獻[5,6,9]中的FSS 方案在重構階段要求所有的參與者均參與重構.而在實際生活中往往存在參與者因為自身原因不能參與重構的場景,例如某個參與者在方案運行的過程中掉線,因此導致整個FSS 方案無法正常運行.除此之外他們的FSS 方案都是基于偽隨機生成器構造的,因此其安全性基于密碼學中單向函數存在性假設[10],這說明了他們的FSS 方案均為計算意義下安全的FSS 方案,即只可以抵抗計算能力有限的敵手.

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

1 相關概念

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

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

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

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

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

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

(1)Gen(1λ,f)→(k1,···,kn):輸入安全參數和秘密函數,輸出n個子函數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),輸出秘密函數在點x0處 的函數值f(x0).

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

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

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

1)敵手 A輸入安全參數1λ輸出(f0,f1),滿足Df0=Df1,并將產生的(f0,f1)發送給挑戰者C.

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

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

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

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

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

本節采用了多項式技術構造了TFSS 方案,按照FSS 定義的t-安全的安全模型證明了本文構造的TFSS 方案具有信息論意義下的t-安全性,并對方案的通信復雜度進行了具體的分析.

2.1 TFSS(Gen,Eval,Dec)

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

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

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

③ 發送者D從GFq中隨機均勻的選取lt個值rj,1,···,rj,t(j=1,···,l),并產生2l個關于z的2t次多項式

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

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

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

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

②Pi計 算

③ 輸出yi.

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

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

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

2.2 TFSS 方案的安全性分析

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

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

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

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

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

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

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

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

2.3 TFSS 方案的通信復雜度分析

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

3 文獻[11]的方案及其分析

本節對文獻[11]構造的方案進行了具體的描述,并對其方案的不滿足方案所定義的t-安全性的原因進行了具體的分析.

3.1 文獻[11]的方案

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

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

通過分析發現文獻[11]的方案在保證方案正確重構的前提下,其方案可以容忍n?t個參與者不參與重,因此其方案可以更加靈活地應用到現實場景.

3.2 安全性分析

本小節對文獻[11]方案的安全性進行分析.詳細分析了每個參與者如何通過自己的子函數來計算得到秘密函數fa,b中b的值,以及任意兩個參與者聯合如何計算得到整個秘密函數fa,b,具體過程如下:

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

2)任意兩個參與者(不妨設為P1,P2)聯合通過k1,k2計算出秘密函數fa,b.

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

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

3.3 通信復雜度分析

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

4 TFSS 方案與現有FSS 方案的比較

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

表1 TFSS 方案與現有FSS 方案的比較

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

5 結語

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