基于博弈論的公平安全兩方計算協議

（山西師范大學數學與計算機科學學院，山西臨汾041004）

（山西師范大學數學與計算機科學學院，山西臨汾041004）

針對傳統安全兩方計算無法實現完全公平性的問題，結合博弈論方法，將參與者看作是理性的，提出了理性安全兩方計算協議.首先，在擴展式博弈框架下，給出安全兩方計算的博弈模型；其次，根據博弈模型描述，給出理性安全兩方計算理想函數FRPCP以及理性安全兩方計算協議πRPCP；最后對協議的安全性、公平性及納什均衡進行了分析.分析結果表明，在混合模型下，協議πRPCP能安全地實現理想函數FRPCP，并且在BDH困難假設下，協議πRPCP中各理性參與者的最佳策略是選擇合作，當博弈達到納什均衡時，參與者雙方能公平地獲得計算結果.

安全兩方計算；擴展博弈；納什均衡；公平性

安全兩方計算是指兩個相互獨立的參與者，在不泄露自己輸入的情況下通過一個密碼協議計算給定的函數，最終每個參與者都可以得到函數的計算結果.安全兩方計算是分布式密碼學的關鍵技術，也是安全多方計算的基礎，此概念由姚期智教授為了解決百萬富翁問題而提出［1］，即兩個百萬富翁想知道他們誰更富有，但又不希望對方知道自己財富的多少，并針對該問題設計了第一個安全兩方計算協議，后來Goldreich、Micali和Wigderson將安全兩方計算的理論系統化，推廣為多方參與的安全多方計算［2］問題，尤其是他們提出的理想/現實范式對后來的密碼學研究具有重要的指導意義，正是這些開創性的研究工作吸引了許多專家學者積極投身于安全多方計算研究，并取得了一系列研究成果［3-10］.

理想/現實模擬范式是衡量安全多方計算協議安全性的標準.假設在理想世界中存在一個可信第三方，參與者將各自的輸入發送給可信第三方，由可信第三方完成計算任務并將最終結果發送給各參與者，理想情況下的參與者是通過安全信道來傳遞自己的私有輸入，并由安全第三方代替參與者完成計算過程，因此可以保證安全性.但是在現實情況下，找到可信第三方是非常困難的，參與者只能通過運行協議來完成計算.如果一個攻擊者在攻擊真實協議執行時所得到的信息并不能比其在理想模型下攻擊所得到的信息多，就稱此協議是安全的.顯然，如果一個安全多方計算協議是安全的，那么攻擊者就不可能得到任何有用信息.

目前已有的兩方計算研究主要關注協議的安全性，忽略其公平性，而公平性在無可信第三方的情況下顯得更為重要，公平性就是指參與雙方要么都獲得計算結果，要么都不能獲得計算結果.Cleve曾指出兩方計算中的完全公平性只有在誠實參與者占大多數的情況下才能實現［11］，該結論使安全多方計算公平性的研究一度陷入了困境.Goldreich等［4］提出了一個在任意模型下多方通用的、可以計算任意函數的安全多方計算協議，但該方法只有存在特殊單向函數的情況下才能實現，非常不實用.Gordon等［12］對某些特殊函數的安全多方計算協議的公平性進行了研究并得出結論，認為即使不存在誠實參與者占大多數的情形也可以實現完全公平性，為公平性的研究擴寬了領域.

