高先鋒，王伊蕾

1.魯東大學(xué) 現(xiàn)代教育技術(shù)部，山東 煙臺 264025

2.魯東大學(xué) 信息與電氣工程學(xué)院，山東 煙臺 264025

常數(shù)輪理性秘密分享機(jī)制

高先鋒1，王伊蕾2

1.魯東大學(xué) 現(xiàn)代教育技術(shù)部，山東 煙臺 264025

2.魯東大學(xué) 信息與電氣工程學(xué)院，山東 煙臺 264025

1 引言

秘密分享機(jī)制是多方安全計(jì)算協(xié)議的基礎(chǔ)，它是由Blakley和Shamir在1979年分別提出的。經(jīng)典的(m，n)秘密分享機(jī)制的參與者包括一個秘密分發(fā)者，記為Dealer和n個參與者，記為(P1，P2，…，Pn)。Dealer試圖在n個參與者之間分享秘密s，他首先將秘密分為n個秘密份額，然后將這些秘密份額告訴每個參與者。這n個參與者執(zhí)行秘密恢復(fù)協(xié)議，滿足一定的條件即可恢復(fù)秘密。秘密分享機(jī)制滿足以下兩個條件：（1）參與者獲得大于m≤n份（m稱為秘密分享的門限值）秘密份額，能夠恢復(fù)秘密；（2）獲得少于m份秘密份額的參與者恢復(fù)秘密的任何信息。

Shamir的秘密分享機(jī)制是應(yīng)用比較廣泛的一種，其工作原理在于一個m-1階多項(xiàng)式可以通過m個多項(xiàng)式上的點(diǎn)恢復(fù)。假設(shè)一個秘密s取自有限域F，其中||F＞n。秘密分發(fā)者隨機(jī)選擇一個m-1階的函數(shù)f(x)，使得f(0)=s，(s≠0)，然后把秘密份額f(i)給每一個參與者Pi，其中i=1，2，…，n。參與者接收到他們的份額后，運(yùn)行一個秘密恢復(fù)協(xié)議，從而可以恢復(fù)秘密值s。

傳統(tǒng)的秘密分享機(jī)制包括兩種參與者：誠實(shí)參與者（Honest player）和惡意參與者（Malicious player）。誠實(shí)參與者總是遵守協(xié)議，而惡意參與者可以采取任意的行為。Halpern和Teague[1]首次提出了理性參與者的概念，所謂理性參與者既不是完全誠實(shí)的也不是任意惡意的，而是根據(jù)事先設(shè)定的收益函數(shù)采取行動，他們的目標(biāo)是如何最大化自己的收益。在文獻(xiàn)[1]中，Halpern和Teague假設(shè)所有的參與者都是理性的，他們的收益函數(shù)需要滿足兩個條件：（1）參與者希望得到秘密s；（2）在自己得到秘密的基礎(chǔ)上，獲得秘密的參與者越少越好。

本文將秘密分享看做是一個常數(shù)輪重復(fù)博弈，在給定收益函數(shù)的基礎(chǔ)上，為參與者設(shè)定了不同的類型，給出了在不完全信息下常數(shù)輪RRSSS協(xié)議，并證明了其有效性。

2 相關(guān)工作

Halpern和Teague的研究表明因?yàn)榧儾呗圆皇侵貜?fù)弱劣刪除策略（Iterated Deletion of Weakly Dominated Strategies，IDOWDS），因此他們提出了一種基于混合策略的理性秘密分享機(jī)制。而且，他們認(rèn)為不存在兩個參與者之間的理性秘密分享機(jī)制。Gordon和Katz[2]放松了一些條件，使得秘密分發(fā)者以概率β在有限域F中選取一個秘密s∈S，以概率1-β選取一個任意元素（假秘密）?，滿足，從而可以有效地克服文獻(xiàn)[1]中的問題。Shareef[3]提出了一個基于點(diǎn)對點(diǎn)通信信道的理性秘密分享機(jī)制，不僅如此，該機(jī)制能夠抵抗多個任意長參與者（long player）或短參與者（short player）的合謀。但是不能抵制一個長參與者和一個短參與者的合謀。張志芳和劉木蘭提出了一個（2，2）理性秘密分享機(jī)制，該機(jī)制能夠?qū)崿F(xiàn)標(biāo)準(zhǔn)通信模型下的無條件安全[4]。

