一般存取結(jié)構(gòu)上可公開驗(yàn)證的多級(jí)秘密共享

宋云，王寧寧，肖孟林，邵志毅

陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安710062

秘密共享是一種先將秘密分割，后分開保存的密碼技術(shù)，是數(shù)據(jù)保密和信息安全中重要的手段，它的目的是阻止因秘密過(guò)于集中而容易被攻擊者竊取，主要思想是將需要保密的數(shù)據(jù)以某種方式分割，分割后每一份由不同的參與者所管理，單一的參與者無(wú)法恢復(fù)秘密，只有特定的一組參與者合作才能恢復(fù)秘密。1979年，Blakley[1]和Shamir[2]分別基于射影幾何理論和Lagrange多項(xiàng)式插值公式提出(t,n)門限秘密共享方案，之后學(xué)者們開始研究不同性質(zhì)的(t,n)門限方案[3-7]。但門限方案在恢復(fù)密鑰的時(shí)候要求各授權(quán)子集人數(shù)相同且各參與者權(quán)利相當(dāng)，故在實(shí)際應(yīng)用中具有一定局限性，為提高秘密共享方案的靈活性和適應(yīng)性，文獻(xiàn)[8]首次提出一種基于一般存取結(jié)構(gòu)的秘密共享方案，此后更多基于一般存取結(jié)構(gòu)[9-13]的秘密共享方案被學(xué)者們所提出。然而已提出的大多數(shù)秘密共享方案都是單秘密共享，在實(shí)際應(yīng)用中當(dāng)需要共享多個(gè)秘密時(shí)，參與者需保存每個(gè)秘密對(duì)應(yīng)的份額，存儲(chǔ)空間過(guò)大，因此學(xué)者們提出了多秘密共享的概念。多秘密共享是指每個(gè)參與者只需持有一個(gè)份額便可恢復(fù)多個(gè)秘密。多秘密共享方案分為一般多秘密共享方案[14-16]和多級(jí)秘密共享方案[17-20]：前者中一個(gè)存取結(jié)構(gòu)對(duì)應(yīng)多個(gè)秘密，不能根據(jù)實(shí)際需求單獨(dú)恢復(fù)一個(gè)或幾個(gè)秘密，故靈活性較低；后者中每級(jí)存取結(jié)構(gòu)對(duì)應(yīng)一個(gè)秘密。多個(gè)存取結(jié)構(gòu)可恢復(fù)多個(gè)秘密，不僅實(shí)現(xiàn)了每個(gè)參與者僅需持有一個(gè)秘密份額就可恢復(fù)多個(gè)秘密，滿足了實(shí)際生活中使用相同數(shù)量份額共享大量信息的需求，且秘密間相互獨(dú)立，在一定程度上避免了因某個(gè)秘密泄露而對(duì)其他秘密造成的影響，提高了效率的同時(shí)也保證了系統(tǒng)的安全性，因此更加實(shí)用。多級(jí)秘密共享技術(shù)所具有的特權(quán)分離、多個(gè)用戶獨(dú)立訪問及分布式特性就很自然地被學(xué)者們應(yīng)用于云計(jì)算、電子投票、分布式存儲(chǔ)以及圖像等領(lǐng)域[21-24]。

