林昌露, 羅景龍, 張勝元, 王華雄

1. 福建師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 福州 350117

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

3. 鵬城實(shí)驗(yàn)室 人工智能研究中心, 深圳 518055

4. 新加坡南洋理工大學(xué) 物理與數(shù)學(xué)學(xué)院, 新加坡 308232

5. 網(wǎng)絡(luò)空間與信息安全重慶市重點(diǎn)實(shí)驗(yàn)室, 重慶 400065

6. 桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室, 桂林 541004

1 引言

1979 年, Shamir[1]和Blakly[2]分別獨(dú)立提出秘密分享的概念并給出了具體構(gòu)造方案, 他們的方案被稱為(t,n)-門限秘密分享方案. 在(t,n)-門限秘密分享方案中, 通常包括1 個(gè)分發(fā)者和n個(gè)參與者, 在秘密的分發(fā)階段分發(fā)者將秘密分為n個(gè)子秘密發(fā)送給相應(yīng)的參與者; 在重構(gòu)階段任意大于t個(gè)參與者合作可以重構(gòu)出秘密, 任意t個(gè)或者少于t個(gè)參與者則得不到關(guān)于秘密的任何信息. 秘密分享在密碼學(xué)和分布式計(jì)算中有許多應(yīng)用, 如拜占庭協(xié)議[3]、安全多方計(jì)算[4–6]、門限密碼學(xué)[7,8]等.

Chor 等人[9]最早考慮了用戶私密信息存取問題中的一種場景, 即用戶想要從服務(wù)器管理的數(shù)據(jù)庫中恢復(fù)某一信息, 同時(shí)服務(wù)器不知道用戶恢復(fù)信息的內(nèi)容, 將解決此類問題的模型稱之為私密信息檢索(Private information retrieval, PIR) 協(xié)議, 并用通信復(fù)雜度表示PIR 協(xié)議中用戶和服務(wù)器之間傳輸信息的總量, 用于衡量協(xié)議的傳輸效率.

為了降低私密信息存取協(xié)議的通信復(fù)雜度, Boyle 等人[10]在2015 年歐密會上提出了函數(shù)秘密分享(Function Secret Sharing, FSS) 的概念. 通過設(shè)計(jì)高效的FSS 方案, 并將其轉(zhuǎn)換為具有同級別通信復(fù)雜度的私密信息存取協(xié)議, 從而實(shí)現(xiàn)降低私密信息存取協(xié)議通信復(fù)雜度的目的. 傳統(tǒng)的秘密分享方案在參與者之間分享的秘密為某一確定的值, 而FSS 方案分享的秘密是一般的函數(shù). 通常地, FSS 方案包含三個(gè)算法, 即子函數(shù)生成算法、子函數(shù)函數(shù)值計(jì)算算法和秘密函數(shù)函數(shù)值重構(gòu)算法, 它們可簡單地描述如下: 在分發(fā)階段, 分發(fā)者通過子函數(shù)生成算法將秘密函數(shù)分為多個(gè)子函數(shù)發(fā)送給對應(yīng)的參與者; 在子函數(shù)值計(jì)算階段, 參與者確定秘密函數(shù)定義域中的點(diǎn)后, 通過子函數(shù)函數(shù)值計(jì)算算法計(jì)算子函數(shù)在該點(diǎn)處的函數(shù)值; 在重構(gòu)階段, 所有參與者聯(lián)合起來用計(jì)算得到的子函數(shù)函數(shù)值重構(gòu)出秘密函數(shù)在該點(diǎn)處的函數(shù)值. FSS 方案的安全性要求秘密函數(shù)子函數(shù)集合的任何真子集不能得到關(guān)于被分享函數(shù)的任何信息.