Maleka和Shareef[5]首先將重復(fù)博弈引入理性秘密分享機(jī)制中，他們提供了一個異步通信模型下的理性秘密分享機(jī)制?；舅枷胧窃谥貜?fù)博弈中引入懲罰策略，使得參與者因?yàn)閾?dān)心未來的懲罰，而在每一輪都采取合作策略。結(jié)論包括：（1）對于無限重復(fù)博弈或者有限重復(fù)博弈（參與者不知道最終輪），存在一個理性秘密分享機(jī)制，使得參與者能夠恢復(fù)秘密；（2）對于有限重復(fù)博弈（參與者知道最終輪），不存在理性秘密分享機(jī)制，使得參與者可以恢復(fù)秘密。然而，有時懲罰策略可能會變成“空洞威脅”，張志芳和劉木蘭將（2，2）理性秘密分享機(jī)制看做一個不完美信息的擴(kuò)展博弈，從而可以有效地消除空洞威脅[6]。張恩和蔡永泉提出了一種新型的理性秘密分享機(jī)制[7]，其中每一個參與者都不知道當(dāng)前輪是否為一個測試輪，這與文獻(xiàn)[5]中有限重復(fù)博弈（參與者不知道最終輪）的情況類似，因此也存在一個有效的理性秘密分享機(jī)制。另外，該機(jī)制還可以實(shí)現(xiàn)公平性和抗合謀的納什均衡（resilient equilibrium）。在理性秘密分享機(jī)制中，除了理性參與者，參與者還可能是惡意的，而且惡意的參與者可能會具有無限的計(jì)算能力。另外，在構(gòu)造理性秘密分享機(jī)制時，不僅需要考慮同步通信下的模型，還需要考慮異步通信下的模型。針對這些不同的情況，Gidney[8]提出了四個協(xié)議，分別考慮了上述的幾種情形，實(shí)現(xiàn)了有惡意參與者下的安全性和抗合謀性。

3 基本概念

對于理性參與者，首先要定義他們的效用函數(shù)，因?yàn)槔硇詤⑴c者所采取的行為完全依賴于能否最大化他們的收益。

3.1 效用和納什均衡

令μi(ο)代表博弈結(jié)果為ο時參與者Pi的效用，δi(ο)=1表示參與者Pi得到秘密，δi(ο)=0表示參與者Pi沒有得到秘密。令表示獲得秘密的參與者個數(shù)。根據(jù)文獻(xiàn)[2]，效用函數(shù)的定義符合以下假設(shè)：

（1）對于兩個博弈結(jié)果ο和ο′，如果滿足δi(ο)＞δi(ο′)，則有μi(ο)＞μi(ο′)；

（2）對于兩個博弈結(jié)果ο和ο′，如果滿足δi(ο)=δi(ο′)，且num(ο)＜num(ο′)，則有μi(ο)＞μi(ο′)。

第一個假設(shè)說明參與者希望得到秘密，即得到秘密的效用大于沒有得到秘密的效用。第二個假設(shè)說明，如果兩個博弈結(jié)果相同，那么參與者希望得到秘密的參與者越少越好。

為簡便起見，本文定義了輸出結(jié)果為ο時，參與者Pi的效用函數(shù)（其中i，j=1，2，…，n，且i≠j）：

（1）μi(ο)=U+，如果Pi得到秘密，而Pj沒有得到秘密；

（2）μi(ο)=U，如果Pi和Pj都得到秘密；

（3）μi(ο)=U-，如果Pi和Pj都沒有得到秘密；

（4）μi(ο)=U--，如果Pj得到秘密，而Pi沒有得到秘密。

為了保證參與者有參與理性秘密分享機(jī)制的動機(jī)，規(guī)定：U+＞U＞U-＞U--。