安全多方計算可以看作是研究相互不信任的多個參與者之間的交互問題的，這個特點與博弈論的局中人非常相似，2004年由Halpern和Teague［13］首次提出了理性安全多方計算的概念，認為參與者都是理性的，所采取的策略和行動都是為了最大化自身利益.事實上，在現實生活中參與者之間的交互都會受到某些利益的驅動，他們通常會為了提高自己的收益而作出理性的選擇，因此相比傳統密碼學中把參與者進行誠實和惡意的劃分，將參與者看作是理性的假設更加接近現實生活，該研究引起了國內外研究者的關注.在文獻［13］的協議中采用了重復剔除弱劣策略下的納什均衡，但對于參與者大于兩個的情況不適用，協議執行過程中要求分發者一直在線，并且不能防止成員合謀；Kol和Naor［14］發現重復剔除方法并不能排除所有不好的策略，提出了嚴格納什均衡及計算性C-resilient均衡，但該方案不能防止參與者在安全多方計算階段欺騙；Abraham等［15］為理性參與者定義了一個抗合謀均衡且給出了一個可以抵抗最多k人合謀的協議；Lysyanskaya等［16］定義了該模型下的納什均衡，利用理想/現實范式分析了具有理性和惡意參與者的混合模型下的安全多方計算問題，滿足惡意敵手控制［n/2］-2局中人時，協議仍然能達到納什均衡；Asharov等［17］討論了理性條件下的多方安全計算的一些基本性質，認為公平性在特定函數和收益設置下不可能達到；Groce等［18］在此基礎上進行了深入研究，認為只要參與者有嚴格動機計算理想環境中的函數，就可以實現理性公平計算；張恩和蔡永泉［19］針對傳統兩方安全計算協議中存在的不公平性，構建了兩方計算協議的博弈模型，最終能公平地得到計算結果；王伊蕾等［20］討論了理性兩方安全計算的序貫結構，構造了更加復雜但是更實際的理性計算協議，利用序貫均衡的概念保證協議的公平性.

從所引文獻可見，理性安全兩方計算協議的公平性是當前密碼學研究的一個熱點.但已有的理性安全多方計算協議存在以下問題：（1）只討論了協議的安全性和隱私性，不能保證完全公平性；（2）在協議中使用了信封和投票箱等較強的物理通道，這種假設在現實中不適用；（3）由于理性參與者的自利行為，導致協議中出現參與者不合作的行為，類似于博弈論中囚徒困境現象，無法實現協議的公平性.本文從擴展博弈的角度出發研究兩方計算的公平性問題，首先給出安全兩方計算的博弈模型，為每個參與者設計不同策略，當理性參與者偏離所設計策略時，其獲得收益不會比其遵守策略時大，當博弈達到均衡狀態時，參與者要么都能獲得正確的計算結果，要么都不能獲得，因此模型滿足兩方計算的公平性定義；其次利用雙線性對技術設計了理性兩方計算協議，通過對參與者收益函數的設置，使得遵守協議是參與者的最優策略；最后利用理想/現實范式對協議的安全性進行了證明.

1 基礎知識

1.1 雙線性對

定義1（雙線性對） 設（G1，+）和（G2，·）為兩個階數均為素數p的循環群，其中前者為加法群，后者為乘法群.令P為G1的生成元，如果滿足下面的性質，稱變換e∶G1×G1→G2為雙線性對.

（1）雙線性：對任意P1、P2和Q∈G1有

e（P1+P2，Q）=e（P1，Q）e（P2，Q）及e（Q2，P1+P）=e（Q，P1）e（Q，P2）成立；

（2）非退化性：存在P∈G1即e（P，P）≠1，也就是說e（P，P）是G2的生成元；

（3）可計算性：對任意P1，P2∈G1，存在有效的算法計算e（P1，P2）.

定義2（可忽略函數） 函數μ（·）＜1/p（k）是可忽略函數，如果對任意正多項式p（·）和足夠大的正數k都有μ（k）＜1/p（k）成立.

定義3（雙線性Diffie-Hellman問題） BDH問題描述如下：在（G1，G2，e）中，給定（P，aP，bP， cP），對任意的a，b，c∈，計算e（P，P）abc∈G2.

根據定義3中可忽略函數的定義，BDH假設可描述為：在求解BDH問題上，沒有概率多項式時間算法有不可忽略的優勢.

定義4 兩個總體 Xdef=｛Xn｝n∈N和 Ydef=｛Yn｝n∈N，如果對于每一個概率多項式時間算法D、每一個正多項式p（·）及所有充分大的n，都有

則稱這兩個總體是在多項式時間內不可區分的.

定義5（安全兩方計算） 兩個參與者P1和P2分別擁有秘密輸入xi（i=1，2），共同執行協議Π來計算函數f（x1，x2）=（y1，y2）（y1可以和y2相等），計算結束后，P1得到y1，P2得到y2.在這個過程中，每個成員僅僅知道自己的輸入數據和最后的結果.