實(shí)質(zhì)上, FSS 方案是對Gilboa 等人[11]的分布式點(diǎn)函數(shù)(Distributed Point Function, DPF) 方案的延伸和拓展. 假設(shè)點(diǎn)函數(shù)的定義域?yàn)閧0,1}l, 值域?yàn)镚, 則對任意的x ∈{0,1}l, 該函數(shù)fα,β滿足: 若x=α, 有fα,β(x) =β; 若x ?=a, 有fα,β(x) = 0. 易知, 此DPF 方案是參與者個(gè)數(shù)為2 且秘密函數(shù)為點(diǎn)函數(shù)的FSS 方案. 在文獻(xiàn)[11] 中, Gilboa 等人將秘密函數(shù)fα,β的所有函數(shù)值排列為長度為2l長的向量, 應(yīng)用兩方的加法秘密分享方案將該向量分為兩個(gè)長度為2l的向量作為秘密函數(shù)fα,β的兩個(gè)子函數(shù).同時(shí), 利用偽隨機(jī)生成器生成的偽隨機(jī)序列來替代子函數(shù)中的隨機(jī)序列的方式, 他們構(gòu)造了子函數(shù)長度為O(λllog3) 的DPF 方案(其中λ為偽隨機(jī)生成器的種子長度), 并將所設(shè)計(jì)的DPF 方案轉(zhuǎn)化得到了通信復(fù)雜度為數(shù)據(jù)庫大小對數(shù)級別的兩服務(wù)器計(jì)算意義下安全的PIR 協(xié)議. 因?yàn)樵谖墨I(xiàn)[11] 中的分布式點(diǎn)函數(shù)方案的構(gòu)造使用了偽隨機(jī)生成器, 所以其方案的安全性基于密碼學(xué)中單向函數(shù)[12]的存在性假設(shè), 它是計(jì)算意義下安全, 即僅可以抵抗計(jì)算能力有限的敵手.

FSS 方案的通信復(fù)雜度是用于衡量執(zhí)行該FSS 方案所需要傳輸信息的總長度, 它是決定基于FSS 方案設(shè)計(jì)的私密信息存取協(xié)議效率高低的關(guān)鍵參數(shù), 它也成為國內(nèi)外學(xué)者關(guān)注的焦點(diǎn). 目前關(guān)于FSS 方案的研究主要是沿著構(gòu)造通信復(fù)雜度更低的計(jì)算意義(computational) 或完善(perfect) 安全的FSS 方案的方向進(jìn)行. 2015 年, Boyle 等人[10]運(yùn)用二叉樹的技術(shù)將文獻(xiàn)[11] 中方案的通信復(fù)雜度從O(λllog3) 降低到O(λl). Boyle 等人[13]運(yùn)用張量運(yùn)算簡化了文獻(xiàn)[10] 中方案的構(gòu)造, 并將其方案的通信復(fù)雜度降低為原來的四分之一. 這些構(gòu)造的安全性均是基于單向函數(shù)的存在性假設(shè), 屬于計(jì)算意義下安全性; 但是它們均能滿足函數(shù)秘密分享的簡潔性、壓縮性以及函數(shù)私密性. 近期, Luo 等人[14]擴(kuò)展文獻(xiàn)[10,13] 中的構(gòu)造, 不僅提出了門限函數(shù)秘密分享(Threshold Function Secret Sharing, TFSS) 概念, 而且還給出了完善安全的TFSS 方案構(gòu)造, 該方案的通信復(fù)雜度為O(l). Li 和Zhang[15]進(jìn)一步研究了完善安全的門限函數(shù)秘密分享, 給出從完善安全的PIR 協(xié)議構(gòu)造完善安全的TFSS 方案的一般構(gòu)造, 并利用互信息熵的概念討論了函數(shù)隱私性. 羅景龍等人[16]基于Shamir 門限秘密分享構(gòu)造了一個(gè)安全的TFSS 方案, 該方案的通信復(fù)雜度為O(l); 同時(shí)指出Yuan 等人的函數(shù)秘密分享方案[17]不滿足函數(shù)安全性. 但是, 這些完善安全的TFSS 方案均無法同時(shí)滿足函數(shù)秘密分享的簡潔性、壓縮性以及函數(shù)私密性. 上述這些函數(shù)秘密分享方案的效率與性質(zhì)見表1.

表1 函數(shù)秘密分享方案效率與性質(zhì)對比Table 1 Efficiencies and properties of function secret sharing schemes

Bolye 等人[10]在提出了函數(shù)秘密分享的概念和構(gòu)造的同時(shí), 還闡述了它與密碼學(xué)中的其他概念之間存在著緊密的聯(lián)系, 如同態(tài)秘密分享[18–20]、全同態(tài)加密[21,22]. FSS 在實(shí)際生活中也具有豐富的應(yīng)用.Wang 等人[23]基于FSS 方案構(gòu)造了“Splinter” 系統(tǒng), 可以支持對公開數(shù)據(jù)庫進(jìn)行種類豐富的私密信息的查詢功能. Boyle 等人[24]將FSS 方案用于安全多方計(jì)算的預(yù)處理, 提高了安全計(jì)算協(xié)議的整體效率.