隨著秘密共享技術(shù)不斷深入研究，更多不同類型的秘密共享方案被提出，如多用的秘密共享、可公開驗(yàn)證的秘密共享、可更新秘密共享等。其中可公開驗(yàn)證的秘密共享最早于1996 年由Stadler[25]提出，該方案中任何人都可對(duì)公開信息的正確性和有效性進(jìn)行驗(yàn)證，且不會(huì)泄露有關(guān)秘密的任何信息；可更新秘密共享最早于1995 年由Herzberg 等人[26]提出，該方案在原秘密方案的基礎(chǔ)上，可對(duì)參與者的秘密份額進(jìn)行定期更新，使方案更加安全。2017年，Harn等人[27]基于二元多項(xiàng)式提出了一個(gè)一般多秘密共享方案，該方案雖然實(shí)現(xiàn)了份額的多用，但沒有實(shí)現(xiàn)份額的驗(yàn)證及更新。同年，Mashhadi等人[28]基于單調(diào)張成方案提出一種多級(jí)秘密共享方案，該方案可對(duì)參與者的份額進(jìn)行驗(yàn)證，且份額多用，但未實(shí)現(xiàn)份額的更新過(guò)程，且方案需要安全信道，系統(tǒng)代價(jià)過(guò)大。張敏等人[29]基于雙線性對(duì)提出的一般多秘密共享方案可對(duì)公開信息及份額進(jìn)行公開驗(yàn)證，支持秘密份額定期更新，但方案中秘密份額不支持多用性。王彩芬等人[30]提出的一般多秘密共享方案，雖然實(shí)現(xiàn)了口令授權(quán)、份額更新及驗(yàn)證等性能，但同文獻(xiàn)[29]一樣未實(shí)現(xiàn)份額的多用性。Chen等人[31]提出了一個(gè)多級(jí)秘密共享方案，該方案在不同階段共享不同秘密的同時(shí)實(shí)現(xiàn)了對(duì)秘密份額的驗(yàn)證。雖然上述已提出的方案在不同程度上具備了多秘密、可更新、可驗(yàn)證及多用等基本特性，但這些方案大多是門限共享方案，由于門限方案中存取結(jié)構(gòu)的特殊性，使得各參與者權(quán)力及地位完全平等一致，但在實(shí)際生活中，大多都要求各參與者之間擁有不同的權(quán)重及地位，因此，研究一般存取結(jié)構(gòu)上具有較好性質(zhì)且安全高效的多級(jí)秘密共享在理論和實(shí)際中都有著重要的意義。對(duì)于研究一般存取結(jié)構(gòu)的秘密共享方案目前采用的方法有基于橢圓曲線、基于插值多項(xiàng)式、基于向量空間、基于線性碼、基于單調(diào)張成方案等多種方法，而在2005年，Xiao 和Liu 已在文獻(xiàn)[32]中驗(yàn)證了實(shí)現(xiàn)存取結(jié)構(gòu)的任意線性多秘密共享方案存在當(dāng)且僅當(dāng)存在一個(gè)可計(jì)算上述存取結(jié)構(gòu)的單調(diào)布爾函數(shù)的單調(diào)張成方案，也就是說(shuō)設(shè)計(jì)線性多秘密共享和構(gòu)建出相應(yīng)的單調(diào)張成方案是等價(jià)的，所有的線性多秘密共享最終也都可歸結(jié)到對(duì)相應(yīng)單調(diào)張成方案的研究。

鑒于此，本文首先提出一個(gè)可公開驗(yàn)證的多級(jí)秘密共享方案模型，而后在單調(diào)張成方案及雙線性對(duì)的基礎(chǔ)上，提出一般存取結(jié)構(gòu)上的可公開驗(yàn)證的可更新多級(jí)秘密共享方案。利用安全多方計(jì)算構(gòu)造偽份額來(lái)實(shí)現(xiàn)方案的多用性，同時(shí)在CDH（computational Diffie-Hellman）和DBDH（decisional bilinear Diffie-Hellman）問題及假設(shè)下，證明本文方案是安全有效的。方案中分發(fā)者公布的公開信息的有效性和正確性及參與者出示份額的正確性均可公開驗(yàn)證，有效防止了分發(fā)者及參與者的欺騙行為；參與者通過(guò)使用自己的私鑰對(duì)公開信息進(jìn)行解密從而得到秘密份額，因此分發(fā)者和參與者間無(wú)需維護(hù)安全信道；分發(fā)者構(gòu)造臨時(shí)份額實(shí)現(xiàn)秘密份額定期更新，加大攻擊者竊取秘密的難度；方案采用的是一般存取結(jié)構(gòu)，打破了門限方案因參與者權(quán)力相當(dāng)所造成的限制，故在實(shí)際中更為實(shí)用。

1 預(yù)備知識(shí)

1.1 存取結(jié)構(gòu)

定義1[8]設(shè)秘密共享方案中參與者集合是P={P1,P2,…,Pn}，Γ是P 的子集族，若Γ中子集所包含的參與者可以恢復(fù)秘密，稱Γ為P 上的存取結(jié)構(gòu)，Γ中的子集稱為授權(quán)子集。

