面向理性用戶的秘密重構設計模型

劉海，田有亮，唐瑩，Jianbing Ni，馬建峰

（1.貴州財經(jīng)大學信息學院，貴州 貴陽 550025；2.中國科學院軟件研究所可信計算與信息保障實驗室，北京 100190；3.貴州大學公共大數(shù)據(jù)國家重點實驗室，貴州 貴陽 550025；4.貴州財經(jīng)大學發(fā)展規(guī)劃與學科建設辦公室，貴州 貴陽 550025；5.女王大學電子與計算機學院，金斯頓 K7L 3N6）

1 引言

隨著通信技術的不斷發(fā)展，邊緣計算[1]、霧計算[2]、云計算[3]等多方參與的互聯(lián)網(wǎng)服務也在不斷普及。為保護多方參與的互聯(lián)網(wǎng)服務數(shù)據(jù)的安全性和用戶的隱私性，作為分布式密碼體制重要組成的秘密共享得到了廣泛研究[4-8]。

理性秘密共享方案[9]是將博弈論中的自利用戶與傳統(tǒng)秘密共享相結(jié)合而提出的一種更適用于現(xiàn)實應用的秘密共享方案。其目的是解決傳統(tǒng)秘密共享方案在現(xiàn)實應用中，由于受到“利益最大化”的驅(qū)使，導致理性用戶選擇自利的行動策略，從而無法實現(xiàn)公平的秘密重構（即不能確保所有用戶均能重構出共享秘密）的問題。然而，若直接使用現(xiàn)有理性秘密共享方案[9-29]，會出現(xiàn)如下不公平的情形[30-32]。

1) 發(fā)送自己擁有的子秘密的用戶無法恢復共享秘密，而未發(fā)送自己擁有的子秘密的用戶卻能恢復共享秘密，即僅有部分參與理性秘密共享的理性用戶能恢復共享秘密。

2) 所有參與秘密共享的理性用戶均未能恢復出真實的共享秘密，但是某些理性用戶可通過欺騙行為，使其他發(fā)送自己擁有的子秘密的用戶會重構出一個錯誤的共享秘密，并將該錯誤的共享秘密視為真實的共享秘密。

造成上述問題的根本原因是：在現(xiàn)有研究中，由于缺乏有效的秘密重構設計模型，方案設計者在設計理性秘密共享方案時（或更準確地說，設計理性秘密重構協(xié)議時），往往依賴個人經(jīng)驗，不能充分考慮理性用戶在“利益最大化”驅(qū)使下的策略選擇，從而難以實現(xiàn)公平的理性秘密重構。

為解決上述問題，本文首先通過構建理性秘密重構博弈模型，結(jié)合理性用戶的自利性偏好，分析自利的理性用戶執(zhí)行秘密重構協(xié)議時追求“利益最大化”的策略選擇，構造出3 種不同應用場景下面向理性用戶的秘密重構設計模型，并從理論上證明了所提設計模型的有效性。此外，為表明所提設計模型的實用性，本文還基于所提設計模型構造了一個公平的秘密重構協(xié)議。本文的主要貢獻如下。

1) 提出面向純理性用戶環(huán)境的理性秘密重構設計模型，并證明該模型能幫助設計者綜合考慮用戶的自利行為，從而構造不依賴第三方且能確保公平性的理性秘密重構協(xié)議。

2) 構造面向信譽環(huán)境的理性秘密重構設計模型，并證明了該模型的有效性，能協(xié)助設計者構建基于信譽的理性秘密重構協(xié)議，實現(xiàn)公平的秘密重構。

3) 構造面向可信用戶環(huán)境的理性秘密重構設計模型，并證明該模型可幫助設計者有效約束理性用戶的自利性，從而設計適用于具有可信用戶參與的理性秘密重構協(xié)議。

2 相關工作

根據(jù)約束理性用戶在秘密重構階段的自利行為的方法，現(xiàn)有理性秘密重構協(xié)議可大致分為：面向純理性用戶環(huán)境的理性秘密重構協(xié)議、面向信譽環(huán)境的理性秘密重構協(xié)議和面向可信用戶環(huán)境的理性秘密重構協(xié)議。

2.1 面向純理性用戶環(huán)境的理性秘密重構協(xié)議