考慮到現(xiàn)有所構(gòu)造的(t,r,n)-FSS 方案均無法同時(shí)滿足函數(shù)秘密分享在實(shí)際應(yīng)用中所需要的簡潔性、壓縮性和函數(shù)私密性. 本文利用文獻(xiàn)[9,25] 中的多變量多項(xiàng)式技術(shù), 將FSS 方案中秘密函數(shù)fα,β:{0,1}l →{0,1}m在某一公開點(diǎn)α′∈{0,1}l處的函數(shù)值fα,β(α′) 的計(jì)算問題轉(zhuǎn)換為某一公開函數(shù)f(λ)在某一秘密點(diǎn)Hβ(α)處的函數(shù)值計(jì)算問題. 通過這種轉(zhuǎn)換分發(fā)者可以將秘密函數(shù)fα,β拆分為n個(gè)子函數(shù)f1,··· ,fn發(fā)送給相應(yīng)的參與者, 使得n個(gè)參與者中的任意r個(gè)可以重構(gòu)出秘密函數(shù)fα,β在α′∈{0,1}l處的函數(shù)值fα,β(α′), 任意t個(gè)或少于t個(gè)參與者則不能得到關(guān)于秘密函數(shù)fα,β的任何信息. 本文還采用Fq上的常數(shù)項(xiàng)為“0” 的r ?1 次隨機(jī)多項(xiàng)式進(jìn)行掩蓋秘密的方法, 構(gòu)造了可以同時(shí)滿足簡潔性, 壓縮性和函數(shù)私密性的(t,r,n)-FSS 方案. 本文方案的效率和性質(zhì)與現(xiàn)有函數(shù)秘密分享方案的比較信息見表1.

本文的組織結(jié)構(gòu)如下: 第2 節(jié)給出本文所需要的相關(guān)概念與知識; 第3 節(jié)簡要介紹多變量多項(xiàng)式以及把它用于構(gòu)造函數(shù)秘密分享的思想; 第4 節(jié)對本文方案進(jìn)行描述與分析; 第5 節(jié)將本文方案與現(xiàn)有的函數(shù)秘密分享方案在效率與性質(zhì)方面作比較分析; 第6 節(jié)對本文工作進(jìn)行了總結(jié).

2 預(yù)備知識

秘密分享由Shamir[1]和Blakly[2]分別獨(dú)立提出, 他們所設(shè)計(jì)的方案被稱為(t,n)-門限秘密分享方案, 其中n表示參與者個(gè)數(shù),t表示門限值. 在分發(fā)階段分發(fā)者將秘密分為n個(gè)子秘密, 安全地發(fā)送給對應(yīng)的參與者, 在重構(gòu)階段, 任意t+1 個(gè)參與者合作可以正確地重構(gòu)出秘密, 其安全性要求任意t個(gè)或少于t個(gè)參與者不能得到秘密的任何信息. Shamir (t,n)-門限秘密分享方案的形式化定義如下:

定義1(Shamir (t,n)-門限方案[1]) 令Fq為q元有限域, 其中q為大素?cái)?shù)且q>n. 令λ1,··· ,λn為Fq上兩兩不同的非零公開值,D為可信的分發(fā)者,P1,··· ,Pn為n個(gè)參與者, 則稱如下定義的秘密分享方案為Shamir (t,n)-門限方案.

?分發(fā)階段: 給定秘密s ∈Fq, 分發(fā)者D構(gòu)造常數(shù)項(xiàng)為s的t次多項(xiàng)式f(x)=s+a1x+···+atxt,其中ai(i=1,··· ,t) 是從Fq中隨機(jī)選取的.D運(yùn)用f(x) 生成參與者Pi(i=1,··· ,n) 的子秘密,

并將每個(gè)子秘密si通過安全信道獨(dú)立地發(fā)送給相應(yīng)的參與者Pi.