在每一輪博弈，每個參與者都會采取一個策略，所有參與者的策略組合表示為一個策略向量σ=(σ1，…，σi-1，σi，σi+1，…，σn)，其中σi表示參與者Pi的策略（注意σi表示參與者采取的混合策略），σ-i=(σ1，…，σi-1，σi+1，…，σn)表示除Pi以外其他參與者的策略向量表示參與者Pi采取策略，而其他參與者遵守策略組合σ-i。下面給出納什均衡的概念。

定義1（納什均衡）一個策略向量σ引入一個納什均衡，如果對于任何一個參與Pi和任何策略，都有：

納什均衡能夠保證每個參與者沒有偏離均衡策略的動機(jī)。

3.2 重復(fù)博弈

在重復(fù)博弈中[9]，參與者多次參加階段博弈，記為(Γ1，Γ2，…，ΓT)，其中T表示博弈的輪數(shù)，它可以是無限值（對應(yīng)無限重復(fù)博弈），也可以是有限值（對應(yīng)有限重復(fù)博弈）。歷史H用來記錄每一階段博弈參與者所采取的行動。為了能夠記錄每一階段參與者的行動，令表示在第k輪參與者采取的行動，其中表示參與者Pi在第k輪采取的純策略，a∈A，A表示參與者的所有策略集合。為簡便起見，歷史從第0輪開始且此時H=Φ，其中Φ表示空集。參與者根據(jù)歷史hk=(a0，a1，…，ak)決定他當(dāng)前輪的行動。在每一輪，參與者Pi獲得一個效用ui(i=1，2，…，n)。在有限重復(fù)博弈中，參與者的總收益是每個階段收益的和。

4 常數(shù)輪RRSSS

在常數(shù)輪RRSSS中，參與者知道哪一輪是最后一輪，因此在最后一輪，所有參與者都會采取不合作策略，因?yàn)橄乱惠啿┺膶⒔Y(jié)束，即使采取不合作的策略也不會擔(dān)心將來受到懲罰。根據(jù)逆向歸納法，可以推導(dǎo)出在所有輪，參與者都沒有合作的動機(jī)。然而文獻(xiàn)[10]和文獻(xiàn)[11]的結(jié)論表明，如果放松某些條件，在有限重復(fù)博弈中，合作是可以出現(xiàn)的。本文將他們的結(jié)論引入到有限重復(fù)理性秘密分享機(jī)制中，構(gòu)造了常數(shù)輪的RRSSS機(jī)制。首先介紹常數(shù)輪RRSSS機(jī)制中用到的策略。

4.1 常數(shù)輪RRSSS的策略

Maleka和Shareef[5]認(rèn)為在參與者知道最后一輪時，不存在有限RRSSS。他們假設(shè)每次分享秘密的參與者都來自于一個相同的集合，如果放松這個條件，允許有不同的參與者執(zhí)行秘密恢復(fù)協(xié)議，就可以實(shí)現(xiàn)有限RRSSS。參與者根據(jù)參加協(xié)議的次數(shù)，分為長期參與者和短期參與者。如果參與者每次都參與協(xié)議，那么就稱之為長期參與者，若參與者僅參加一次協(xié)議，則稱之為短期參與者。一個參與者是長期參與者還是短期參與者取決于他們參加協(xié)議的次數(shù)。

這里的長期參與者和短期參與者與文獻(xiàn)[3]的不同，在文獻(xiàn)[3]中，長參與者表示參與者擁有長的秘密份額，而短參與者擁有短的秘密份額。假設(shè)在每一輪中只有一個長期參與者，他會一直參與所有輪的RRSSS，而剩余的n-1個參與者是短期參與者，他們只參加一次RRSSS。為了分析方便，將整個參與秘密恢復(fù)協(xié)議的短期參與者看做一個集合，稱之為短期集合。