面向純理性用戶環(huán)境的理性秘密重構協(xié)議是指參與執(zhí)行該類協(xié)議的用戶均是理性用戶，無可信用戶參與且無信譽系統(tǒng)。該類理性秘密重構協(xié)議最早是由Halpern 和Teague[10]提出的，其基本思想是：每個理性用戶在秘密重構階段中發(fā)送包含大量虛假子秘密和真實子秘密的秘密集合給其余用戶，使所有用戶只有遵循協(xié)議的執(zhí)行，才能分辨出真實的子秘密，從而共同恢復出共享秘密。在他們的方案中，每個理性用戶采用“投硬幣”的方式確定是否交互真實的子秘密。若有理性用戶不發(fā)送子秘密，則終止交互。采用上述方法，所有理性用戶只能遵循協(xié)議的執(zhí)行，直至每個理性用戶同時發(fā)送真實的子秘密給其余用戶；否則，將沒有任何用戶能恢復出共享秘密。然而，該方案并不適用于t=n=2 的情形。其中，t表示門限值，即表示可恢復共享秘密所需的最少子秘密數(shù)量；n表示分發(fā)的子秘密的總數(shù)量。為解決該問題，Maleka 等[11-12]通過每多交互一輪將增加用戶的通信開銷從而降低用戶的最終收益的方法，不斷地調(diào)整理性用戶選擇遵循協(xié)議執(zhí)行的概率，從而實現(xiàn)公平的理性秘密重構。

然而，上述重構協(xié)議僅適用于同步通信的情形。為解決該問題，Kol 和Naor[13-14]通過讓先發(fā)送子秘密的用戶可獲知交互真實子秘密，而后發(fā)送子秘密的用戶不能獲知交互真實子秘密的方法，設計了適用于異步通信的理性秘密重構協(xié)議。隨后，F(xiàn)uchsbauer 等[15]通過讓理性用戶在秘密重構階段中隨機驗證其余理性用戶發(fā)送子秘密正確性的方法，降低理性用戶執(zhí)行秘密重構協(xié)議時的計算開銷。Cai和Shi[16]讓秘密分發(fā)者利用概率加密的方法對分發(fā)的子秘密進行加密，分別降低秘密分發(fā)者在秘密分發(fā)階段和理性用戶在秘密重構階段的計算開銷。Dani 等[17]通過讓理性用戶延遲收到其余用戶發(fā)送的子秘密的方法來激勵其遵循協(xié)議的執(zhí)行，設計了一個僅需一輪交互的理性秘密重構協(xié)議。Kawachi等[18]提出的理性秘密重構協(xié)議中，通過指定理性用戶在秘密重構階段中交互子秘密的先后順序，使理性用戶通過3 輪交互就可恢復共享秘密。

此外，Zhang 和Liu[19]對理性秘密重構協(xié)議的概率安全性進行研究；Zhang 等[20]、De 和Ruj[21]分別提出了適用于通信資源受限場景的理性重構協(xié)議。田有亮等[22]探討了理性用戶的風險偏好函數(shù)對秘密重構博弈結(jié)果的影響。

2.2 面向信譽環(huán)境的理性秘密重構協(xié)議

面向信譽環(huán)境的理性秘密重構協(xié)議最早是由Nojoumian 等[23]提出的，其基本思想是：將秘密重構視為一類特殊的社會活動，通過對理性用戶的信譽（即其長期收益）的增減來約束他們在秘密重構中的自利性。因此，該類協(xié)議又稱為社會理性秘密重構協(xié)議。隨后，Nojoumian[24]采用數(shù)據(jù)擬合的方法，構造參與社會理性秘密重構的理性用戶的收益函數(shù)。Wang 和Xu[25]、Tian 等[26]分別結(jié)合貝葉斯博弈模型，分析了理性用戶在執(zhí)行社會理性秘密重構協(xié)議時的策略選擇。Wang 和Cai[27]指出理性用戶可能會進行多次社會理性秘密重構活動。因此，他們結(jié)合重復博弈模型設計了一個適用于多秘密重構的社會理性秘密重構協(xié)議。Yu 和Zhou[28]對執(zhí)行社會理性秘密重構協(xié)議中的合謀行為進行研究，設計了概率安全的社會理性秘密共享協(xié)議。彭長根等[29]通過綜合理性用戶的長期收益和短期收益，設計了一個適用于無秘密分發(fā)者場景的分布式理性秘密重構協(xié)議。隨后，Jin 等[33]研究發(fā)現(xiàn)當理性用戶考慮自己的長期收益時，理性用戶參與秘密重構的收益函數(shù)將發(fā)生改變。因此，他們對文獻[24]構造的收益函數(shù)進行修改，給出理性用戶的混合收益函數(shù)。此外，Nojoumian 等[34]還對社會理性秘密重構協(xié)議的無條件安全性進行研究。