定義6（安全兩方計算安全性） 設f為一個實現安全計算的理想函數，Π為現實模型的協議. Π能夠模擬理想函數f，當且僅當對于任意現實模型中的攻擊者A，存在一個理想模型下的攻擊者S，使得在任意的環境下，與真實環境下的攻擊者A和協議Π交互還是與理想環境下的攻擊者S和理想函數f交互是不可區分的，也就是說使得概率總體RΠ，A（ˉx，y）與If，S（x，y）是計算不可分辨的，則稱協議Π安全實現了理想函數f.

定義7（安全兩方計算公平性） 如果安全兩方計算協議中的參與者要么得到了計算結果，要么都沒有得到計算結果，則稱該協議滿足公平性.

1.2 博弈論相關概念

博弈論主要研究利益存在沖突的決策主體在相互對抗中，對抗雙方（或多方）相互依存的一系列策略和行動的過程集合.在分析其他參與方可能出現的行為策略基礎上，理性參與者會選擇對自己最有利的策略，均衡就是在參與方選擇各自最優策略時所達到的一種穩定狀態，這時任何參與方都不會單獨改變策略，因為改變策略意味著自身利益的損失，因此沒有人會愿意打破這一狀態.

設P=｛P1，P2，…，Pn｝表示由n個參與者組成的集合，用ai表示參與者Pi的策略，A=（a1，a2，…，an）表示所有參與者的策略組合，a-i表示除Pi以外其他人的策略.o表示博弈的結果，ui（o）表示關于結果o的效益函數，令Oout（o）=（s1，s2，…，sn），如果參與者Pi最終得到了輸出結果，則令si= 1，否則令si=0，令Oi=si.假設理性兩方計算中的參與者總是希望得到輸出結果，并且希望得到輸出結果的參與者越少越好，則效用假設的形式化描述如下：

（1）U1：如果Oi（o）=Oi（o′），那么ui（o）= ui（o′）；

（2）U2：如果Oi（o）=1，Oi（o′）=0，那么ui（o）＞ui（o′）；

（3）U3：如果Oi（o）=Oi（o′），對于所有j≠i，有Oj（o）≤Oj（o′），并存在某個j滿足Oj（o）＜Oj（o′），那么ui（o）＞ui（o′）.

動態博弈中參與者行為不是同時進行，而是先后選擇.擴展博弈能夠描述參與者決策的動態結構，每一個參與者輪流采取行動，而且其行動依賴于他們之前博弈的歷史，參與者需要隨著協議的進行選擇新的行為，而如何選擇則是由策略決定.

定義8（擴展式博弈） 一個擴展式博弈Γ是一個五元組（P，Q，p，（Ii）i∈P，（≤i）i∈P），其中P代表參與者集合，Q是行動序列集合，且滿足如下性質：

（1）空序列φ屬于Q；

（2）如果ak∈Q，k=1，2，…，w和0＜v＜w，那么ak∈Q，k=1，2，…，v；

（3）如果無限行動序列ak∈Q，k=1，2，…，∞滿足ak∈Q，k=1，2，…，v對任意正整數v，則ak∈Q，k=1，2，…，∞.

①p是參與者函數，它賦給每個非終端序列（Q＼Z的元素）一個P的元素；

②Ii是參與者i∈P的信息集，它表示參與者進行選擇時所知道的信息；

③≤i是參與者的偏好關系：對每個i∈P有一個Z上的偏序關系.

擴展博弈的解釋如下：每個Q中的行動序列代表博弈的可能歷史.空序列φ代表博弈的開始節點，每個參與者輪流采取行動，而且其行動依賴于他們之前博弈的歷史，每個參與者擁有一個節點，參與者從該節點出發所采取的行動會引出指向另外節點的一條邊，終端集合Z代表博弈所有可能的結果（outcomes）.如果將一個擴展式博弈看成是一棵博弈樹，樹的邊和節點分別對應博弈的行動和行動序列.

定義9（納什均衡） 在博弈Γ=（Ai，ui），i= 1，2，…，n中，稱行為策略a∈A達到納什均衡.如果對于任意參與方Pi∈P有

兩方擴展式博弈可記為（｛P1，P2｝，｛A1，A2｝，｛u1，u2｝），其納什均衡表述為

ui（ai，a-i）≥ui，a-i），

納什均衡是指參與者在選擇各自最優行為時的狀態，是一個穩定的狀態，在其他參與者不改變策略的情況下沒有人愿意偏離這個狀態.相關博弈論的詳細知識請參閱文獻［21-22］.