為了達(dá)到相互合作的均衡，短期集合必須在每一輪中先采取行動，否則短期參與者肯定會在每一輪采取不合作策略。這是因?yàn)槎唐趨⑴c者只參加一輪秘密恢復(fù)協(xié)議后就退出，因此不必?fù)?dān)心下一輪受到懲罰。如果短期參與者先行，那么為了獲得秘密，短期參與者肯定會采取合作的策略。另一方面，長期參與者不能采取純策略，如果他每次都采取合作策略，那么一旦短期參與者知道了他的策略，那么短期參與者就失去了合作的動機(jī)；如果他每次都采取不合作策略，那么一旦短期參與者知道了這一純策略，短期參與者也不會合作。這是因?yàn)?，即使短期參與者合作，沒有長期參與者的份額，他也無法恢復(fù)秘密。因此對于長期參與者來說，他最好采取混合策略。所以在異步通信信道中，每一輪短期參與者先行，長期參與者以概率β采取針鋒相對策略（Tit-For-Tat，TFT）。所謂針鋒相對策略就是參與者在博弈的第一輪采取合作策略，然后在接下來的每一輪，都將采取對手上一輪的策略。結(jié)果表明，在滿足一定條件下，長期參與者和短期參與者都可以獲得秘密，因?yàn)樗麄冊诿恳惠喍疾扇『献鞑呗浴?/p>

4.2 常數(shù)輪RRSSS機(jī)制

當(dāng)重復(fù)博弈是完全信息時，即使參與者有不同的類型，也不存在實(shí)際可行的RRSSS，使得參與者獲得秘密。這是因?yàn)槊恳粋€參與者都清楚地知道對手的類型以及他們將采取的策略。然而，在不完全信息下，因?yàn)閰⑴c者不知道對手的類型，為了能夠獲得秘密，參與者有互相合作的可能。

為了使參與者在每一輪都采取合作策略，分享他們的秘密份額，最終恢復(fù)秘密，本文考慮了不完全信息下的常數(shù)輪RRSSS。常數(shù)輪RRSSS機(jī)制包括兩個子協(xié)議，秘密分發(fā)協(xié)議和秘密恢復(fù)協(xié)議。

秘密分發(fā)協(xié)議（The dealer’s protocol）：

（1）秘密分發(fā)者隨機(jī)選擇一個m-1階的函數(shù)f(x)，使得f(0)=s(s≠0)。

（2）秘密分發(fā)者確定一個長期參與者（不失一般性，記為P1）和n-1短期參與者（記為P2，P3，…，Pn）。在不完全信息下，每個參與者知道自己的類型，但是不知道對手的類型。

（3）秘密分發(fā)者把秘密份額f(i)給每一個參與者Pi，其中i=1，2，…，n。

秘密恢復(fù)協(xié)議（The players’protocol）：

（1）每一個參與者在得到秘密份額f(i)后，隨機(jī)選擇一個T-m*-1階的函數(shù)gi(x)，其中g(shù)i(0)=f(i)，i=1，2，…，n。T是一個常數(shù)，它表示協(xié)議執(zhí)行的輪數(shù)，m*表示剩余的輪數(shù)，它的值由定理1給出。

（2）在每一輪，包括兩個參與者：長期參與者P1和一個短期參與者Pj，j=2，3，…，n。

①短期參與者Pj首先采取合作的策略，將f(j)的子秘密份額gj(1)發(fā)送給長期參與者P1。

②長期參與者P1采取混和策略（混合策略以概率β采取TFT策略，以概率1-β采取占優(yōu)策略。其中TFT策略指的是參與者在第一輪采取合作策略，在以后的每一輪都采取對方上一輪所采取的策略。占優(yōu)策略指的是，參與者在每一輪都采取不合作的策略）決定是否將f(1)子份額g1(j)發(fā)給短期參與者Pj。

（3）協(xié)議進(jìn)行到最后一輪，每個參與者根據(jù)自己的子份額，通過朗格朗日插值公式恢復(fù)出秘密份額，進(jìn)一步恢復(fù)秘密s。

4.3 機(jī)制有效性證明

如果滿足一定條件，新機(jī)制可以實(shí)現(xiàn)RRSSS，并且具有高效性。

引理1存在一個ˉ滿足（β表示長期參與者采取針鋒相對策略的概率），使得短期參與者在不完全信息下的常數(shù)輪RRSSS中，有采取合作策略的動機(jī)。

證明短期參與者在每一輪先行，他們不知道長期參與者是否會采取TFT策略。假設(shè)長期參與者以概率β采取TFT策略，以概率1-β采取占優(yōu)策略。