?重構(gòu)階段: 參與者集合{Pi}i∈[n]中的任意t+1 個(gè)參與者Piτ(τ=1,··· ,t+1) 拿出自己的子秘密siτ, 通過多項(xiàng)式插值公式可計(jì)算

Shamir(t,n)-門限方案在構(gòu)造的過程中不基于任何密碼學(xué)中的困難問題假設(shè), 它被公認(rèn)為是完善安全的密碼原語.

現(xiàn)有的FSS 方案在重構(gòu)階段需要全部參與者的參與, 導(dǎo)致其不能靈活運(yùn)用于一些實(shí)際場景. Luo 等人[14]給出了參與者人數(shù)為n, 私密門限為t, 重構(gòu)門限為r的門限函數(shù)秘密分享的形式化定義(簡稱為(t,r,n)-FSS 方案). 其定義思想來源于文獻(xiàn)[10,11,13], 并運(yùn)用基于游戲的安全模型給出了安全性的形式化定義.

定義2(門限函數(shù)秘密分享方案[14]) 令Fq(q>n) 為有限域, 1λ為安全參數(shù),D為分發(fā)者,n為參與者的個(gè)數(shù),t為私密門限值,r為重構(gòu)門限值. 設(shè)f:Df →Rf為可有效的計(jì)算并能被簡潔描述的函數(shù), 則關(guān)于秘密函數(shù)f的門限函數(shù)秘密分享方案包含以下三個(gè)概率多項(xiàng)式時(shí)間算法(Gen, Eval, Dec):

-Gen(1λ,f)→(k1,··· ,kn) : 此算法為子函數(shù)生成算法,D輸入安全參數(shù)1λ, 秘密函數(shù)f, 此算法輸出秘密函數(shù)f的n個(gè)子函數(shù)(k1,··· ,kn).

-Eval(i,ki,x)→yi: 此算法為子函數(shù)計(jì)算算法, 對于給定的x ∈Df, 當(dāng)參與者Pi(i= 1,··· ,n)收到子函數(shù)ki后, 輸入(i,ki,x), 此算法輸出子函數(shù)ki在x點(diǎn)處的函數(shù)值yi.

-Dec((λi1,yi1),··· ,(λir,yir))→s: 此算法為輸出解碼器, 收到任意r個(gè)子函數(shù)在x ∈Df處的函數(shù)值yi1,··· ,yir后, 此算法輸出秘密函數(shù)f在x點(diǎn)處的函數(shù)值f(x).

針對上述所定義的(t,r,n)-FSS 方案, 要求其滿足以下正確性和安全性要求:

正確性: (t,r,n)-FSS 的正確性要求當(dāng)算法(Gen,Eval,Dec) 正確執(zhí)行時(shí), 在重構(gòu)階段, 任意r個(gè)參與者可以利用計(jì)算算法Eval的輸出值重構(gòu)出秘密函數(shù)f在x點(diǎn)處的函數(shù)值f(x). 用數(shù)學(xué)語言可以描述如下:

即對任意的可以有效計(jì)算的且能被簡潔地描述的函數(shù)f:Df →Rf, 任意的x ∈Df, 集合{i1,··· ,ir} ?[n], 當(dāng)算法(Gen,Eval,Dec) 均正確執(zhí)行時(shí), 秘密函數(shù)f在x點(diǎn)處的函數(shù)值f(x) 被正確重構(gòu)的概率為“1”.

t-安全性: 假設(shè)存在受賄參與者集合T ?{P1,··· ,Pn}且|T| =t, 則關(guān)于(t,r,n)-FSS 方案的基于游戲的安全模型具體如下:

- 對任意計(jì)算能力無限的敵手A, 輸入安全參數(shù)1λ, 敵手A生成函數(shù)(f0,f1)←A(1λ), 其中Df0=Df1, 并將產(chǎn)生的函數(shù)f0,f1發(fā)送給挑戰(zhàn)者C.

- 挑戰(zhàn)者C收到函數(shù)f0,f1后, 從{0,1}中隨機(jī)地選擇挑戰(zhàn)指數(shù)b, 確定秘密函數(shù)fb, 執(zhí)行算法Gen

生成秘密函數(shù)fb的子函數(shù)(k1,··· ,kn)←Gen(1λ,fb).