2.3 面向可信用戶環(huán)境的理性秘密重構協(xié)議

面向可信用戶環(huán)境的理性秘密重構協(xié)議的基本是思想是：在秘密重構的過程中，由可信用戶充當“仲裁者”來判斷每個理性用戶交互的子秘密的正確性，確保遵循協(xié)議執(zhí)行的理性用戶能恢復共享秘密；而偏離協(xié)議執(zhí)行的理性用戶不能恢復共享秘密。Gordon 和Katz[35]通過讓秘密分發(fā)者Dealer 在重構協(xié)議執(zhí)行過程中觀察用戶的行為，使只有當所有理性用戶均發(fā)送自己的子秘密給其余用戶時，他們才能進入真實子秘密的交互階段。然而，Abraham等[36]研究發(fā)現(xiàn)，在使用上述協(xié)議時，由于理性用戶需經(jīng)過多輪交互來不斷提高自己選擇“誠實地發(fā)送子秘密”的信念，故該協(xié)議的交互輪數(shù)較多，極大地增加了理性用戶的通信負擔。為減少交互輪數(shù)，降低理性用戶的通信開銷，Micali 和Shelat[37]基于拍賣模型，通過讓理性用戶將自己擁有的子秘密發(fā)送給“拍賣官”，由其恢復共享秘密，并根據(jù)用戶發(fā)送的子秘密正確性來確定哪些用戶可獲得共享秘密。Ong 等[38]通過將理性用戶分成2 個不同的群組，使每個不同的群組中均存在誠實的可信用戶，由這些可信用戶監(jiān)測理性用戶在秘密重構中所選擇的策略，設計了一個僅需2 輪交互的秘密重構協(xié)議。然而，Zhang 和Liu[39]研究發(fā)現(xiàn)，當直接使用上述理性秘密重構協(xié)議時，會出現(xiàn)所有理性用戶均不發(fā)送子秘密的特殊情形。因此，他們結(jié)合序貫納什均衡設計了一個可避免上述“空威脅”情形的理性秘密重構協(xié)議。

但是，在設計上述理性秘密重構協(xié)議時，由于缺乏有效的參考模型，設計者只能根據(jù)自己的經(jīng)驗來設計理性秘密重構協(xié)議，未能有效地約束理性用戶追求“利益最大化”的自利行為（面向可信用戶環(huán)境的理性秘密共享協(xié)議除外）。這就導致如果直接使用上述理性秘密重構協(xié)議，就可能會出現(xiàn)如下不公平的情形：1) 正確發(fā)送子秘密的用戶未能獲得共享秘密，而未發(fā)送子秘密的用戶卻能獲得共享秘密，即僅有部分理性用戶能恢復共享秘密；2) 雖然所有參與秘密共享的理性用戶均未能恢復真實的共享秘密，但是某些理性用戶可通過欺騙行為，使其他發(fā)送自己擁有的子秘密的用戶會重構出一個錯誤的共享秘密，并將該錯誤的共享秘密視為真實的共享秘密。

3 預備知識

3.1 秘密共享

(t,n) 門限秘密共享方案由秘密分發(fā)協(xié)議和秘密重構協(xié)議組成。其中，分發(fā)協(xié)議是由秘密分發(fā)者Dealer 執(zhí)行，其目的是將共享秘密S拆分成n份子秘密s1,s2,…,sn后，分別將子秘密si(1≤i≤n)分發(fā)給用戶Pi；而秘密重構協(xié)議主要是由n個用戶P1,P2,…,Pn共同執(zhí)行，其目的是讓每個用戶Pi將秘密分發(fā)者Dealer 分發(fā)的子秘密si交互給其余用戶Pj(j≠i)，從而共同恢復共享秘密S。為更好地分析用戶執(zhí)行秘密重構協(xié)議時的策略，下面給出門限秘密共享的形式化描述模型。

定義1（門限秘密共享方案）門限秘密共享方案ΓSS={,ΠDis,ΠRes}是一個三元組，具體解釋如下。

①對于秘密分發(fā)者Dealer 來說，在確定持有子秘密的用戶以及門限值t后，可通過拆分函數(shù)Dis(?)將共享秘密S拆分成n份子秘密s1,s2,…,sn。即

② 對于用戶Pi(1≤i≤n)來說，當秘密分發(fā)者Dealer 執(zhí)行完成秘密分發(fā)協(xié)議ΠDis后，其可獲得子秘密si。即

3)ΠRes=ΠRes(P,Res(?),s1,s2,…,sn)是秘密重構協(xié)議。其中，Res(?)是秘密重構函數(shù)，它滿足以下性質(zhì)。