定義2[8]設(shè)秘密共享方案中參與者集合是P={P1,P2,…,Pn}，集合P 上一個(gè)單調(diào)存取結(jié)構(gòu)Γ是集合P的子集所組成的集合且滿足單調(diào)遞增性質(zhì)A∈Γ，A?A＇?P?A＇∈Γ。一個(gè)非存取結(jié)構(gòu)，記作Δ，是集合P 的子集所組成的集合且滿足單調(diào)遞減性質(zhì)A＇∈Δ,A?A＇?A∈Δ，根據(jù)單調(diào)的性質(zhì)，存取結(jié)構(gòu)Γ和非存取結(jié)構(gòu)Δ分別對(duì)應(yīng)存在一個(gè)極小存取結(jié)構(gòu)Γmin={A∈Γ|?B?A?B?Γ}及一個(gè)極大非存取結(jié)構(gòu)Δmax={B∈Δ|?B?A?A?Δ}。

1.2 單調(diào)張成方案及線性秘密共享方案

MSP 是一種計(jì)算模型，于1993 年由Karchmer 和Wigderson[33]所提出。

定義3一個(gè)可計(jì)算布爾函數(shù)的單調(diào)張成方案（monotone span program，MSP）可記作Μ(κ,Μ,Ψ)，其中κ=GF(q)是有限域，Μ是κ上的d×u階矩陣，P={P1,P2,…,Pn}是參與者集合，Ψ是{矩陣的行標(biāo)} →{P1,P2,…,Pn}的一個(gè)滿射，即給出矩陣Μ中的行用P 中參與者標(biāo)記的方式。

定義4假設(shè)Γ={Γ1,Γ2,…,Γm}是存取結(jié)構(gòu)集合。Μ(κ,Μ,Ψ)是對(duì)于u維目標(biāo)向量ej可以實(shí)現(xiàn)存取結(jié)構(gòu)Γj的一個(gè)MSP，若對(duì)所有的集合A?P有A∈Γj(1 ≤j≤m)當(dāng)且僅當(dāng)存在向量wA使得ej=wA·ΜA，其中ΜA表示由A中參與者所對(duì)應(yīng)的行所構(gòu)成的矩陣。故，其中Vi是根據(jù)Ψ的Μ標(biāo)號(hào)為Pi的行向量在κ上生成的向量空間。

根據(jù)以上理論，下面給出如何使用MSP 實(shí)現(xiàn)存取結(jié)構(gòu)Γ={Γ1,Γ2,…,Γm}上的線性秘密共享方案。

分發(fā)階段：分發(fā)者擁有秘密集合S={S1,S2,…,Sm}，其中秘密個(gè)數(shù)m小于單調(diào)張成方案Μ(κ,Μ,Ψ)中矩陣Μ的階數(shù)u。分發(fā)者構(gòu)造滿足Sj=(ej,r)的u維向量r，計(jì)算Μi·rT的值給Pi，其中1 ≤j≤m,1 ≤i≤n，Μi是標(biāo)號(hào)矩陣Μ的第i行，rT表示r的轉(zhuǎn)置。

重構(gòu)階段：對(duì)于授權(quán)子集A∈Γj，存在向量wA∈κ|A|，使得ej=wA·ΜA，則秘密Sj=(ej·r)=ej·rT=(wA·ΜA)·rT=wA(ΜA·rT)。因此，通過(guò)對(duì)A中參與者份額的線性計(jì)算即可重構(gòu)秘密Sj。

1.3 雙線性對(duì)

設(shè)G1、G2是階為大素?cái)?shù)q的加法群和乘法群，其中P、Q是加法群G1的生成元，存在映射e：G1×G1→G2，滿足以下性質(zhì)：

（1）非線性：對(duì)于a,b∈和P,Q∈G1，e(aP,bQ)=e(P,Q)ab。

（2）非退化性：?P,Q∈G1，滿足e(P,Q)≠1。

（3）可計(jì)算性：對(duì)于?P,Q∈G1，都存在有效的算法計(jì)算e(P,Q)。

1.4 相關(guān)困難問題及假設(shè)

設(shè)G1、G2是階為大素?cái)?shù)q的加法群和乘法群，存在映射e：G1×G1→G2，存在如下數(shù)學(xué)困難問題：

1.5 安全多方計(jì)算

安全多方計(jì)算[34-36]可以定義為允許多個(gè)成員在互不信任的情況下以安全的方式進(jìn)行計(jì)算，輸出計(jì)算結(jié)果，并保證任何一方均無(wú)法得到除應(yīng)得的計(jì)算結(jié)果之外的其他任何信息。這意味著其能保證輸出的正確性且即使某些玩家作弊，成員輸入的私密性也能得到保障。