在第k輪，如果短期參與者采取不合作策略，那么長期參與者也采取不合作策略。這是因?yàn)槿绻L期參與者采取TFT策略，那么長期參與者應(yīng)該選擇不合作策略，如果長期參與者選擇占優(yōu)策略，那么長期參與者也應(yīng)該選擇不合作策略，此時短期參與者的收益為U-。

在第k輪，如果短期參與者采取合作策略，那么就有兩種情況：

（1）如果長期參與者以概率β采取TFT策略，那么長期參與者應(yīng)該采取合作策略，此時短期參與者的收益為U。

（2）如果長期參與者以概率1-β采取占優(yōu)策略，那么長期參與者應(yīng)該采取不合作策略，此時短期參與者的收益為U--。

在這種情況下，短期參與者的期望收益為βU+(1-β)U--。作為理性參與者，短期參與者必定采取收益大的策略。

為了促進(jìn)短期參與者采取合作策略，需要使短期參與者采取合作策略的效用大于采取不合作策略的效用。因此，需要滿足：

證明證明的主要思路是：對于n個理性參與者，共進(jìn)行T輪階段博弈，那么秘密分發(fā)者選擇門限m時，需要滿足m≤T-m*。如果在T-m*輪之前，所有的參與者都采取合作策略，那么每個參與者就可以獲得足夠的子秘密份額恢復(fù)秘密份額，進(jìn)而恢復(fù)秘密。

令m*表示剩余的輪數(shù)，根據(jù)引理1，已知短期參與者有采取合作策略的動機(jī)。不失一般性，假設(shè)在第T-m*輪前，短期參與者不分享份額，那么長期參與者也不分享份額（引理1），短期參與者在第T-m*輪采取合作的策略。在接下來的m*輪，短期參與者和長期參與者都采取不合作策略，他們的收益均為U-。本文不考慮這種情形，因?yàn)檫@對雙方都不利。

假設(shè)短期參與者合作（在不完全信息下，根據(jù)引理1，短期參與者肯定會合作），如果長期參與者也采取合作策略，那么他在這一輪得到收益U。在接下來的m*-1輪，新進(jìn)入?yún)f(xié)議的短期參與者如果觀察到上一輪的結(jié)果是雙方都合作，那么新加入的短期參與者認(rèn)為長期參與者在這一輪也有合作的傾向，因此短期參與者和長期參與者會一直合作下去。在這種情況下，長期參與者的總收益是(m*-1)U。在接下來的m*-1輪，一旦有一輪長期參與者采取不合作策略（而短期參與者仍然采取合作策略），那么長期參與者在第T-m*的收益為U+。但是在后續(xù)輪中，新加入的短期參與者因?yàn)楹ε碌貌坏矫孛芏徊扇『献鞑呗?。因此新加入的短期參與者在剩余的m*-1輪都會采取不合作策略。因?yàn)椴还荛L期參與者是什么類型，不合作策略總是短期參與者的占優(yōu)策略，因此一旦長期參與者采取不合作策略，在后續(xù)的m*-1輪，參與者會進(jìn)入相互不合作狀態(tài)。在這種情況下，長期參與者的總收益為：U++(m*-1)U-。為了使長期參與者具有合作的動機(jī)，必須使長期參與者合作時的收益大于不合作時的收益，需要滿足：

因此有：

表1對本文方案和其他理性秘密分享方案進(jìn)行了比較，可以看出，給定滿足條件的隨機(jī)數(shù)，本文方案在納什均衡、期望執(zhí)行時間和通信信道方面均占有優(yōu)勢。

表1 各種理性秘密分享方案的比較

5 結(jié)束語

為了在常數(shù)輪RRSSS中能夠引入相互合作的策略，為參與者設(shè)定了不同的類型，使得參與者在知道最后一輪的常數(shù)輪RRSSS中也能都采取合作策略，進(jìn)而成功恢復(fù)秘密。在不完全信息下，構(gòu)造了一個常數(shù)輪RRSSS，可以證明，如果滿足一定的條件，參與者可以實(shí)現(xiàn)相互的合作，從而達(dá)到恢復(fù)秘密的目的。

[1]Halpern J，Teague V.Rational secret sharing and multiparty computation：extended abstract[C]//Proceedings of the Thirty Sixth Annual ACM Symposium on Theory of Computing，Chicago，2004：623-632.

