（山西師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西臨汾041004）

（山西師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西臨汾041004）

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

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

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

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

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

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

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

1 基礎(chǔ)知識

1.1 雙線性對

定義1（雙線性對） 設(shè)（G1，+）和（G2，·）為兩個階數(shù)均為素數(shù)p的循環(huán)群，其中前者為加法群，后者為乘法群.令P為G1的生成元，如果滿足下面的性質(zhì)，稱變換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（可忽略函數(shù)） 函數(shù)μ（·）＜1/p（k）是可忽略函數(shù)，如果對任意正多項式p（·）和足夠大的正數(shù)k都有μ（k）＜1/p（k）成立.

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

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

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

則稱這兩個總體是在多項式時間內(nèi)不可區(qū)分的.

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

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

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

1.2 博弈論相關(guān)概念

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

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

（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′）.

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

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

（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對任意正整數(shù)v，則ak∈Q，k=1，2，…，∞.

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

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

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

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

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

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

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

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

2 理性兩方計算博弈模型

理性安全兩方計算是指參與者為理性的安全兩方計算協(xié)議，與傳統(tǒng)安全兩方計算最大的區(qū)別在于參與者根據(jù)他們的效用來決定是否遵守協(xié)議.

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

2.1 參與人

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

2.2 信息集

最后終結(jié)于博弈的葉子節(jié)點.

2.3 策略集

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

（1）按照協(xié)議的方式發(fā)送正確的信息，記為C；

（2）按照協(xié)議的方式發(fā)送錯誤的信息，記為D；

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

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

2.4 效用函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

③發(fā)送（Pinput，receipt，Psid）給Pi.

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

當(dāng)收到（P1，P2）的輸入值，同時給每位參與者都發(fā)送回復(fù)消息（Pinput，receipt，Psid）后，F(xiàn)RPCP計算隨機函數(shù)

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

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

①若當(dāng)前存在被標(biāo)識為“賄賂”的參與者，則給其發(fā)送中斷符⊥，給其余參與者發(fā)送相應(yīng)的fi；

②否則，給每位參與者Pi發(fā)送fi.

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

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

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

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

②轉(zhuǎn)發(fā)fi給敵手S；

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

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

4 公平的理性兩方計算協(xié)議

本節(jié)利用雙線性對技術(shù)，設(shè)計理性公平計算協(xié)議，記該協(xié)議為πRPCP.

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

4.1 數(shù)據(jù)準(zhǔn)備階段

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

P1執(zhí)行如下：

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

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

步驟2 生成兩個次數(shù)為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執(zhí)行如下：

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

步驟2 生成兩個次數(shù)為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 數(shù)據(jù)交互計算階段

步驟1 參與者P1給參與者P2發(fā)送x10，P2給參與者P1發(fā)送x20.

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

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

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

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

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

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

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

4.3 結(jié)果輸出階段

此階段分如下兩步：

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

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

5 方案分析

本節(jié)對所構(gòu)造的協(xié)議進(jìn)行安全性、公平性及納什均衡分析.

定理1 在BDH困難假設(shè)下，所構(gòu)造的理性安全公平計算協(xié)議πRPCP是安全的和公平的，即協(xié)議πRPCP能安全實現(xiàn)其理想函數(shù)FRPCP.

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

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

5.1 仿真可信第三方（TTP）

當(dāng)一個可信的TTP被激活，S從FRPCP得到相關(guān)激活信息，并為敵手S仿真協(xié)議πRPCP.

5.2 仿真發(fā)送者

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

（1）當(dāng)S從FRPCP得到參與者P′1激活消息，S發(fā)送該消息給A，然后轉(zhuǎn)發(fā)A的回復(fù)給FRPCP.

（2）當(dāng)S從FRPCP得到參與者P′2激活消息，S發(fā)送該消息給A，然后轉(zhuǎn)發(fā)A的回復(fù)給FRPCP.

5.3 仿真接收者

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

5.4 仿真攻陷

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

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

事件1 當(dāng)某參與者Pi被攻陷，很容易觀察到，在 REAL環(huán)境下，根據(jù)理想博弈模型、協(xié)議πRPCP的程序規(guī)則，可知S能完美仿真協(xié)議操作.因此，在此情況下，REAL和IDEAL是不可區(qū)分的.

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

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

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

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

（1）若當(dāng)前存在被標(biāo)識為“賄賂”的參與者，則給其發(fā)送⊥，而給其余參與者發(fā)送相應(yīng)的fi；

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

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

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

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

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

6 結(jié)束語

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

［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］.電子學(xué)報，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］ 唐春明，石桂花，姚正安.排序問題的安全多方計算協(xié)議［J］.中國科學(xué)：信息科學(xué)，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］ 田有亮，彭長根，馬建峰，等.通用可組合公平安全多方計算協(xié)議［J］.通信學(xué)報，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］ 張恩，蔡永泉.理性的安全兩方計算協(xié)議［J］.計算機研究與發(fā)展，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］.計算機研究與發(fā)展，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.

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

王 潔

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

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

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