2 理性兩方計算博弈模型

理性安全兩方計算是指參與者為理性的安全兩方計算協議，與傳統安全兩方計算最大的區別在于參與者根據他們的效用來決定是否遵守協議.

兩方計算博弈中的參與人就是安全兩方計算的參與者，策略是協議中允許的行為，博弈的過程按照協議執行流程來進行，由于在每一輪協議執行之前，各參與者均不知道對方可能采取的策略，只有當收到對方發送的結果并進行驗證后才能確定其行動，可見該博弈是不完全信息動態博弈，效用函數按照博弈結束時，每個參與人是否得到正確的計算結果來考慮.本節基于擴展式博弈建立兩方公平計算博弈模型，稱為安全兩方計算博弈Γ.

2.1 參與人

用P=｛P1，P2｝表示安全兩方計算博弈Γ的兩個理性參與者，用T表示可信第三方.

2.2 信息集

最后終結于博弈的葉子節點.

2.3 策略集

參與者Pi在行動序列q后會依據其信息集和其效用函數選擇下一步可行策略，其可行策略集合分為以下3類：

（1）按照協議的方式發送正確的信息，記為C；

（2）按照協議的方式發送錯誤的信息，記為D；

（3）不做選擇或退出協議，記為Q.

在理性安全計算博弈中，每位參與者Pi可以在任何時候選擇退出博弈，即選擇策略Q；若沒有選擇策略Q，則參與者Pi可以在當前狀態下給任何其他參與者發送信息，包括發送正確或者錯誤的信息，也即選擇策略C或者D.

2.4 效用函數

對于理性參與者Pi（i=1，2），在以上效用假設下定義4種情況的效用值：

（1）ui（o）=a，只有Pi得到計算結果，另外的參與者沒有得到；

（2）ui（o）=b，兩個參與者都得到計算結果；

（3）ui（o）=c，兩個參與者都沒有得到計算結果；

（4）ui（o）=d，Pi沒有得到計算結果，另外的參與者得到了.

如果參與者Pi在協議執行過程中選擇退出策略Q，那么對于另外一個參與者來說，其最優選擇也是選擇策略Q，此時兩個參與者的效用都為c；否則，如果其不選擇Q，他的效用可能是d，而d＜c.

根據安全多方計算協議公平性的要求，在協議結束后，參與者要么都得到協議的正確計算結果，要么都得不到協議的正確計算結果.該公平性在該博弈模型下可表現為參與者雙方均得到相同的收益.

3 公平的理性兩方計算理想模型

本節闡述在理想情況下，公平的安全兩方計算協議博弈模型，記該協議為FRPCP，稱其為理想函數.具體分為以下5步：

給定需計算的二元函數f（x1，x2）∈，其中x1，x2∈；參與者集合 P=（P1，P2）.FRPCP處理如下：

（1）當 FRPCP從參與者 Pi∈P收到其輸入（Pinput，Psid，w），如果存在 P′sid，使得 Psid=（P，），則

①將w賦值給xi，即xi=w；

③發送（Pinput，receipt，Psid）給Pi.

（2）當 FRPCP從參與者 Pi∈P收到（Pcompute， Psid，Pi），如果存在，使得Psid=（P，P′sid），則

當收到（P1，P2）的輸入值，同時給每位參與者都發送回復消息（Pinput，receipt，Psid）后，FRPCP計算隨機函數

f（x1，x2）=（f1（x1，x2），f2（x1，x2）），…，（f1，f2）.

（3）當FRPCP從參與者Pi∈P收到公平輸出消息（Pfair.output，Psid，Pi），如果存在 P′sid，使得 Psid=（P，P′sid），則

①若當前存在被標識為“賄賂”的參與者，則給其發送中斷符⊥，給其余參與者發送相應的fi；

②否則，給每位參與者Pi發送fi.

（4）當從敵手S收到（Pcorrupt.input，Psid，Pi），如果存在P′sid，使得Psid=（P，P′sid），則

①登記Pi是“被賄賂的”；

（5）當從敵手S收到（Pcorrupt.input，Psid，Pi），如果存在，使得Psid=（P，），則

①登記Pi是“被賄賂的”；

②轉發fi給敵手S；

