一般存取結構上可公開驗證的多級秘密共享

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

陜西師范大學 計算機科學學院，西安710062

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

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

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

1 預備知識

1.1 存取結構

定義1[8]設秘密共享方案中參與者集合是P={P1,P2,…,Pn}，Γ是P 的子集族，若Γ中子集所包含的參與者可以恢復秘密，稱Γ為P 上的存取結構，Γ中的子集稱為授權子集。

定義2[8]設秘密共享方案中參與者集合是P={P1,P2,…,Pn}，集合P 上一個單調存取結構Γ是集合P的子集所組成的集合且滿足單調遞增性質A∈Γ，A?A＇?P?A＇∈Γ。一個非存取結構，記作Δ，是集合P 的子集所組成的集合且滿足單調遞減性質A＇∈Δ,A?A＇?A∈Δ，根據單調的性質，存取結構Γ和非存取結構Δ分別對應存在一個極小存取結構Γmin={A∈Γ|?B?A?B?Γ}及一個極大非存取結構Δmax={B∈Δ|?B?A?A?Δ}。

1.2 單調張成方案及線性秘密共享方案

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

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

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

根據以上理論，下面給出如何使用MSP 實現存取結構Γ={Γ1,Γ2,…,Γm}上的線性秘密共享方案。

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

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

1.3 雙線性對

設G1、G2是階為大素數q的加法群和乘法群，其中P、Q是加法群G1的生成元，存在映射e：G1×G1→G2，滿足以下性質：

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

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

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

1.4 相關困難問題及假設

設G1、G2是階為大素數q的加法群和乘法群，存在映射e：G1×G1→G2，存在如下數學困難問題：

1.5 安全多方計算

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

1.6 可公開驗證的多級秘密共享

在一個多級秘密共享方案中，分發者想要在n個參與者中根據m個存取結構Γ1,Γ2,…,Γm分別共享m個秘密S1,S2,…,Sm。下面提出一個可公開驗證的多級秘密共享方案模型。

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

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

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

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

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

一個實現存取結構Γ1,Γ2,…,Γm的可公開驗證的多級秘密共享Ω=(Stp,Dist,Sub,Rec)需滿足以下性質：

（1）正確性要求：如果分發者和參與者均是誠實的，則對任意一個j∈{1,2,…,m}及任意授權集A∈Γj中的所有參與者Pi合作可正確恢復秘密Sj，即Rec(pms,

（2）可驗證性：在分發階段之后和重構階段之前，任何人均可檢驗分發者或參與者是否有欺騙行為。

（3）安全性要求：

①在不可區分實驗的安全模型下，敵手在多項式時間算法內無法由公開的秘密份額的加密信息獲得關于份額及秘密的任何信息；

②敵手在多項式時間算法內無法通過少數不誠實參與者集合B（存在某個j，使得B?Γj）的份額得到其他參與者份額及秘密Sj的任何信息。

1.7 計算安全模型

可公開驗證的多級秘密共享Ω=(Stp,Dist,Sub,Rec)的計算安全模型是利用一個多項式時間的敵手A和挑戰者之間的游戲G 來刻畫的，具體如下：

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

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

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

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

定義敵手A打破多級秘密共享Ω的優勢為：

如果對任何多項式時間的敵手A，AdvA(λ)是一個關于λ可忽略的函數，那么就稱該可公開驗證的多級秘密共享方案Ω=(Stp,Dist,Sub,Rec)是計算安全的。

2 具體方案

2.1 系統初始化

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

（2）D隨機選擇s∈Z*q作為系統私鑰，并計算Ppub=sP，將Ppub作為系統公鑰，同時公布P和Ppub的值。

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

2.2 秘密分發階段

設τ代表時間周期，在初始狀態τ=0時，分發階段分為以下幾個步驟：

2.3 秘密份額的更新

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

2.4 秘密重構階段

（4）待授權子集Aj,l中的所有參與者通過份額驗證后，秘密恢復者通過等式（7）來計算秘密Sj的值。

2.5 方案中公開驗證部分

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

（1）在秘密分發階段，分發者D公布公開信息后，其他人對D公布的公開信息通過式（1）～（3）進行驗證，通過驗證后參與者用自己的私鑰解密公開信息得到自己的份額，因此在秘密分發階段通過驗證D公布的公開信息是否正確來防止分發者的欺騙行為。

（2）在份額更新階段，D公布更新的公開信息后，其他人對D公布的更新后的公開信息通過式進行驗證，通過驗證后參與者用自己的私鑰解密更新后的公開信息得到自己更新后的份額，因此在份額更新階段通過驗證D公布的更新后的公開信息是否正確來防止分發者的欺騙行為。

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

3 方案分析

3.1 正確性分析

當τ=0 時：

即驗證等式（1）、等式（2）的正確性。

即驗證等式（3）的正確性。

即驗證等式（4）的正確性。

即驗證等式（5）的正確性。

當τ=1,2…時：

即驗證等式（6）的正確性。

即驗證等式（7）的正確性。

3.2 安全性分析

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

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

3.3 性能分析

3.3.1 性質比較

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

（1）方案采用的是一般存取結構，這使得各參與者的權力各不相同，打破了門限方案因參與者權力相同所造成的限制，且方案中多個秘密之間相互獨立，可根據需要單獨恢復其中一個或多個秘密，在實際生活中更為實用。

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

（3）方案不需安全信道。用公鑰加密秘密份額，使分發者和參與者間不需要建立安全信道，參與者通過自己私鑰對公開信息進行解密便可得到秘密份額，從而降低了系統代價。

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

（5）多用性。因在秘密重構階段授權子集中的各參與者會隨機選擇一個ki∈，然后利用ki加工自己的真實份額產生偽份額，在秘密重構階段出示偽份額，因此即使在秘密重構階段攻擊者竊取了參與者的份額，也不會暴露參與者的真實份額。當參與者再次參與秘密重構時，會出示新的偽份額，實現了份額的多用。

3.3.2 計算復雜度比較

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

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

3.3.3 綜合比較分析

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

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

表2 計算復雜度比較Table 2 Comparison of computational complexity

4 總結

本文基于單調張成方案，利用雙線性對、哈希函數及安全多方計算提出一般存取結構上的可驗證多用的可更新的多級多秘密共享方案。利用雙線性對的性質和哈希函數實現對分發者公開信息的驗證及各參與者份額的驗證，利用安全多方計算實現了參與者份額的多用。同時，通過對單調張成方案中向量的改變實現各參與者份額的定期更新，提高系統的安全性。最后對方案的正確性、安全性以及性能進行分析，結果表明，該方案在性能方面具有一定優勢，實用性較高且計算復雜度相對較低。