①對每個執(zhí)行秘密重構協(xié)議的用戶Pi(1≤i≤n)來說，若將自己擁有的子秘密發(fā)送給其余用戶，那么最終獲得的子秘密數(shù)量應不少于t個；若不將自己擁有的子秘密發(fā)送給其余用戶，則最終獲得的子秘密數(shù)量應不多于t?1個，即

②對每個執(zhí)行秘密重構協(xié)議的用戶Pi(1≤i≤n)來說，如果其擁有的子秘密數(shù)量不少于t個，則通過秘密重構函數(shù)Res(?)就能正確地恢復共享秘密S；否則，將不能得到關于共享秘密S的任何信息。即

其中，符號“⊥”表示空信息。

3.2 秘密重構中的理性用戶

從秘密共享的形式化模型可以看出，當秘密分發(fā)者Dealer 執(zhí)行秘密分發(fā)協(xié)議ΠDis后，每個用戶Pi僅獲得一個子秘密si。為能恢復共享秘密S，用戶Pi在執(zhí)行完秘密重構協(xié)議ΠRes時，至少要獲得其他t?1個用戶擁有的子秘密。因此，用戶Pi在執(zhí)行秘密重構協(xié)議時所選擇的行動策略將直接影響其最終擁有的子秘密數(shù)量。為更清晰地分析理性用戶執(zhí)行秘密重構協(xié)議時所選擇的行動策略，本文首先給出理性用戶的形式化模型。

定義2（理性用戶）參與執(zhí)行秘密重構協(xié)議的理性用戶Pi={θi,Ai,ωi,ui}是一個四元組，具體解釋如下。

1)θi表示理性用戶Pi執(zhí)行秘密重構協(xié)議時的個人偏好。即自利的理性用戶首先總是希望自己能獲得共享秘密；其次，希望在自己獲得共享秘密的同時讓盡可能少的其余用戶也獲得共享秘密。若令表示理性用戶Pi獨自獲得共享秘密時的收益；Ui表示所有參與秘密重構的理性用戶都獲得共享秘密時理性用戶Pi的收益；表示所有參與秘密重構的理性用戶都未獲得共享秘密時理性用戶Pi的收益；表示其他參與秘密重構的理性用戶Pj(j≠i)獲得共享秘密，而自己卻未獲得共享秘密時的收益；表示所有參與秘密重構的理性用戶都未獲得共享秘密，但是有部分理性用戶將重構出的錯誤秘密認為是真實共享秘密時理性用戶Pi的收益，則”。

3)ωi表示理性用戶Pi在執(zhí)行秘密重構協(xié)議時所擁有的背景知識。顯然，不同的理性用戶所擁有的背景知識是不同的。因此，? 1 ≤i,j≤n且i≠j，有ωi≠ωj。

4)ui表示理性用戶Pi執(zhí)行完秘密重構協(xié)議時的收益函數(shù)。

在執(zhí)行秘密重構協(xié)議時，理性用戶Pi在其個人偏好θ i的影響下，總在追求自身利益的最大化。因此，在執(zhí)行秘密重構協(xié)議的過程中，理性用戶Pi選擇的行動策略ai∈Ai應遵循如下原則。

3.3 理性秘密重構博弈

當執(zhí)行秘密重構協(xié)議時，自利的理性用戶總是遵循“利益最大化”原則來選擇自己的行動策略。從理性用戶的形式化模型中可以發(fā)現(xiàn)，其自身利益最大化受2 個因素的影響：1) 自己是否獲得共享秘密；2) 其余用戶是否獲得共享秘密。因此，為更好地約束理性用戶執(zhí)行秘密重構協(xié)議的自利行為，本文形式化描述理性秘密重構博弈模型。

定義3（理性秘密重構博弈）理性秘密重構博弈GRes={P,H,F,u}是一個四元組，具體解釋如下。

1)P={P1,P2,…,Pn}是參與理性秘密重構博弈GRes的用戶集合。其中，Pi∈P表示第i(1≤i≤n)個理性用戶。

2)H是秘密重構博弈過程的歷史序列集合。?h=(al,am,…,aj)∈H，其表示在某時刻已選擇行動策略的理性用戶Pl,Pm,…,Pj所選擇的行動策略al,am,…,aj組成的策略組合。在h之后的形成的所有行動策略組合記為A(h)={a|(h,a)∈H}。空字符Φ∈H，表示理性秘密重構博弈GRes的開始時刻。如果對于任意的歷史h′∈H使A(h′)=?，則稱該歷史h′是終止的，即表示理性秘密重構博弈GRes結(jié)束。Z表示由所有終止的歷史組成的集合。其中，Pl,Pm,…,Pj∈P；符號“?”表示空集。