③如果當前敵手S提供另一個值w′，并且計算函數的輸出階段其輸出值fi還沒有寫在Pi的輸出帶上，則置xi=w′.

在該理想函數中，參與者輸入的保密性由其理想函數FRPCP的第（1）步保證；計算輸出的正確性由第（2）步保證；根據上節在博弈模型下公平性的說明，即參與者有相同的收益，該性質由第（3）步保證；其安全性由第（4）和（5）步保證.

4 公平的理性兩方計算協議

本節利用雙線性對技術，設計理性公平計算協議，記該協議為πRPCP.

根據定義5中安全兩方計算協議的定義，兩個參與者分別擁有秘密輸入xi（i=1，2），共同計算函數f（x1，x2）=（y1，y2）（y1可以和 y2相等）.設（G1，+）和（G2，·）分別為p階加法循環群和乘法循環群，p為素數.令P、Q和R為G1的生成元，并且其間的離散對數問題無人知道.e∶G1×G1→G2為雙線性對.該協議包括3個階段：數據準備階段、數據交互計算階段和結果輸出階段.

4.1 數據準備階段

令x1和x2作為P1和P2的私有輸入（如果任意一方的輸入是無效的，則該協議給雙方發送中斷符⊥）.

P1執行如下：

步驟1 根據幾何分布隨機從｛1，2，…，p｝選取t1（其中p是群G1的階）；

說明 選取多項式次數服從幾何分布是為了讓參與者雙方的多項式盡量分布在群階數p的中間位置，避免出現多項式的次數過高和過低的情況；

步驟2 生成兩個次數為t1-1的多項式f（x）和g（x）：

式中：x1=a0+b0；

步驟3 計算承諾對

C10=e（a0P+b0Q，R），C11=e（a1P+b1Q，R），…，C1t-1=e（at-1P+bt-1Q，R），并公布C1i，其中0≤i≤t1；

步驟4 計算ri=f（i）和si=g（i），令x10=（0，r0），x11=（s0，r1），x12=（s1，r2），…，x1i=（si，ri+1），…，x1n=（si-1，ri），x1n+1=（sn，0），并保密x1i，其中i=1，2，…，n＞t1.

P2執行如下：

步驟1 根據幾何分布隨機從｛1，2，…，p｝選取t2（其中p是群G1的階）；

步驟2 生成兩個次數為t2-1的多項式f（x）和g（x）：

式中：x2=a0+b0.

步驟3 計算承諾對

C20=e（a0P+b0Q，R），C21=e（a1P+b1Q，R），…，C2t-1=e（at-1P+bt-1Q，R），并公布C2i，其中0≤i≤t2；

步驟4 計算ri=f（i）和si=g（i），令x20=（0，r0），x21=（s0，r1），x22=（s1，r2），…，x2i=（si，ri+1），…，x2n+1=（sn，0），并保密 x2i，其中 i=1，2，…，n＞t2.

4.2 數據交互計算階段

步驟1 參與者P1給參與者P2發送x10，P2給參與者P1發送x20.

步驟2 參與者P1給參與者P2發送x11，P2給參與者P1發送x21.同時，P1通過式（4）驗證在上一輪收到數據的正確性，若式（4）成立，則繼續；否則，則終止協議.

P2通過式（5）驗證在上一輪收到數據的正確性，若式（5）成立，則繼續；否則，則終止協議.

在第i輪，i∈｛1，2，…，n｝，參與者P1給參與者P2發送x1i，P2給參與者P1發送x2i.同時，P1通過式（6）驗證在上一輪收到數據的正確性，若式（6）成立，則繼續；否則，則終止協議.

P2通過式（7）驗證在上一輪收到數據的正確性，若式（7）成立，則繼續；否則，則終止協議.

此階段結果輸出說明：協議總共n+1輪，在每一輪參與者按照以下規則決定自己的輸出：

（1）在協議第i輪，如果P1在P2收到x1i之前終止協議，則P2將隨機決定他的輸出；如果P2在P1收到x2i之前終止協議，則P1也將隨機決定他的輸出，并根據輸出結果是否正確獲得一定收益值；

（2）如果P1遵守協議規則正常運行結束，且每一輪均通過驗證，則P2將輸出正確的x2i；如果P2遵守協議規則正常運行結束，且每一輪均通過驗證，則P1將輸出，并根據輸出結果是否正確獲得一定收益值x1i.

