常數輪理性秘密分享機制

高先鋒，王伊蕾

1.魯東大學 現代教育技術部，山東 煙臺 264025

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

常數輪理性秘密分享機制

高先鋒1，王伊蕾2

1.魯東大學 現代教育技術部，山東 煙臺 264025

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

1 引言

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

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

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

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

2 相關工作

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

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

3 基本概念

對于理性參與者，首先要定義他們的效用函數，因為理性參與者所采取的行為完全依賴于能否最大化他們的收益。

3.1 效用和納什均衡

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

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

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

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

為簡便起見，本文定義了輸出結果為ο時，參與者Pi的效用函數（其中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沒有得到秘密。

為了保證參與者有參與理性秘密分享機制的動機，規定：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和任何策略，都有：

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

3.2 重復博弈

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

4 常數輪RRSSS

在常數輪RRSSS中，參與者知道哪一輪是最后一輪，因此在最后一輪，所有參與者都會采取不合作策略，因為下一輪博弈將結束，即使采取不合作的策略也不會擔心將來受到懲罰。根據逆向歸納法，可以推導出在所有輪，參與者都沒有合作的動機。然而文獻[10]和文獻[11]的結論表明，如果放松某些條件，在有限重復博弈中，合作是可以出現的。本文將他們的結論引入到有限重復理性秘密分享機制中，構造了常數輪的RRSSS機制。首先介紹常數輪RRSSS機制中用到的策略。

4.1 常數輪RRSSS的策略

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

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

為了達到相互合作的均衡，短期集合必須在每一輪中先采取行動，否則短期參與者肯定會在每一輪采取不合作策略。這是因為短期參與者只參加一輪秘密恢復協議后就退出，因此不必擔心下一輪受到懲罰。如果短期參與者先行，那么為了獲得秘密，短期參與者肯定會采取合作的策略。另一方面，長期參與者不能采取純策略，如果他每次都采取合作策略，那么一旦短期參與者知道了他的策略，那么短期參與者就失去了合作的動機；如果他每次都采取不合作策略，那么一旦短期參與者知道了這一純策略，短期參與者也不會合作。這是因為，即使短期參與者合作，沒有長期參與者的份額，他也無法恢復秘密。因此對于長期參與者來說，他最好采取混合策略。所以在異步通信信道中，每一輪短期參與者先行，長期參與者以概率β采取針鋒相對策略（Tit-For-Tat，TFT）。所謂針鋒相對策略就是參與者在博弈的第一輪采取合作策略，然后在接下來的每一輪，都將采取對手上一輪的策略。結果表明，在滿足一定條件下，長期參與者和短期參與者都可以獲得秘密，因為他們在每一輪都采取合作策略。

4.2 常數輪RRSSS機制

當重復博弈是完全信息時，即使參與者有不同的類型，也不存在實際可行的RRSSS，使得參與者獲得秘密。這是因為每一個參與者都清楚地知道對手的類型以及他們將采取的策略。然而，在不完全信息下，因為參與者不知道對手的類型，為了能夠獲得秘密，參與者有互相合作的可能。

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

秘密分發協議（The dealer’s protocol）：

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

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

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

秘密恢復協議（The players’protocol）：

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

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

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

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

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

4.3 機制有效性證明

如果滿足一定條件，新機制可以實現RRSSS，并且具有高效性。

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

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

在第k輪，如果短期參與者采取不合作策略，那么長期參與者也采取不合作策略。這是因為如果長期參與者采取TFT策略，那么長期參與者應該選擇不合作策略，如果長期參與者選擇占優策略，那么長期參與者也應該選擇不合作策略，此時短期參與者的收益為U-。

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

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

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

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

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

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

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

假設短期參與者合作（在不完全信息下，根據引理1，短期參與者肯定會合作），如果長期參與者也采取合作策略，那么他在這一輪得到收益U。在接下來的m*-1輪，新進入協議的短期參與者如果觀察到上一輪的結果是雙方都合作，那么新加入的短期參與者認為長期參與者在這一輪也有合作的傾向，因此短期參與者和長期參與者會一直合作下去。在這種情況下，長期參與者的總收益是(m*-1)U。在接下來的m*-1輪，一旦有一輪長期參與者采取不合作策略（而短期參與者仍然采取合作策略），那么長期參與者在第T-m*的收益為U+。但是在后續輪中，新加入的短期參與者因為害怕得不到秘密而不采取合作策略。因此新加入的短期參與者在剩余的m*-1輪都會采取不合作策略。因為不管長期參與者是什么類型，不合作策略總是短期參與者的占優策略，因此一旦長期參與者采取不合作策略，在后續的m*-1輪，參與者會進入相互不合作狀態。在這種情況下，長期參與者的總收益為：U++(m*-1)U-。為了使長期參與者具有合作的動機，必須使長期參與者合作時的收益大于不合作時的收益，需要滿足：

因此有：

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

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

5 結束語

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

[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

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

博弈論；納什均衡；重復博弈；理性秘密分享機制

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.

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

高先鋒（1968—），男，副教授，高級工程師，研究領域為網絡安全和秘密分享機制；王伊蕾（1979—），女，博士研究生，講師，研究領域為多方安全計算和博弈論。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