- 敵手A利用T中的受賄參與者所提供的子函數(shù){ki}i∈T, 輸出關(guān)于挑戰(zhàn)指數(shù)b的猜測b′←A({ki}i∈T).

注1(完善安全性) 上述安全模型與文獻(xiàn)[10,11,13] 中的安全模型定義是一致的. 但這些文獻(xiàn)中所設(shè)計(jì)的FSS 方案僅為計(jì)算意義下安全, 在其安全模型中假設(shè)敵手A僅具有有限的計(jì)算能力, 并僅限制Adv(1λ,A,T)≤u(λ), 其中u(λ) 為關(guān)于安全參數(shù)1λ的可忽略函數(shù)[26]. 不同于文獻(xiàn)[10,11,13], 本文專注于考慮完善安全的情形, 即方案的安全性可以抵抗任意具有無限計(jì)算能力的敵手, 因此在上述安全模型中假設(shè)敵手A具有無限的計(jì)算能力, 且要求Adv(1λ,A,T)=0.

注2(魯棒的解碼) 在文獻(xiàn)[10,11,13] 中所構(gòu)造的FSS 方案的輸出解碼器Dec需要收到所有子函數(shù)在x點(diǎn)的函數(shù)值才可以重構(gòu)出秘密函數(shù)f在x點(diǎn)處的函數(shù)值f(x), 當(dāng)存在參與者不能參與重構(gòu)就會導(dǎo)致整個(gè)FSS 方案停止運(yùn)行. 在定義2 中給出的(t,r,n)-FSS 的定義中輸出解碼器Dec具有魯棒性, 只需要收到任意r個(gè)子函數(shù)在x ∈Df處的函數(shù)值就可以重構(gòu)處秘密函數(shù)f在x點(diǎn)處的函數(shù)值f(x), 即可以允許n ?r個(gè)參與者不參與重構(gòu), 因此可以更加靈活的應(yīng)用于現(xiàn)實(shí)場景中.

根據(jù)上述(t,r,n)-FSS 方案的定義, Shamir (t,n)-門限方案可以看作參與者人數(shù)為n, 私密門限值為t, 重構(gòu)門限值為t+1 的門限秘密分享方案, 為了方便將該方案記作Shamir (t,t+1,n)-門限方案.

不同于傳統(tǒng)的秘密分享方案分享, 分享的秘密為有限域Fq上的確定值, 子秘密的大小等于所分享的秘密的大小等于q, 因此子秘密的大小為常數(shù)級別. 而在FSS 方案中分享的秘密為某一函數(shù), 且一般在FSS 方案中子函數(shù)的長度與秘密函數(shù)的定義域大小成線性關(guān)系. 當(dāng)秘密函數(shù)的定義域大小為指數(shù)級別時(shí),則構(gòu)造的FSS 方案的子函數(shù)長度為指數(shù)級別, 進(jìn)而該FSS 方案的通信復(fù)雜度也為指數(shù)級別. 考慮到FSS方案設(shè)計(jì)的最初目的是用于提高私密信息存取協(xié)議的通信效率, 因此在文獻(xiàn)[10] 中對FSS 方案提出了簡潔性、壓縮性和函數(shù)私密性的要求.

簡潔性: 在FSS 方案中通過執(zhí)行子函數(shù)生成算法Gen產(chǎn)生子函數(shù)長度的大小級別要小于秘密函數(shù)定義域大小的級別.

壓縮性: 在FSS 方案中通過子函數(shù)計(jì)算算法Eval計(jì)算得到的子函數(shù)的函數(shù)值為秘密函數(shù)值域中的元素.

函數(shù)私密性: 在FSS 方案中對任意的秘密函數(shù), 當(dāng)參與者在重構(gòu)前確定重構(gòu)該函數(shù)在某一點(diǎn)處的函數(shù)值后, 要求在重構(gòu)階段參與者僅能重構(gòu)出秘密函數(shù)在該點(diǎn)處的函數(shù)值, 而得不到秘密函數(shù)在其他點(diǎn)處的函數(shù)值.

如果要求在FSS 方案中, 函數(shù)值f(x′) 對于參與者來說是完善安全則需要當(dāng)算法Eval收到需要計(jì)算的點(diǎn)x時(shí), 其輸出結(jié)果{y1,··· ,yn}將函數(shù)值f(x′)(x′?=x) 的所有信息全部移除, 只保留重構(gòu)函數(shù)f在點(diǎn)x處的函數(shù)值f(x) 的信息, 其形式化定義如下:

定義4(完善安全的函數(shù)私密性) 對于(t,r,n)-FSS 方案, 若存在概率多項(xiàng)式時(shí)間算法Sim:Fq →Fnq對于其分享的任何秘密函數(shù)f:Df →Rf都有以下等式

成立, 則稱該(t,r,n)-FSS 方案滿足完善安全的函數(shù)私密性. 其中, “X ≡Y” 表示隨機(jī)變量集X與Y具有相同的概率分布.

注3定義4 的含義是指若(t,r,n)-FSS 方案滿足完善安全的函數(shù)私密性, 則存在概率多項(xiàng)式時(shí)間算法Sim : Fq →Fnq可以僅通過函數(shù)值f(x) 以及一些公開信息“?” 就可以模擬出該(t,r,n)-FSS 方案計(jì)算算法Eval的輸出結(jié)果{y1,··· ,yn}, 因此可以說明算法Eval的輸出結(jié)果{y1,··· ,yn}只包含秘密函數(shù)f在點(diǎn)x處的信息而不包含秘密函數(shù)f在其他點(diǎn)x′∈Df,x′?=x的函數(shù)值f(x′) 的相關(guān)信息.

3 多變量多項(xiàng)式與函數(shù)秘密分享

當(dāng)向量E(α′)(α′∈[N]) 的重為d時(shí), 多項(xiàng)式Fα′(z1,··· ,zm) 的次數(shù)為d. 此外將長度為m重為d的向量Hβ(α) 代入多項(xiàng)式Fα′(z1,··· ,zm) 中有以下等式成立:

本文將利用式(2) 把FSS 方案中計(jì)算秘密函數(shù)fα,β(x):{0,1}l →Fq在某一公開點(diǎn)α′∈{0,1}l處的函數(shù)值fα,β(α′) 的問題, 轉(zhuǎn)換為計(jì)算公開函數(shù)Fα′(·) 在秘密點(diǎn)Hβ(α) 處函數(shù)值的問題. 通過此轉(zhuǎn)換,任意r=dt+1 個(gè)參與者可以重構(gòu)出秘密函數(shù)fα,β在點(diǎn)α′∈{0,1}l處的函數(shù)值fα,β(α′) 且任意t個(gè)或少于t個(gè)參與者不能得到關(guān)于秘密函數(shù)fα,β的任何信息, 具體過程如下:

對任意t個(gè)向量V1,··· ,V t ∈Fmq, 令

易知, 式(3)是關(guān)于λ的dt=r ?1 次多項(xiàng)式.

因?yàn)槎囗?xiàng)式Fα′(Q(λ)) 為Q(λ)l(l=1,··· ,m) 中的d個(gè)多項(xiàng)式的乘積, 所以Fα′(Q(λ)) 為Fq上的可約多項(xiàng)式, 故多項(xiàng)式Fα′(Q(λ)) 不是Fq上關(guān)于變量λ的隨機(jī)多項(xiàng)式. 為了使得本節(jié)所構(gòu)造的(t,r,n)-FSS 方案滿足完善安全的函數(shù)私密性, 本文選取Fq上常數(shù)項(xiàng)為“0” 的r ?1 次隨機(jī)多項(xiàng)式來掩蓋多項(xiàng)式Fα′(Q(λ)) 得到Fq上的隨機(jī)多項(xiàng)式f(λ). 令多項(xiàng)式R(λ) = 0+a1λ+···+ar?1λr?1, 為定義在Fq上常數(shù)項(xiàng)為“0” 的r ?1 次隨機(jī)多項(xiàng)式, 其中a1,··· ,ar?1是從Fq上隨機(jī)獨(dú)立選取的. 令

因?yàn)镽(λ) 為定義在Fq上關(guān)于變量λ的r ?1 次隨機(jī)多項(xiàng)式, 因此f(λ) 也為定義在Fq上的關(guān)于變量λ的r ?1 次隨機(jī)多項(xiàng)式且多項(xiàng)式f(λ) 的常數(shù)項(xiàng)