4.3 結果輸出階段

此階段分如下兩步：

步驟1 如果第一階段（數據準備階段）和第二階段（數據交互計算階段）均順利完成，則參與者根據第二階段收到的信息，利用拉格朗日插值多項式重構收到的信息，最后計算出f（x1，x2）的值；

步驟2 如果第一階段（數據準備階段）和第二階段（數據交互計算階段）均未完成，則參與者隨機輸出f（x1，x2）的值.

5 方案分析

本節對所構造的協議進行安全性、公平性及納什均衡分析.

定理1 在BDH困難假設下，所構造的理性安全公平計算協議πRPCP是安全的和公平的，即協議πRPCP能安全實現其理想函數FRPCP.

證明 設A是現實中的敵手與實際協議πRPCP中的參與者交互，并運行理性安全公平協議πRPCP，同時構造理想博弈模型下的敵手S，使得任何區分器Z均不能以不可忽略的概率區分：在混合模型下（記為REAL）A與敵手和理性安全公平計算協議πRPCP交互，還是在理想博弈模型（記為IDEAL）下與理想敵手S與理想博弈模型FRPCP交互.

構造理想敵手S：敵手S運行A的一個仿真副本，來自區分器Z的任何輸入都轉給敵手A，同時A的任何輸出都將拷貝給S作為其輸出.

5.1 仿真可信第三方（TTP）

當一個可信的TTP被激活，S從FRPCP得到相關激活信息，并為敵手S仿真協議πRPCP.

5.2 仿真發送者

當未被攻陷的參與者通過輸入激活消息被激活，仿真敵手通過FRPCP得到該消息，同時為A仿真協議πRPCP.

（1）當S從FRPCP得到參與者P′1激活消息，S發送該消息給A，然后轉發A的回復給FRPCP.

（2）當S從FRPCP得到參與者P′2激活消息，S發送該消息給A，然后轉發A的回復給FRPCP.

5.3 仿真接收者

當未被攻陷的參與者通過輸入激活信息被激活，S從FRPCP得到該信息，同時為A仿真協議πRPCP.

5.4 仿真攻陷

當現實敵手A攻陷某一參與者，則S也攻陷該位參與者，同時將該參與者的內部狀態提供給FRPCP.在此要求任何參與者均不存在任何形式的秘密內部狀態.

IDEAL和REAl的不可區分性：基于所構造的理想敵手S，定義3類事件，同時證明下述3類事件中，無論哪一類事件發生，在BDHP假設下，其IDEAL和REAL均是不可區分的.

事件1 當某參與者Pi被攻陷，很容易觀察到，在 REAL環境下，根據理想博弈模型、協議πRPCP的程序規則，可知S能完美仿真協議操作.因此，在此情況下，REAL和IDEAL是不可區分的.

事件2 當某參與者Pi被攻陷，在協議πRPCP執行過程中，Pi試圖從公開信息中推斷出對方的秘密輸入信息，根據多項式的構造以及BDH假設可知，此時S能完美完成仿真協議操作.故此情況下，REAL和IDEAL是不可區分的.

事件3 當某參與者Pi被攻陷，在協議πRPCP執行過程中，試圖以提前終止協議獲得收益，根據理想模型FRPCP和協議πRPCP程序規則可知，在此情況下S能完美仿真協議操作.所以在此情況下REAL和IDEAL是不可區分的.

定理2 在BDH困難假設下，協議實例πRPCP執行中各理性參與者的最佳策略是C，即選擇互相合作，此時各參與者的效用均為b.

證明 根據第3節（3）理想函數FRPCP的輸出結果，即當FRPCP從參與者Pi∈P收到公平輸出消息（Pfair.output，Psid，Pi），如果存在 P′sid，使得 Psid=（P，P′sid），則：

（1）若當前存在被標識為“賄賂”的參與者，則給其發送⊥，而給其余參與者發送相應的fi；

（2）否則，給每位參與者Pi發送fi.

又因為a＞b＞c＞d，每位參與者的最佳選擇是選擇策略C，否則他們將得到更差的收益.因此，在理想函數FRPCP中，其最優策略是C，當博弈達到納什均衡時，各理性參與者得到的效用均為b.