3)F:(H/Z)→P是參與理性秘密重構博弈GRes的策略選擇順序函數(shù)。其含義是：為未終止的歷史h∈H/Z指派下一個選擇行動策略的理性用戶Pi∈P。若采用同步通信信道，即所有理性用戶同時選擇參與理性秘密重構博弈GRes的行動策略時，F(xiàn)(Φ)=P。

4)u=(u1,u2,…,un)是理性秘密重構博弈結(jié)束時，每個理性用戶Pi獲得的最終收益ui組成的收益組合。

下面，結(jié)合理性秘密重構博弈模型，給出理性秘密重構的公平性、安全性和正確性模型。

定義4（理性秘密重構的公平性）一個理性秘密重構博弈GRes是公平的，若?Pi,Pj∈P和a∈Z，有

其中，i≠j。

定義5（理性秘密重構的安全性）一個理性秘密重構博弈GRes是安全的，若?Pi∈P和，有

4 理性秘密重構設計模型與面向不同環(huán)境的設計模型

4.1 理性秘密重構設計模型

結(jié)合理性用戶模型和理性秘密重構博弈模型，本文給出理性秘密重構設計模型，具體如下。

定義7（理性秘密重構設計模型）理性秘密重構設計模型M={F,u,p}是一個三元組，具體解釋如下。

1)F是執(zhí)行理性秘密重構協(xié)議時，各理性用戶Pi選擇策略ai的先后順序。

2)u=(u1,u2,…,un)是理性秘密重構協(xié)議執(zhí)行結(jié)束時，每個理性用戶Pi選擇策略ai所獲得的收益ui組成的收益組合。

3)p=(p1,p2,…,pn)是設計的理性秘密重構協(xié)議根據(jù)理性用戶Pi所選擇的策略ai返回給其的額外收益pi所組成的組合。

簡單來說，在上述理性秘密重構設計模型中，p=(p1,p2,…,pn)是根據(jù)參與執(zhí)行秘密重構協(xié)議的用戶選擇執(zhí)行策略的先后順序以及可能選擇的策略，協(xié)議設計者需要設計的額外收益組合，從而通過該額外收益組合來約束理性用戶的自利性。在該模型中，要求協(xié)議設計者結(jié)合用戶選擇策略的先后順序F來設計額外收益組合p的原因如下。

以異步通信情形為例。在本文中，若理性用戶能準確地知道共享秘密將在哪輪重構交互中被恢復，則稱該重構輪為“已知最后重構輪”。

在異步通信情形下的理性秘密重構博弈中，由于后選擇策略的理性用戶可觀察到在其之前已進行策略選擇的理性用戶選擇的策略，故在已知最后重構輪中，當有t?1 個理性用戶Pi選擇策略時（即將自己擁有的子秘密si正確地發(fā)送給其余用戶），剩余的理性用戶Pj(j≠i)由于其自利性，將選擇策略，即不將自己擁有的子秘密正確地發(fā)送給其余用戶。因此，對于所有選擇策略的理性用戶Pk來說，此時他們的收益uk=。然而，對于理性用戶Pi來說，其收益為。

由此可知，若要設計出公平的理性秘密重構協(xié)議，協(xié)議設計者不僅要考慮參與執(zhí)行秘密重構協(xié)議的理性用戶可能選擇的策略，更要根據(jù)這些理性用戶在執(zhí)行秘密重構協(xié)議時選擇策略的先后順序來設計額外收益組合。這樣才能有效地約束理性用戶的自利行為，確保所有理性用戶均能重構出共享秘密。

為進一步證明所給出的理性秘密重構設計模型的有效性，本文針對面向純理性用戶環(huán)境、面向信譽環(huán)境以及面向可信用戶環(huán)境分別給出適用于異步通信情形的理性秘密重構協(xié)議的設計模型。

4.2 面向純理性用戶環(huán)境的設計模型

當所有用戶均是理性的，且無信譽系統(tǒng)時，可使用下述設計模型來構造公平的理性秘密重構協(xié)議。

定義8（面向純理性用戶環(huán)境的設計模型）面向純理性用戶環(huán)境的理性秘密重構設計模型M={F,u,p}是一個三元組，具體解釋如下。

1)F：若i

2)u=(u1,u2,…,un)是執(zhí)行完理性秘密重構協(xié)議后用戶的收益組合。它滿足

