面向理性用戶的秘密重構(gòu)設(shè)計(jì)模型

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

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

1 引言

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

3.1 秘密共享

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

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

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

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

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

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

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

其中，符號(hào)“⊥”表示空信息。

3.2 秘密重構(gòu)中的理性用戶

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

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

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

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

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

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

3.3 理性秘密重構(gòu)博弈

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

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

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

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

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

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

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

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

其中，i≠j。

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

4 理性秘密重構(gòu)設(shè)計(jì)模型與面向不同環(huán)境的設(shè)計(jì)模型

4.1 理性秘密重構(gòu)設(shè)計(jì)模型

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

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

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

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

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

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

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

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

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

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

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

當(dāng)所有用戶均是理性的，且無(wú)信譽(yù)系統(tǒng)時(shí)，可使用下述設(shè)計(jì)模型來(lái)構(gòu)造公平的理性秘密重構(gòu)協(xié)議。

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

1)F：若i

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

其中，1≤i≤n。

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

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

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

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

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

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

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

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

其中，1≤k′

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

此時(shí)，其最終收益滿足

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

4.3 面向信譽(yù)環(huán)境的設(shè)計(jì)模型

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

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

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

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

其中，1≤i≤n。

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

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

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

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

證明 1) 在已知最后重構(gòu)輪中，當(dāng)有t個(gè)理性用戶Pj已選擇行動(dòng)策略時(shí)，理性用戶Pi選擇行動(dòng)策略和的收益為

此時(shí)，他選擇行動(dòng)策略和使其自身信譽(yù)變化收益滿足

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

故自利的理性用戶Pi不會(huì)選擇行動(dòng)策略。

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

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

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

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

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

①如果k=t?2，對(duì)于理性用戶Pi來(lái)說(shuō)，若i=n，那么理性用戶Pi在已知最后重構(gòu)中選擇行動(dòng)策略和的收益為

此時(shí)，理性用戶iP的最終收益為

② 若t≠n，i=n?1時(shí)，理性用戶Pi的最終收益與“當(dāng)有t?1個(gè)理性用戶Pj已選擇行動(dòng)策略”情形中i=n的最終收益相同。此時(shí)，理性用戶Pi不會(huì)選擇行動(dòng)策略。

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

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

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

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

1)F：若i

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

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

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

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

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

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

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

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

5 設(shè)計(jì)實(shí)例

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

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

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

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

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

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

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

5.2 協(xié)議分析

1) 公平性

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

在提出的理性秘密重構(gòu)協(xié)議中，當(dāng)理性用戶Pi惡意地改變理性用戶Pj的信譽(yù)值rj時(shí)，其余理性用戶將會(huì)通過合理地降低理性用戶Pi的信譽(yù)值ir來(lái)提升自己的最終收益。因此，對(duì)于理性用戶Pi來(lái)說(shuō)，由于其自利性，他將不會(huì)對(duì)rj進(jìn)行惡意操作。因此，本文所提出的理性秘密共享協(xié)議的公平性將得以保證。

2) 正確性

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

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

3) 安全性

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

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

6 結(jié)束語(yǔ)

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