另一方面，在協議的數據準備階段和數據輸出階段，均是理性參與者獨立完成計算任務，不存在破壞協議公平性的問題.在數據交互階段，當協議執行到第i輪時，算法僅能驗證上一輪i-1所收到數據的正確性.如果參與者在第i-1輪選擇策略Q或者D，此時其收益最多為c，因協議雙方必須多執行一輪，才能彼此驗證對方收到信息的正確性.故在數據交互的整個過程中，參與者無論在哪一輪出現背叛，均不可能增加受益，因此協議雙方的最佳策略是相互合作.

根據定理1的結果可知，協議πRPCP在BDH假設下能安全實現理性函數FRPCP，又因為在理想函數FRPCP下其理性參與者選擇合作，其效用為b.因此，根據定理1中仿真證明過程可知，協議πRPCP滿足公平性要求.根據定理證明過程中事件的證明，以及第4節協議πRPCP的博弈論模型可知，協議執行最終的納什均衡為各參與者互相合作，在協議行動序列的每一步均將選擇策略C，此時各方的收益均為，即所有參與者都能得到計算結果.

在協議性能方面，由于該理性公平計算協議是基于擴展式博弈建立的，因此可達到較強的納什均衡，滿足序貫均衡性質.在協議通信復雜度方面，其通信復雜度為n，是隨機選取的大于門限t的數，故其通信輪數為常數，與文獻［10］的通信輪數相當，但優于文獻［13，19］的通信輪數O（k）（k為安全參數）.

6 結束語

安全兩方計算協議中的公平性問題是密碼學中的一個難題，本文結合博弈論方法對其進行了研究.首先基于擴展博弈提出了理性安全公平兩方計算協議的博弈模型；其次根據博弈模型，對理性安全兩方協議的安全性和公平性進行了分析，給出了其博弈模型下理想函數FRPCP，在此基礎上基于雙線性對技術，構造了公平的理性安全兩方計算協議πRPCP；最后在混合模型下證明了理性安全兩方計算協議πRPCP能安全實現其理想函數FRPCP，并且分析了當兩方博弈達到納什均衡狀態時，參與者雙方能公平地獲得計算結果.

［1］ YAO A C.Protocols for secure computation［C］∥Proc. of the23rd IEEE Symposium on Foundationsof Computer Science（FOCS）.LosAlamitos：IEEE Computer Society Press，1982：160-164.

［2］ GOLDREICH O，MICALI S，WIGDERSON A.How to play any mental game［C］∥Proc.of the 19th Annual ACM Symposium on Theory of Computing（STOC）. New York：ACM Press，1987：218-229.

［3］ GOLDWASSER S.Multi-party computation：past and present［C］∥ Proc. of the 16th Annual ACM Symposium on Principles of Distributed Computing.New York：ACM Press，1997：21-24

［4］ GOLDREICH O.Foundations of cryptography：volume 2，basic applications［M］. Cambridge：Cambridge University Press，2004：79-92.

［5］ BLAKE IF，KOLESNIKOV V.Strongcondition oblivious transfer and computing on intervals［G］∥Proc.of Advances in Cryptology.Berlin：Springer，2004：515-529.

［6］ 李順東，戴一奇，游啟友.姚氏百萬富翁問題的高效解決方案［J］.電子學報，2005，33（5）：769-773.

LI Shundong，DAI Yiqi，YOU Qiyou.An efficient solution to Yao' millionaires' problem［J］. Acta Electronica Sinica，2005，33（5）：769-773.

［7］ LIN H Y，TZENG W G.An efficient solution to the millionaires problem based on homomorphic encryption［C］∥In ASIA crypto logy 2005.Berlin：Springer，2005：456-466.

［8］ LINDELL Y，PINKAS B.A proof of Yao's protocol for secure two-party computation［J］. Journal of Cryptology，2009，22（5）：161-188.

［9］ 唐春明，石桂花，姚正安.排序問題的安全多方計算協議［J］.中國科學：信息科學，2011，41（7）：789-797.

TANG Chunming，SHI Guihua，YAO Zheng'an.Secure multi-party computation protocol for sequencing problem［J］. Scientia Sinica Informationis，2011，41（7）：789-797.

［10］ 田有亮，彭長根，馬建峰，等.通用可組合公平安全多方計算協議［J］.通信學報，2014，35（2）：54-62.