其中，1≤i≤n。

3)p=(p1,p2,…,pn)是設計的理性秘密重構約束機制根據(jù)用戶Pi選擇的策略ai，返回給理性用戶Pi的額外收益pi(ai)所組成的額外收益組合。它滿足

其中，ui(i←i+0)表示理性用戶Pi選擇行動策略的順序（無論是在該次重構博弈的第k+1輪中，還是在新開設的重構博弈的第一輪中）保持不變時的收益；ui(i←i∧k=1)表示理性用戶Pi在新開始的重構博弈的第一輪中率先選擇行動策略時的收益。此時，原來的其余理性用戶Pj(1≤j≤i?1)選擇策略的順序分別向后順延一位。此時，由于所有用戶均未能重構出真實的共享秘密，故理性用戶iP選擇的行動策略ia時的額外收益均為。

值得注意的是，在使用上述模型時，需對秘密分發(fā)協(xié)議做相應的約束。具體約束如下。

在秘密分發(fā)協(xié)議執(zhí)行之前，秘密分發(fā)者Dealer首先選擇一個隨機數(shù)Round 作為執(zhí)行該理性秘密重構協(xié)議時所需的最大交互輪數(shù)；然后在[1,Round?1]中隨機選擇整數(shù)K作為能重構出真實共享秘密的重構輪數(shù)。此外，秘密分發(fā)者Dealer 在理性用戶P1,P2,…,Pt?1中任選b個理性用戶Pim發(fā)送子秘密集合{sim_(1),…,sim_(K),sim_(K+1)}，給其余用戶發(fā)送子秘密集合。其中，；l是正整數(shù)；si_(k)是真實共享秘密S對應的子秘密，1≤j≤n。當j=im時，sj_(K+1)為重構協(xié)議的執(zhí)行終止符；而其余的子秘密均是錯誤的子秘密。此外，秘密分發(fā)者Dealer 還需分發(fā)可驗證所有子秘密正確性的驗證信息。當所有理性收到執(zhí)行終止符時，即可知道在第K輪中重構出真實的共享秘密S。

本文將上述重構協(xié)議設計模型所對應的重構約束機制稱為純理性機制，下面證明該機制能幫助協(xié)議設計者有效約束理性用戶的自利行為。

定理1在異步通信情形下的(t,n)理性秘密共享重構博弈GRes中，純理性機制能有效約束理性用戶的自利行為。

證明在純理性機制中，只有理性用戶Pim知道何時能正確地重構出真實的共享秘密S。因此，本文首先證明理性用戶Pim在純理性機制的約束下的策略選擇。

由于理性用戶Pim明確知道真實的共享秘密S是在已知重構輪——第k輪交互中才能恢復，因此在第k輪之前的交互輪k′中，其選擇策略和的最終收益分別為

其中，1≤k′

綜上所述，根據(jù)其自利性，理性用戶Pim在已知重構輪中只會選擇策略。

此時，其最終收益滿足

通過上述證明可以得出，本文給出的面向純理性用戶環(huán)境的設計模型能幫助協(xié)議設計者有效地約束理性用戶的自利行為，使設計出的理性秘密重構協(xié)議是公平的。

4.3 面向信譽環(huán)境的設計模型

在信譽環(huán)境中，假設每個理性用戶Pi具有一個公開可見的信譽值ri，且ri將會根據(jù)理性用戶Pi在社會活動中的行為被其余用戶進行提高或降低。令R={r1,r2,…,rn}為理性秘密重構博弈中理性用戶的信譽值集合；并且在秘密分發(fā)階段中，秘密分發(fā)者Dealer 已分發(fā)相應的驗證信息給理性用戶，使他們可驗證收到的子秘密和重構出的共享秘密的正確性。那么，面向信譽環(huán)境的理性秘密共享重構協(xié)議的設計參考模型如下。

定義9（面向信譽環(huán)境的設計模型）面向信譽環(huán)境的理性秘密重構設計模型M={F,u,p}是一個三元組，具體解釋如下。

1)F：若ri≤rj，則理性用戶Pi在執(zhí)行理性秘密重構協(xié)議時比理性用戶Pj先進行策略的選擇。

2)u=(u1,u2,…,un)是執(zhí)行完理性秘密重構協(xié)議時用戶的收益組合。它滿足

其中，1≤i≤n。

3)p=(p1,p2,…,pn)是設計的理性秘密重構約束機制根據(jù)用戶Pi選擇的策略ai，返回給理性用戶的額外收益pi(ai)所組成的額外收益組合。它滿足