令λ1,··· ,λn為Fq上的n個(gè)兩兩不同的非零公開值, 因?yàn)槎囗?xiàng)式f(λ) 為關(guān)于變量λ的r ?1 次隨機(jī)多項(xiàng)式, 使用f(λ) 的任意r個(gè)值f(λ1),··· ,f(λr) 可以通過多項(xiàng)式插值得到f(λ) 的常數(shù)項(xiàng)f(0) =fα,β(α′). 另一方面因?yàn)橄蛄縌(λ)的每一個(gè)分量Q(λ)l(l=1,··· ,m)為關(guān)于λ的t次隨機(jī)多項(xiàng)式, 其中Q(0) =Hβ(α).Q(λ1),··· ,Q(λn)∈Fmq, 則Q(λ1),··· ,Q(λn) 中任意t個(gè)或少于t個(gè)值不包含Hβ(α)的任何信息.

4 方案構(gòu)造

在上節(jié)分析的基礎(chǔ)上構(gòu)造關(guān)于點(diǎn)函數(shù)fα,β(x) :{0,1}l →Fq完善安全的(t,r,n)-FSS 方案, 并將分析該方案能同時(shí)滿足簡潔性、壓縮性和函數(shù)私密性.

4.1 方案描述

假設(shè)分享的秘密函數(shù)為fα,β(x) :{0,1}l →Fq, 分發(fā)者為D, 參與者人數(shù)為n, 私密門限為t, 重構(gòu)門限為r, 且有t

4.2 方案分析

本節(jié)將對上述所構(gòu)造方案進(jìn)行正確性分析、安全性證明和通信復(fù)雜度分析, 并對在實(shí)際應(yīng)用中所需要的簡潔性、壓縮性、函數(shù)私密性也進(jìn)行詳細(xì)分析.

證明:根據(jù)定義2 中所給出的關(guān)于函數(shù)秘密分享方案的形式化定義, 需要證明本文方案滿足正確性和t-安全性.

正確性: 根據(jù)本文(Gen, Eval, Dec)的構(gòu)造要證明其正確性只需要證明如下等式成立,

即當(dāng)三個(gè)算法(Gen, Eval, Dec)可以正確且順利地執(zhí)行時(shí), 秘密函數(shù)fα,β在α′點(diǎn)處的函數(shù)值可以被成功重構(gòu)的概率為“1”.

若算法(Gen, Eval, Dec)正確且順利地執(zhí)行, 則子函數(shù)生成算法可以正確地生成子函數(shù)ki=(Q(λi),R(λi)) (i= 1,··· ,n). 因?yàn)閒(λ) 為定義在Fq上的關(guān)于變量λ的r ?1 次隨機(jī)多項(xiàng)式且其常數(shù)項(xiàng)為f(0) =Fα′(Hβ(α)) =fα,β(α′). 對Fq上兩兩不同的非零公開值λ1,··· ,λn, 每個(gè)參與者Pi(i= 1,··· ,n) 執(zhí)行子函數(shù)計(jì)算算法Eval輸出yi= Eval(i,ki,α′) =f(λi), 它們是多項(xiàng)式f(λ) 的n個(gè)值. 當(dāng)輸出解碼器Dec收到任意r個(gè)值yih=f(λih) (h=1,··· ,r) 后可以通過多項(xiàng)式插值計(jì)算出多項(xiàng)式f(λ) 的常數(shù)項(xiàng)f(0)=Dec((i1,yi1),··· ,(ir,yir))=∑r h=1bih ·yih=Fα′(Hβ(α))=fα,β(α′), 進(jìn)而重構(gòu)出秘密函數(shù)fα,β在α′點(diǎn)處的函數(shù)值. 綜上, 正確性得證.

t-安全性: 通過考慮以下存在受賄參與者集合T ?{P1,··· ,Pn},|T| =t, 具有無限計(jì)算能力敵手A的基于游戲的安全模型來證明本文方案的t-安全性. 不失一般性假設(shè)T={P1,··· ,Pt}.

- 具有無限計(jì)算能力的敵手A輸入安全參數(shù)1λ生成(fα0,β0,fα1,β1)←A(1λ), 其中Dfα0,β0=Dfα1,β1,α0,α1∈[N],β0,β1∈Fq, 并將產(chǎn)生的函數(shù)(fα0,β0,fα1,β1) 發(fā)送給挑戰(zhàn)者C.