1.6 可公開驗(yàn)證的多級(jí)秘密共享

在一個(gè)多級(jí)秘密共享方案中，分發(fā)者想要在n個(gè)參與者中根據(jù)m個(gè)存取結(jié)構(gòu)Γ1,Γ2,…,Γm分別共享m個(gè)秘密S1,S2,…,Sm。下面提出一個(gè)可公開驗(yàn)證的多級(jí)秘密共享方案模型。

（1）初始化算法Dist 是以安全參數(shù)λ、參與者集合P和m個(gè)存取結(jié)構(gòu)Γ1,Γ2,…,Γm為輸入，輸出公共參數(shù)pms←Stp(1λ,P,Γ1,Γ2,…,Γm)。

（2）分發(fā)算法Dist 是以pms、在參與者集合中共享的秘密S1,S2,…,Sm為輸入，輸出秘密份額加密集合以及一些公共的輸出Proof，這些可能的公共輸出能夠用于加密份額正確性驗(yàn)證，即,Proof)←Dist(pms,S1,S2,…,Sm)。

（3）偽份額生成算法Sub 是以每個(gè)參與者利用自己的私鑰解密后所得的秘密份額的集合為輸入，依據(jù)所要恢復(fù)的不同秘密輸出相應(yīng)的偽份額，即subij←Sub(shi,j)。偽份額生成算法可以隱藏于分發(fā)算法中。

（4）驗(yàn)證算法Ver 是以pms、Proof 以及加密后的份額或偽份額subij為輸入，輸出Ture 或⊥。如果Ver(pms,Proof,Ei(shi))=True及Ver(pms,Proof,subij)=True 成立，則shi是參與者Pi相對(duì)于參數(shù)pms及Proof 的有效份額。