其中，rmin=min{ui(ri←ri+n?1)}表示理性用戶Pi的信譽值ri提升n?1時其獲得的最小收益；rmax=max{ui(ri←ri?n+1)}表示理性用戶Pi的信譽值ri降低n?1時的最大評估；“←”表示賦值。

顯然，通過不斷調(diào)整用戶信譽值提高和降低的額度，一定存在一個最小的n′ 使成立。為便于描述，本文假設n′=n。本文將上述設計參考模型所對應的重構約束機制稱為信譽機制。下面，將證明所提出的信譽機制能幫助協(xié)議設計者有效地約束理性用戶在理性秘密重構博弈GRes的已知最后重構輪中的自利行為，實現(xiàn)公平的理性秘密重構。

定理2在異步通信情形下的(t,n)理性秘密共享重構博弈GRes中，信譽機制能有效約束理性的自利行為。

證明 1) 在已知最后重構輪中，當有t個理性用戶Pj已選擇行動策略時，理性用戶Pi選擇行動策略和的收益為

此時，他選擇行動策略和使其自身信譽變化收益滿足

因此，理性用戶的最終收益滿足

故自利的理性用戶Pi不會選擇行動策略。

2) 在已知最后重構輪中，有t?1個理性用戶Pj已選擇行動策略。

①若t=n，理性用戶Pi是已知最后重構輪中最后選擇行動策略的理性用戶。那么，理性用戶Pi選擇行動策略和的收益為

那么，理性用戶iP的最終收益為

② 若t≠n，即理性用戶Pi不是已知最后重構輪中最后選擇行動策略的用戶。那么，通過上述分析可知，理性用戶Pn將會選擇行動策略。此時，與有t個理性用戶Pj已選擇行動策略的情形相同，故理性用戶Pi不會選擇行動策略。

3) 在已知最后重構輪中，有k(0≤k≤t?1)個理性用戶Pj已選擇策略。

①如果k=t?2，對于理性用戶Pi來說，若i=n，那么理性用戶Pi在已知最后重構中選擇行動策略和的收益為

此時，理性用戶iP的最終收益為

② 若t≠n，i=n?1時，理性用戶Pi的最終收益與“當有t?1個理性用戶Pj已選擇行動策略”情形中i=n的最終收益相同。此時，理性用戶Pi不會選擇行動策略。

那么，根據(jù)逆向歸納法可知，當k=0 且i=1時，理性用戶Pi仍只會選擇行動策略。

4.4 面向可信用戶環(huán)境的設計模型

當有可信用戶參與理性秘密重構協(xié)議的執(zhí)行時，可利用可信用戶作為“仲裁者”來監(jiān)督協(xié)議的執(zhí)行過程。這不僅能降低執(zhí)行理性秘密重構協(xié)議時理性用戶的交互輪數(shù)，還能有效約束理性用戶的自利性。假設在秘密分發(fā)階段中，秘密分發(fā)者Dealer分發(fā)驗證信息給所有的理性用戶，使他們可驗證收到的子秘密和重構出的共享秘密的正確性。那么，適用于具有可信用戶環(huán)境的理性秘密重構協(xié)議設計參考模型如下所示。

定義10（面向可信用戶環(huán)境的設計模型）面向可信用戶環(huán)境的理性秘密重構設計模型M={F,u,p}是一個三元組，具體解釋如下。

1)F：若i

2)u=(u1,u2,…,un)是執(zhí)行完理性秘密重構協(xié)議后用戶的收益組合。它滿足

其中，1≤i≤n；策略表示可信用戶Ph將恢復出的共享秘密S發(fā)送給理性用戶Pi(i≠h,1≤i≤n)；策略表示理性用戶Pi未將正確的子秘密si發(fā)送給可信用戶Ph；策略表示可信用戶Ph保持沉默。

3)p=(p1,p2,…,pn)是設計的理性秘密重構約束機制根據(jù)用戶Pi選擇的行動策略ai，返回給理性用戶的額外收益p i(ai)所組成的額外收益組合。它滿足

本文將上述重構協(xié)議設計模型所對應的重構約束機制稱為可信機制，下面證明該機制能幫助協(xié)議設計者有效約束理性用戶的自利行為。

定理3在異步通信情形下的(t,n)理性秘密共享重構博弈GRes中，可信機制能有效約束理性的自利行為。

證明由于驗證信息的存在，使可信用戶可驗證理性用戶發(fā)送的子秘密的正確性。因此，理性用戶無法欺騙誠實用戶。并且，由于可信用戶將根據(jù)理性用戶選擇的行動策略決定是否將重構出的共享秘密S發(fā)送給理性用戶。如果理性用戶Pi選擇策略，即不發(fā)送自己擁有的子秘密給誠實用戶Ph，其最終獲得收益為

