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

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

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

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

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

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

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

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

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

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

1 基礎(chǔ)知識(shí)

1.1 雙線性對(duì)

定義1（雙線性對(duì)） 設(shè)（G1，+）和（G2，·）為兩個(gè)階數(shù)均為素?cái)?shù)p的循環(huán)群，其中前者為加法群，后者為乘法群.令P為G1的生成元，如果滿足下面的性質(zhì)，稱變換e∶G1×G1→G2為雙線性對(duì).

（1）雙線性：對(duì)任意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，也就是說(shuō)e（P，P）是G2的生成元；

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

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

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

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

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

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

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

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

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

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

博弈論主要研究利益存在沖突的決策主體在相互對(duì)抗中，對(duì)抗雙方（或多方）相互依存的一系列策略和行動(dòng)的過(guò)程集合.在分析其他參與方可能出現(xiàn)的行為策略基礎(chǔ)上，理性參與者會(huì)選擇對(duì)自己最有利的策略，均衡就是在參與方選擇各自最優(yōu)策略時(shí)所達(dá)到的一種穩(wěn)定狀態(tài)，這時(shí)任何參與方都不會(huì)單獨(dú)改變策略，因?yàn)楦淖儾呗砸馕吨陨砝娴膿p失，因此沒(méi)有人會(huì)愿意打破這一狀態(tài).

設(shè)P=｛P1，P2，…，Pn｝表示由n個(gè)參與者組成的集合，用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è)理性兩方計(jì)算中的參與者總是希望得到輸出結(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′），對(duì)于所有j≠i，有Oj（o）≤Oj（o′），并存在某個(gè)j滿足Oj（o）＜Oj（o′），那么ui（o）＞ui（o′）.

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

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

（1）空序列φ屬于Q；

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

（3）如果無(wú)限行動(dòng)序列ak∈Q，k=1，2，…，∞滿足ak∈Q，k=1，2，…，v對(duì)任意正整數(shù)v，則ak∈Q，k=1，2，…，∞.

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

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

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

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

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

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

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

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

2 理性兩方計(jì)算博弈模型

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

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

2.1 參與人

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

2.2 信息集

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

2.3 策略集

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

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

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

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

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

2.4 效用函數(shù)

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

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

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

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

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

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

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

3 公平的理性兩方計(jì)算理想模型

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

給定需計(jì)算的二元函數(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）的輸入值，同時(shí)給每位參與者都發(fā)送回復(fù)消息（Pinput，receipt，Psid）后，F(xiàn)RPCP計(jì)算隨機(jī)函數(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)識(shí)為“賄賂”的參與者，則給其發(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提供另一個(gè)值w′，并且計(jì)算函數(shù)的輸出階段其輸出值fi還沒(méi)有寫(xiě)在Pi的輸出帶上，則置xi=w′.

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

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

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

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

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

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

P1執(zhí)行如下：

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

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

步驟2 生成兩個(gè)次數(shù)為t1-1的多項(xiàng)式f（x）和g（x）：

式中：x1=a0+b0；

步驟3 計(jì)算承諾對(duì)

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

步驟4 計(jì)算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ù)幾何分布隨機(jī)從｛1，2，…，p｝選取t2（其中p是群G1的階）；

步驟2 生成兩個(gè)次數(shù)為t2-1的多項(xiàng)式f（x）和g（x）：

式中：x2=a0+b0.

步驟3 計(jì)算承諾對(duì)

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

步驟4 計(jì)算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ù)交互計(jì)算階段

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

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

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

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

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

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

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

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

4.3 結(jié)果輸出階段

此階段分如下兩步：

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

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

5 方案分析

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

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

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

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

5.1 仿真可信第三方（TTP）

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

5.2 仿真發(fā)送者

當(dāng)未被攻陷的參與者通過(guò)輸入激活消息被激活，仿真敵手通過(guò)FRPCP得到該消息，同時(shí)為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)未被攻陷的參與者通過(guò)輸入激活信息被激活，S從FRPCP得到該信息，同時(shí)為A仿真協(xié)議πRPCP.

5.4 仿真攻陷

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

IDEAL和REAl的不可區(qū)分性：基于所構(gòu)造的理想敵手S，定義3類事件，同時(shí)證明下述3類事件中，無(wú)論哪一類事件發(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í)行過(guò)程中，Pi試圖從公開(kāi)信息中推斷出對(duì)方的秘密輸入信息，根據(jù)多項(xiàng)式的構(gòu)造以及BDH假設(shè)可知，此時(shí)S能完美完成仿真協(xié)議操作.故此情況下，REAL和IDEAL是不可區(qū)分的.

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

定理2 在BDH困難假設(shè)下，協(xié)議實(shí)例πRPCP執(zhí)行中各理性參與者的最佳策略是C，即選擇互相合作，此時(shí)各參與者的效用均為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)識(shí)為“賄賂”的參與者，則給其發(fā)送⊥，而給其余參與者發(fā)送相應(yīng)的fi；

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

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

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

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

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

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

安全兩方計(jì)算協(xié)議中的公平性問(wèn)題是密碼學(xué)中的一個(gè)難題，本文結(jié)合博弈論方法對(duì)其進(jìn)行了研究.首先基于擴(kuò)展博弈提出了理性安全公平兩方計(jì)算協(xié)議的博弈模型；其次根據(jù)博弈模型，對(duì)理性安全兩方協(xié)議的安全性和公平性進(jìn)行了分析，給出了其博弈模型下理想函數(shù)FRPCP，在此基礎(chǔ)上基于雙線性對(duì)技術(shù)，構(gòu)造了公平的理性安全兩方計(jì)算協(xié)議πRPCP；最后在混合模型下證明了理性安全兩方計(jì)算協(xié)議πRPCP能安全實(shí)現(xiàn)其理想函數(shù)FRPCP，并且分析了當(dāng)兩方博弈達(dá)到納什均衡狀態(tài)時(shí)，參與者雙方能公平地獲得計(jì)算結(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］ 李順東，戴一奇，游啟友.姚氏百萬(wàn)富翁問(wèn)題的高效解決方案［J］.電子學(xué)報(bào)，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］ 唐春明，石桂花，姚正安.排序問(wèn)題的安全多方計(jì)算協(xié)議［J］.中國(guó)科學(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］ 田有亮，彭長(zhǎng)根，馬建峰，等.通用可組合公平安全多方計(jì)算協(xié)議［J］.通信學(xué)報(bào)，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ì)算協(xié)議［J］.計(jì)算機(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ì)算序貫均衡的理性公平計(jì)算［J］.計(jì)算機(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.

基于博弈論的公平安全兩方計(jì)算協(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—），女，副教授，研究方向?yàn)樾畔踩?，E-mail：lktwj0801@163.com

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

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