（5）重構(gòu)算法Rec 以pms、Proof、指標(biāo)j∈{1,2,…,m}及某個(gè)子集A∈Γj中的參與者的偽份額為輸入，輸出第j個(gè)秘密的可能取值，即S＇j=Rec(pms,

一個(gè)實(shí)現(xiàn)存取結(jié)構(gòu)Γ1,Γ2,…,Γm的可公開驗(yàn)證的多級(jí)秘密共享Ω=(Stp,Dist,Sub,Rec)需滿足以下性質(zhì)：

（1）正確性要求：如果分發(fā)者和參與者均是誠(chéng)實(shí)的，則對(duì)任意一個(gè)j∈{1,2,…,m}及任意授權(quán)集A∈Γj中的所有參與者Pi合作可正確恢復(fù)秘密Sj，即Rec(pms,

（2）可驗(yàn)證性：在分發(fā)階段之后和重構(gòu)階段之前，任何人均可檢驗(yàn)分發(fā)者或參與者是否有欺騙行為。

（3）安全性要求：

①在不可區(qū)分實(shí)驗(yàn)的安全模型下，敵手在多項(xiàng)式時(shí)間算法內(nèi)無(wú)法由公開的秘密份額的加密信息獲得關(guān)于份額及秘密的任何信息；

②敵手在多項(xiàng)式時(shí)間算法內(nèi)無(wú)法通過(guò)少數(shù)不誠(chéng)實(shí)參與者集合B（存在某個(gè)j，使得B?Γj）的份額得到其他參與者份額及秘密Sj的任何信息。

1.7 計(jì)算安全模型

可公開驗(yàn)證的多級(jí)秘密共享Ω=(Stp,Dist,Sub,Rec)的計(jì)算安全模型是利用一個(gè)多項(xiàng)式時(shí)間的敵手A和挑戰(zhàn)者之間的游戲G 來(lái)刻畫的，具體如下：

（1）敵手A 公布參與者集合P 和存取結(jié)構(gòu)Γj(1 ≤j≤m)。

（2）挑戰(zhàn)者運(yùn)行pms←Stp(1λ,P,Γj(1 ≤j≤m)) 并發(fā)送pms給敵手A。

（3）敵手A廣播一個(gè)腐敗的參與者子集B?P。

（6）敵手A輸出b＇∈{0,1}。

定義敵手A打破多級(jí)秘密共享Ω的優(yōu)勢(shì)為：

如果對(duì)任何多項(xiàng)式時(shí)間的敵手A，AdvA(λ)是一個(gè)關(guān)于λ可忽略的函數(shù)，那么就稱該可公開驗(yàn)證的多級(jí)秘密共享方案Ω=(Stp,Dist,Sub,Rec)是計(jì)算安全的。

2 具體方案

2.1 系統(tǒng)初始化

（1）D首先構(gòu)造一個(gè)對(duì)于u維目標(biāo)向量ej(1 ≤j≤m)可實(shí)現(xiàn)存取結(jié)構(gòu)Γj的單調(diào)張成方案Μ(Zq,Μ,Ψ)，其中Μ是Zq上矩陣，且Ψ(i)=Pi，取目標(biāo)向量ej為單位向量，且第j個(gè)分量為1，其余分量全為0，如e2=[0,1,…,0]。

（2）D隨機(jī)選擇s∈Z*q作為系統(tǒng)私鑰，并計(jì)算Ppub=sP，將Ppub作為系統(tǒng)公鑰，同時(shí)公布P和Ppub的值。

（3）每個(gè)參與者Pi(1 ≤i≤n)隨機(jī)選取di∈[1,q-1]作為自己的私鑰并將其秘密保存，計(jì)算并公布自己的公鑰Yi=diPpub，確保Yi≠Yj(i≠j)。

2.2 秘密分發(fā)階段

設(shè)τ代表時(shí)間周期，在初始狀態(tài)τ=0時(shí)，分發(fā)階段分為以下幾個(gè)步驟：

2.3 秘密份額的更新

為提高系統(tǒng)安全性，可將共享秘密Sj的生命分為若干周期，為防止因參與者受到攻擊而泄露秘密份額，分發(fā)者D將定期更新參與者的秘密份額。下面假設(shè)在τ=1,2…時(shí)刻對(duì)參與者Pi的秘密份額進(jìn)行更新，其中1 ≤j≤m。

2.4 秘密重構(gòu)階段

（4）待授權(quán)子集Aj,l中的所有參與者通過(guò)份額驗(yàn)證后，秘密恢復(fù)者通過(guò)等式（7）來(lái)計(jì)算秘密Sj的值。

2.5 方案中公開驗(yàn)證部分

公開驗(yàn)證是本文秘密共享方案一個(gè)較為重要的性能，可防止分發(fā)者及參與者的欺騙行為，下面將具體描述本文方案在構(gòu)造過(guò)程中幾次公開驗(yàn)證。

（1）在秘密分發(fā)階段，分發(fā)者D公布公開信息后，其他人對(duì)D公布的公開信息通過(guò)式（1）～（3）進(jìn)行驗(yàn)證，通過(guò)驗(yàn)證后參與者用自己的私鑰解密公開信息得到自己的份額，因此在秘密分發(fā)階段通過(guò)驗(yàn)證D公布的公開信息是否正確來(lái)防止分發(fā)者的欺騙行為。

（2）在份額更新階段，D公布更新的公開信息后，其他人對(duì)D公布的更新后的公開信息通過(guò)式進(jìn)行驗(yàn)證，通過(guò)驗(yàn)證后參與者用自己的私鑰解密更新后的公開信息得到自己更新后的份額，因此在份額更新階段通過(guò)驗(yàn)證D公布的更新后的公開信息是否正確來(lái)防止分發(fā)者的欺騙行為。

（3）在秘密重構(gòu)階段，秘密恢復(fù)者收到參與者的份額后，首先通過(guò)等式（4）或等式（6）是否成立來(lái)驗(yàn)證參與者份額的正確性，若等式（4）或等式（6）成立，則證明參與者出示的份額是正確的，因此在秘密重構(gòu)階段通過(guò)驗(yàn)證參與者提供的份額是否正確來(lái)防止參與者的欺騙行為。

3 方案分析

3.1 正確性分析

當(dāng)τ=0 時(shí)：

即驗(yàn)證等式（1）、等式（2）的正確性。

即驗(yàn)證等式（3）的正確性。

即驗(yàn)證等式（4）的正確性。

即驗(yàn)證等式（5）的正確性。

當(dāng)τ=1,2…時(shí)：

即驗(yàn)證等式（6）的正確性。

即驗(yàn)證等式（7）的正確性。

3.2 安全性分析

命題2若存在攻擊算法能夠攻破本文方案，則可以構(gòu)造一個(gè)模擬算法以不可忽略的優(yōu)勢(shì)在判定性BDH攻擊游戲中獲得成功。

證明利用規(guī)約思想證明方案的安全性。假設(shè)存在一個(gè)多項(xiàng)式時(shí)間敵手AΩ，他能夠以優(yōu)勢(shì)ε攻破本文方案。則可構(gòu)造模擬算法B，B 在判定性BDH游戲中的優(yōu)勢(shì)可以達(dá)到。具體地，令A(yù)Ω是計(jì)算安全的可公開驗(yàn)證的多級(jí)秘密共享方案Ω針對(duì)秘密區(qū)分實(shí)驗(yàn)（Game G ）具有多項(xiàng)式時(shí)間攻擊能力的敵手，構(gòu)造多項(xiàng)式時(shí)間算法下的攻擊者（模擬器）B 以不可忽略的概率計(jì)算DBDH 問題，且構(gòu)造過(guò)程將用AΩ作為子程序，具體如下：

3.3 性能分析

3.3.1 性質(zhì)比較

本小節(jié)將所提出多級(jí)秘密共享方案與文獻(xiàn)[20，27-29]中方案就性質(zhì)方面進(jìn)行比較，結(jié)果如表1所示。下面具體討論本文方案的一些重要特性。

（1）方案采用的是一般存取結(jié)構(gòu)，這使得各參與者的權(quán)力各不相同，打破了門限方案因參與者權(quán)力相同所造成的限制，且方案中多個(gè)秘密之間相互獨(dú)立，可根據(jù)需要單獨(dú)恢復(fù)其中一個(gè)或多個(gè)秘密，在實(shí)際生活中更為實(shí)用。

（2）防欺騙。分發(fā)者公布的公開信息以及各參與者出示的份額均可進(jìn)行公開驗(yàn)證，有效防止分發(fā)者及參與者的欺騙行為。

（3）方案不需安全信道。用公鑰加密秘密份額，使分發(fā)者和參與者間不需要建立安全信道，參與者通過(guò)自己私鑰對(duì)公開信息進(jìn)行解密便可得到秘密份額，從而降低了系統(tǒng)代價(jià)。

（4）定期更新。方案中參與者的份額定期更新，使攻擊者的攻擊難度大大增強(qiáng)，提高了方案的安全性。

（5）多用性。因在秘密重構(gòu)階段授權(quán)子集中的各參與者會(huì)隨機(jī)選擇一個(gè)ki∈，然后利用ki加工自己的真實(shí)份額產(chǎn)生偽份額，在秘密重構(gòu)階段出示偽份額，因此即使在秘密重構(gòu)階段攻擊者竊取了參與者的份額，也不會(huì)暴露參與者的真實(shí)份額。當(dāng)參與者再次參與秘密重構(gòu)時(shí)，會(huì)出示新的偽份額，實(shí)現(xiàn)了份額的多用。

3.3.2 計(jì)算復(fù)雜度比較

從本文方案可以看出，該方案在構(gòu)造中引進(jìn)雙線性對(duì)以及單向Hash 函數(shù)，本小節(jié)將所提多級(jí)秘密共享方案與現(xiàn)有類似文獻(xiàn)[20，28-29]中的方案就計(jì)算復(fù)雜度方面進(jìn)行比較。在本文方案中，分發(fā)階段中分發(fā)者D計(jì)算雙線性對(duì)Ei運(yùn)算n次，單向Hash運(yùn)算n次，nu次乘法運(yùn)算，m次逆運(yùn)算；重構(gòu)階段中，假設(shè)參與恢復(fù)秘密的授權(quán)子集是Aj,l，在秘密重構(gòu)階段授權(quán)子集Aj,l中的每個(gè)參與者Pi計(jì)算自己的偽份額的雙線性對(duì)shi偽為|Aj,l|+1 次；驗(yàn)證階段里在秘密分發(fā)階段，驗(yàn)證公開信息的有效性和真實(shí)性共計(jì)算雙線性對(duì)mn+2n+2次，秘密恢復(fù)者驗(yàn)證來(lái)自授權(quán)子集Aj,l中的參與者所出示的偽份額的正確性時(shí)，共計(jì)算雙線性對(duì)2|Aj,l|次。如表2 所示，容易看出本文方案用相對(duì)較低的復(fù)雜度實(shí)現(xiàn)了方案的多用、更新、可公開驗(yàn)證等性質(zhì)。

表2中，Tb表示一次雙線性對(duì)運(yùn)算的時(shí)間，Th表示單向Hash運(yùn)算一次的時(shí)間，Te表示一次模冪運(yùn)算的時(shí)間，TP表示構(gòu)造單向函數(shù)Lagrange插值多項(xiàng)式運(yùn)算的時(shí)間，Tep是一次多線性映射運(yùn)算的時(shí)間[20]，TL表示Lagrange插值運(yùn)算一次的時(shí)間；n為參與者人數(shù)，t為門限值，m為共享的秘密數(shù)，u是MSP中矩陣列數(shù)。

3.3.3 綜合比較分析

本文基于單調(diào)張成方案，利用雙線性對(duì)、哈希函數(shù)提出了一種一般存取結(jié)構(gòu)上的可驗(yàn)證多用的可更新的多級(jí)秘密共享方案，利用雙線性對(duì)的性質(zhì)和哈希函數(shù)實(shí)現(xiàn)了份額的更新以及公開信息和份額的公開驗(yàn)證。根據(jù)表1和表2可以看出：（1）與文獻(xiàn)[27，29]方案相比較，本文方案是一般存取結(jié)構(gòu)，相對(duì)靈活和實(shí)用，且文獻(xiàn)[27]性能較為單一。（2）文獻(xiàn)[20，28]計(jì)算復(fù)雜度較小，但方案無(wú)法實(shí)現(xiàn)可公開驗(yàn)證及份額定期更新等實(shí)用性能。（3）文獻(xiàn)[29]中方案在雙線性對(duì)的基礎(chǔ)上引入Lagrange 插值運(yùn)算，目前Lagrange 插值算法的復(fù)雜度為O(lb2n)，求解雙線性對(duì)的可行算法是Boneh 和Franklin 提出的基于有限域內(nèi)超奇異橢圓曲線上的Weil Pairing算法[37]。根據(jù)Weil Pairing算法，雙線性對(duì)可由兩個(gè)時(shí)間復(fù)雜度為O(lbq)的函數(shù)得到，而復(fù)雜度又是衡量算法效率的主要標(biāo)準(zhǔn)之一。表2中計(jì)算出了本文方案和文獻(xiàn)[29]方案中雙線性和Lagrange 插值運(yùn)算的執(zhí)行次數(shù)，隨著方案規(guī)模的增大，結(jié)合雙線性和Lagrange插值運(yùn)算的時(shí)間復(fù)雜度[29，35]可以得到，本文方案效率更優(yōu)。（4）從通信性能上來(lái)看，文獻(xiàn)[20，27-28]均需要安全信道，而本文方案中的信息都是以公開公布的形式傳遞，也就是廣播的形式傳遞。眾所周知，廣播是最節(jié)約能量的、最有效的通信方式，從而降低了系統(tǒng)代價(jià)，提高了方案的效率。因此，與文獻(xiàn)[20，27-29]中方案相比，本文方案時(shí)間復(fù)雜度相對(duì)較低，效率較高，性能更優(yōu)。

表1 方案性能比較Table 1 Performance comparison of schemes

表2 計(jì)算復(fù)雜度比較Table 2 Comparison of computational complexity

4 總結(jié)

本文基于單調(diào)張成方案，利用雙線性對(duì)、哈希函數(shù)及安全多方計(jì)算提出一般存取結(jié)構(gòu)上的可驗(yàn)證多用的可更新的多級(jí)多秘密共享方案。利用雙線性對(duì)的性質(zhì)和哈希函數(shù)實(shí)現(xiàn)對(duì)分發(fā)者公開信息的驗(yàn)證及各參與者份額的驗(yàn)證，利用安全多方計(jì)算實(shí)現(xiàn)了參與者份額的多用。同時(shí)，通過(guò)對(duì)單調(diào)張成方案中向量的改變實(shí)現(xiàn)各參與者份額的定期更新，提高系統(tǒng)的安全性。最后對(duì)方案的正確性、安全性以及性能進(jìn)行分析，結(jié)果表明，該方案在性能方面具有一定優(yōu)勢(shì)，實(shí)用性較高且計(jì)算復(fù)雜度相對(duì)較低。