[2]Gordon S D，Katz J.Rational secret sharing，revisited[C]//De Prisco R，Yung M.The Fifth Conference on Security and Cryptography for Networks，Maiori，2006：229-241.

[3]Shareef A.Rational secret sharing without broadcast[EB/OL]. [2012-01-05].http：//eprint.iacr.org/2010/249.

[4]Zhang Zhifang，Liu Mulan.Unconditionally secure rational secret sharing in standard communication networks[C]//Information Security and Cryptology，2011，6829：355-369.

[5]Maleka S，Shareef A，Rangan C P.Rational secret sharing with repeated games[C]//ISPEC’08 Proceedings of the 4th International Conference on Information Security Practice and Experience，Heidelberg，2008：334-346.

[6]Zhang Zhifang，Liu Mulan.Rational secret sharing as extensive games[J].Science China Information Sciences，2013，56.

[7]Zhang En，Cai Yongquan.A new rational secret sharing scheme[J]. China Communications，2010，7（4）：18-22.

[8]Gidney.Rational secret sharing with and without synchronous broadcast，conspicuous secrets，malicious players and unbounded opponents[D].MCSc Thesis Defence，2012.

[9]Osborne M，Rubinstein A.A course in game theory[M].Cambridge：MIT Press，2004.

[10]Andreoni J，Miller J H.Rational cooperation in the finitely repeated prisoners’dilemma：experimental evidence[J].The Ecomonic Journal，1993，103（418）：570-585.

[11]Milgrom P，Roberts J.Predation，reputation，and entry deterrence[J].Journal of Economic Theory，1982，27（2）：280-312.

GAO Xianfeng1,WANG Yilei2

1.Department of Modern Education Technology,Ludong University,Yantai,Shandong 264025,China
2.School of Information and Electrical Engineering,Ludong University,Yantai,Shandong 264025,China

Finitely repeated rational secret sharing scheme is first proposed by Maleka and Shareef who conclude that there does not exist a Repeated Rational Secret Sharing Scheme（RRSSS）within constant rounds.However,RRSSS within infinite rounds is lack of efficiency and has no application value.To achieve an efficient RRSSS within constant rounds,players are set different types.An efficient RRSSS within constant rounds is put forward under incomplete information and then its validity is proved. Compared with other rational secret sharing schemes,given proper conditions,the new scheme has advantages in Nash equilibrium, expected running time and communication channel.

game theory;Nash equilibrium;finitely repeated games;rational secret sharing scheme

基于重復(fù)博弈的理性秘密分享機(jī)制，首先由Maleka和Shareef提出，他們認(rèn)為不存在常數(shù)輪的重復(fù)理性秘密分享機(jī)制（Repeated Rational Secret Sharing Scheme，RRSSS）。然而，無限輪RRSSS效率低下，不具備應(yīng)用價值。為了實(shí)現(xiàn)高效的常數(shù)輪RRSSS，為參與者設(shè)置了不同的類型，提出了不完全信息下的常數(shù)輪RRSSS機(jī)制，并證明了機(jī)制的有效性。與其他理性秘密分享方案比較，在給定條件下，新方案在（納什）均衡、期望執(zhí)行時間和通信信道方面均具有優(yōu)勢。

博弈論；納什均衡；重復(fù)博弈；理性秘密分享機(jī)制

A

TP309.7

10.3778/j.issn.1002-8331.1203-0439

GAO Xianfeng,WANG Yilei.Rational secret sharing scheme with constant rounds.Computer Engineering and Applications,2013,49（18）：65-68.

國家自然科學(xué)基金（No.60875039）；山東省自然科學(xué)基金（No.ZR2011FM017）。

高先鋒（1968—），男，副教授，高級工程師，研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)安全和秘密分享機(jī)制；王伊蕾（1979—），女，博士研究生，講師，研究領(lǐng)域?yàn)槎喾桨踩?jì)算和博弈論。E-mail：xianfenggao_ldu@163.com

2012-03-19

2012-06-08

1002-8331（2013）18-0065-04

CNKI出版日期：2012-07-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120716.1500.021.html