- 挑戰(zhàn)者C從{0,1}中隨機(jī)地選擇一個(gè)挑戰(zhàn)值b, 確定秘密函數(shù)fαb,βb并按如下過程執(zhí)行子函數(shù)生成算法Gen輸入秘密函數(shù)fαb,βb.

1) 分發(fā)者D隨機(jī)獨(dú)立地選取t個(gè)m長的向量V1,··· ,V t ∈Fmq和a1,··· ,ar?1∈Fq.

2) 分發(fā)者D生成多項(xiàng)式Q(λ)=Hβb(αb)+λV1+···+λtV t,R(λ)=0+a1λ+···+ar?1λr?1.

3) 分發(fā)者D計(jì)算ki=(Q(λi),R(λi))(i=1,··· ,n).

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

- 敵手A利用受賄參與者集合T中的受賄參與者所提供的子函數(shù){ki}i∈T, 給出關(guān)于挑戰(zhàn)指數(shù)b的猜測b′←A({ki}i∈T).根據(jù)本文方案的構(gòu)造可知秘密子函數(shù)ki=(Q(λi),R(λi)), 可以對Q(λi) 和R(λi) 分別進(jìn)行如下分析:

首先, 在方案中Q(λ)=Hβb(αb)+λV1+···+λtV t,λ1,··· ,λn為Fq上的兩兩不同的非零公開值,因此{(lán)Q(λi)}i∈T滿足以下等式:

在式(4) 中因?yàn)閂為t×m的隨機(jī)矩陣, Λ 為t階非退化矩陣, 又Q=ΛV+H且H是t×m的未知常矩陣, 則矩陣Q為t×m的隨機(jī)矩陣. 因此, 敵手通過矩陣Q得不到關(guān)于矩陣H的任何信息, 即敵手無法獲知關(guān)于挑戰(zhàn)指數(shù)b的任何信息.

其次,R(λi) 為多項(xiàng)式R(λ) = 0+a1λ+···+ar?1λr?1在λi點(diǎn)處的取值, 因?yàn)槎囗?xiàng)式R(λ) 不包含挑戰(zhàn)指數(shù)b的信息, 故R(λi) 中不包含關(guān)于挑戰(zhàn)指數(shù)b的任何信息. 因此,{ki}i∈T中不包含關(guān)于挑戰(zhàn)指數(shù)b的任何信息. 綜上, 敵手猜對挑戰(zhàn)指數(shù)b的概率為Pr[b′=b]=1/2, 即可證得本文所構(gòu)造的方案具有完善的t-安全性.

綜上由定義4可知本文方案滿足完善安全的函數(shù)私密性.

5 方案比較

本節(jié)將基于多變量多項(xiàng)式的(t,r,n)-FSS 方案與現(xiàn)有的FSS 方案在效率和性質(zhì)方面進(jìn)行比較. 將它與現(xiàn)有的文獻(xiàn)[10,11,13–16] 在安全性、有無門限值及方案的通信復(fù)雜度進(jìn)行比較; 對其是否滿足簡潔性、壓縮性和函數(shù)私密性進(jìn)行比對. 假設(shè)所有FSS 方案分享的秘密函數(shù)均為點(diǎn)函數(shù)fα,β:{0,1}l →Fq,t表示私密門限值,n為參與者個(gè)數(shù),λ為偽隨機(jī)生成器的種子長度. 具體比較結(jié)果見表1.

6 總結(jié)

本文基于多變量多項(xiàng)式技術(shù)構(gòu)造了新的(t,r,n)-FSS 方案, 按照函數(shù)秘密分享形式化的安全定義對其進(jìn)行了相應(yīng)的安全證明與分析. 將本文方案與現(xiàn)有相關(guān)工作作對比, 經(jīng)過分析發(fā)現(xiàn)本文方案的通信復(fù)雜度與方案重構(gòu)門限值r和私密門限值t之間的比值相關(guān), 當(dāng)重構(gòu)門限值與私密門限值之間的比值較大時(shí), 該方案可以實(shí)現(xiàn)較低的通信復(fù)雜度. 此外, 本文方案可以同時(shí)滿足函數(shù)秘密分享的簡潔性、壓縮性及函數(shù)私密性.