TIAN Youliang，PENG Changgen，MA Jianfeng，et al. Universally composable secure multiparty computation protocol with fairness［J］.Journal on Communications，2014，35（2）：54-62.

［11］ CLEVE R.Limits on the security of coin flips when half the processors are faulty［C］∥ In 18th Annual ACM Symposium on Theory of Computing.Berkeley：［s.n.］，1986：364-369.

［12］ GORDON D，HAZAY C，KATZ J，et al.Complete fairness in secure two-party computation［C］∥Proc of the 40th Annual ACM Symposium on Theory of Computing（STOC）.New York：ACM Press，2008：413-422.

［13］ HALPERN J，TEAGUE V.Rational secret sharing and multiparty computation［C］∥Proc of the 36th Annual ACM Symposium on Theory of Computing（STOC）. New York：ACM Press，2004：623-632.

［14］ KOL G， NAOR M. Games for exchanging information［C］∥Proc.of the 40th Annual ACM Symposium on Theory of Computing（STOC）.New York：ACM，2008：423-432.

［15］ ABRAHAM I，DOLEVD，GONENR，etal. Distributed computing meets game theory：Robust mechanisms for rational secret sharing and multiparty computation［C］∥Proc.of the 25th ACM symposium on Principles of distributed computing（PODC'06）. New York：ACM，2006：53-62.

［16］ LYSYANSKAYA A， TRIANDOPOULOS N. Rationality and adversarialbehaviorin multiparty computation［G］∥Proc.the 26th Annual Cryptology. Berlin：Springer，2006：180-197.

［17］ ASHAROV G，CANETTI R，HAZAY C.Towards a game theoretic view of secure computation［G］∥Proc. of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin：Springer，2011：426-445.

［18］ GROCE A，KATZ J.Fair computation with rational player［G］∥Proc.of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin：Springer，2012：81-98.

［19］ 張恩，蔡永泉.理性的安全兩方計算協議［J］.計算機研究與發展，2013，50（7）：1409-1417.

ZHANG En，CAI Yongquan.Rational secure two-party computation protocol［J］. Journal of Computer Research and Development，2013，50（7）：1409-1417.

［20］ 王伊蕾，鄭志華，王皓，等.滿足可計算序貫均衡的理性公平計算［J］.計算機研究與發展，2014，51（7）：1527-1537.

WANG Yilei，ZHENG Zhihua，WANG Hao，et al. Rational fair computation with computational sequential equilibrium［J］.Journal of Computer Research and Development，2014，51（7）：1527-1537.

［21］ OSBORNE M，RUBINSTEIN A.A course in game theory［M］.Cambridge：MIT Press，2004：10-15.

［22］ KATZ J.Bridging game theory and cryptography：recent results and future directions［G］∥Proc.of the 5th Theory of Cryptography Conf（TCC 2008）.Berlin：Springer，2008：251-25.

基于博弈論的公平安全兩方計算協議

王 潔

Fair Secure Two-Party Computation Protocol Based on Game Theory

WANG Jie
（College of Mathematics and Computer Science，Shanxi Normal University，Linfen 041004，China）

Since complete fairness cannot be achieved in traditional two-party computation，a rational two-party computation protocol，based on game theory，was proposed，which regards player as rational.At first，the game model of secure two-party computation was put forward in the extensive game framework.Secondly，according to the description of game model，the ideal function FRPCPof rational secure two-party computation and rational two-party computation protocol πRPCPwere presented. Finally，the security，fairness and Nash Equilibrium of protocol was analyzed.The analysis results show that the protocol πRPCPcan realize ideal function FRPCPsafely in the hybrid model；meanwhile，under the Bilinear Diffie-Hellman（BDH）assumption，the best strategy of the rational players is to choose cooperation；and when the game achieves Nash Equilibrium，all players can obtain the right results fairly.

secure two-party computation；extensive game；Nash Equilibrium；fairness

0258-2724（2016）05-0902-08

10.3969/j.issn.0258-2724.2016.05.012

TP309

A

2015-08-21

王潔（1977—），女，副教授，研究方向為信息安全，E-mail：lktwj0801@163.com

王潔.基于博弈論的公平安全兩方計算協議［J］.2016，51（5）：902-909.

（中文編輯：唐 晴 英文編輯：周 堯）