如果理性用戶Pi選擇策略，即發(fā)送自己擁有的子秘密給可信用戶Ph，其最終獲得收益為

值得注意的是，在上述給出的面向純理性用戶環(huán)境、面向信譽環(huán)境和面向可信用戶環(huán)境的理性秘密重構協(xié)議設計模型中，僅需將各設計模型中發(fā)送子秘密的順序F調(diào)整為所有理性用戶同時發(fā)送各自擁有的子秘密，就可用于同步通信情形下的理性秘密重構協(xié)議的設計。

5 設計實例

為表明所給出的設計模型具有可用性，本文將根據(jù)給出的面向信譽環(huán)境的設計模型來構造一個公平的理性秘密重構協(xié)議。

5.1 公平的理性秘密重構協(xié)議

假設在秘密分發(fā)階段中，秘密分發(fā)者Dealer 利用Shamir 方案[40]中的方法將共享秘密S進行拆分；利用可公開驗證秘密共享[41]的思想，選擇單向承諾函數(shù)C(?)和承諾值C(si)；最后，秘密分發(fā)者Dealer將子秘密si秘密地發(fā)送給理性用戶Pi，并廣播發(fā)送C(?)和C(si)。那么，本文所構造的理性秘密重構協(xié)議如下。

步驟1根據(jù)理性用戶的信譽值的高低決定發(fā)送子秘密的先后順序。即若ri≤rj，則理性用戶Pi將先發(fā)送自己的子秘密si。

步驟2Pi發(fā)送自己的子秘密si給其余用戶Pk(k≠i)；并等待接收其余理性用戶Pk發(fā)送的消息Infok并觀察自己的信譽值ri。

步驟3Pi等待接收理性用戶Pj發(fā)送的子秘密sj，并利用承諾函數(shù)驗證其正確性。

步驟4當理性用戶Pi收到所有正確的子秘密后，利用拉格朗日插值法重構出共享秘密S。

5.2 協(xié)議分析

1) 公平性

由定理2 可知，在基于異步信道通信的(t,n)理性秘密共享重構博弈中，信譽機制可有效地約束理性用戶在已知最后重構輪中的自利行為。即?Pi,Pj∈P，有

在提出的理性秘密重構協(xié)議中，當理性用戶Pi惡意地改變理性用戶Pj的信譽值rj時，其余理性用戶將會通過合理地降低理性用戶Pi的信譽值ir來提升自己的最終收益。因此，對于理性用戶Pi來說，由于其自利性，他將不會對rj進行惡意操作。因此，本文所提出的理性秘密共享協(xié)議的公平性將得以保證。

2) 正確性

由于承諾函數(shù)C(?)的存在，使理性用戶可在秘密分發(fā)階段中驗證秘密分發(fā)者所分發(fā)的子秘密正確性。而在秘密重構階段中，理性用戶也可通過收到的承諾驗證其余理性用戶發(fā)送的子秘密的正確性。

因此，本文提出的協(xié)議可確保理性用戶均接收到正確的子秘密，從而使協(xié)議執(zhí)行完成時所有理性用戶均可重構出正確的共享秘密。

3) 安全性

由于該協(xié)議是基于多項式函數(shù)對共享秘密進行拆分的，那么根據(jù)線性方程組解的性質(zhì)可知，即使用戶獲得數(shù)量少于t個的子秘密也不能得到關于共享秘密S的任何信息。即

因此，本文提出的基于信譽的理性秘密重構協(xié)議也是安全的。

6 結(jié)束語

由于缺少設計參考模型，導致協(xié)議設計者在設計理性秘密重構協(xié)議時往往依賴個人經(jīng)驗，難以充分考慮理性用戶在“利益最大化”驅(qū)使下的策略選擇。這就導致如果直接使用現(xiàn)有的理性秘密重構協(xié)議，不僅只有部分理性用戶能恢復共享秘密，甚至還會出現(xiàn)部分理性用戶將錯誤的秘密視為真實共享秘密的極端情形。為解決上述問題，本文基于理性用戶的形式化模型，通過構建理性秘密重構博弈模型來分析自利的用戶在執(zhí)行秘密重構協(xié)議時追求“利益最大化”的策略選擇，分別提出了適用于不同應用場景的理性秘密重構協(xié)議設計模型。理論證明和實例設計分別說明了本文給出的設計模型的有效性和實用性。