理性密碼協(xié)議研究進展

摘 要：理性密碼協(xié)議結(jié)合密碼學與博弈理論，擴展了密碼學與博弈理論的研究領(lǐng)域，為彌補傳統(tǒng)密碼學中未考慮參與者行為對協(xié)議造成的影響而提供了新的研究思路，現(xiàn)已成為當前密碼領(lǐng)域的研究熱點。傳統(tǒng)經(jīng)典密碼系統(tǒng)中，參與者要么是誠實的，要么是惡意的，參與者為了達到某種目的必須付出一定代價。理性密碼協(xié)議中引入理性的參與者，介紹理性密碼協(xié)議的安全性定義，從博弈的角度討論密碼協(xié)議的公平性；其次，對理性秘密共享、理性安全多方計算、理性交換協(xié)議和理性認證協(xié)議等研究現(xiàn)狀進行了研究；最后簡單地闡述了有關(guān)理性密碼協(xié)議面臨的問題與挑戰(zhàn)。

關(guān)鍵詞：理性密碼協(xié)議；博弈論；安全性；公平性

中圖分類號：TP309.7

文獻標識碼： A

理性密碼協(xié)議作為一個新興的研究領(lǐng)域，其主要研究方向是利用數(shù)學和經(jīng)濟學中博弈論的思想來分析傳統(tǒng)密碼協(xié)議。傳統(tǒng)的密碼協(xié)議模型中，參與者一般是誠實的或者惡意的，密碼協(xié)議的參與者為達到某種通信目的需要付出很大的代價。因此，參與者可能會從自身利益最大化的角度來選擇自己的行動，從這個意義上來說，密碼協(xié)議中的理性參與者正好與博弈論中的理性局中人相符。但傳統(tǒng)的密碼協(xié)議側(cè)重于協(xié)議的設(shè)計與實現(xiàn)，其安全性和效率等是協(xié)議中參與者較為關(guān)心的問題；而博弈論則側(cè)重于博弈策略及規(guī)則設(shè)計，其最終的個人或集體收益問題是博弈中各參與者關(guān)心的問題。理性密碼協(xié)議是傳統(tǒng)的密碼學和博弈論相結(jié)合的產(chǎn)物，它擴展了密碼學與博弈理論的研究領(lǐng)域，為彌補傳統(tǒng)密碼學中未考慮參與者行為對協(xié)議造成的影響提供了新的研究思路。在這種背景下，密碼學和博弈論相結(jié)合的理性密碼學[1]逐漸成為研究熱點，在當前云計算背景下更是如此。

密碼學與博弈論的結(jié)合在早期就有學者進行研究，博弈論[2-3]就是研究參與者是如何進行決策以及如何達到納什均衡的問題。1993年Fischer等[4]針對博弈論與密碼協(xié)議的關(guān)系進行了分析，利用了博弈論技術(shù)來分析多方密碼交換協(xié)議；Dodis、Halevi和Rabin[5]解決了當系統(tǒng)中存在可信第三方時，二人之間博弈存在性的判定性問題可以由效用進行比較；隨后Bettyan等[6]根據(jù)博弈論中納什均衡提出了理性交換的概念，給出了密碼協(xié)議公平性的不同的形式化定義，證明了如何通過公平交換將理性交換推出；Asokan、Shoup和Waidner[7] 基于博弈論技術(shù)應(yīng)用隨機化方法闡述了公平簽名交換的形式化安全模型；Caballero Gil等[8]通過博弈論技術(shù)研究了密碼協(xié)議的理性方法；利用博弈論作為一種形式化工具建模分析具體的密碼協(xié)議，如公平安全交換協(xié)議及簽約[9-11]。

其中，眾多學者們極為關(guān)注的問題就是密碼協(xié)議的公平性。早在1986年，Cleve[12]在文中指出如果存在多數(shù)的惡意參與者，實現(xiàn)公平的安全計算是不可能實現(xiàn)的；隨后Gordon等[13-15]證明了某些特殊函數(shù)的安全多方計算是能完全公平實現(xiàn)，研究在誠實參與者占多數(shù)情況下多方安全計算問題的部分公平性實現(xiàn)問題及探討了部分公平性的不同概念；Tian等[16]研究秘密共享協(xié)議的公平性問題，提出公平的秘密分發(fā)和重構(gòu)方案，在三種攻擊模型下進行公平性和安全性證明；Groce和Katz [17]證明在理想環(huán)境下只要有一人有嚴格的動機去計算一個函數(shù)，則實現(xiàn)其函數(shù)的理性公平計算是可能的，指出還不清楚理性公平性與部分公平性、完全公平性的關(guān)系。理性密碼協(xié)議研究的內(nèi)容主要集中在理性秘密共享、理性委托計算、理性安全多方計算、理性交換協(xié)議和理性認證協(xié)議等。理性秘密共享是將傳統(tǒng)秘密共享中誠實或者惡意的參與者換成理性參與者，Halpern等[18]首次提出了理性秘密共享的概念，并提出理性安全多方計算是理性秘密共享協(xié)議的一種直接應(yīng)用；Abraham等[19]學者考慮到局中人可以結(jié)盟的情況下，分析了理性秘密共享和安全多方計算問題，他們用一個可信第三方作為博弈中仲裁者；理性交換協(xié)議[20]是通過發(fā)送消息視為一種支出而接收到信息視為一種收入來刻畫每位參與者間的效用；Tian等[21]在博弈論框架下分析秘密共享體制的分發(fā)機制和重構(gòu)機制，并針對其問題給出了理想的解決方案；他們也基于貝葉斯博弈研究有關(guān)一次秘密共享的問題，并解決該類理性秘密共享體制的合作問題[22]。

本研究主要圍繞理性密碼協(xié)議的發(fā)展展開探討，探究理性密碼協(xié)議的效率及優(yōu)化模型。首先介紹了博弈論在密碼學中應(yīng)用的相關(guān)概念及方法，密碼學相關(guān)的基本概念；其次重點綜述各典型理性密碼協(xié)議近年來的發(fā)展研究成果及其應(yīng)用場景；接著總結(jié)我們近年來在理性密碼協(xié)議及其公平性，安全性等方面的相關(guān)研究工作；最后提出理性密碼協(xié)議面臨的問題及挑戰(zhàn)，并給出相關(guān)思考與展望。

1 密碼學與博弈論相關(guān)概念

1.1 密碼學相關(guān)概念

1.1.1 雙線性映射

1.1.2 安全多方計算

安全多方計算是分布式密碼學的理論基礎(chǔ)，也屬于分布式計算研究的一個基本問題，安全多方計算蘊含了密碼學中很多協(xié)議問題及在原則上的實現(xiàn)方案。最早是由A.Yao[23]在1982年通過姚氏百萬富翁問題提出了安全兩方計算問題。

安全多方計算是指在一個分布式網(wǎng)絡(luò)中，如存在n個互不信任的參與者P1，…，Pn，每個參與者Pi的私有輸入為xi，所有的參與者共同計算函數(shù)

其中，函數(shù)F中參與者Pi的輸入xi對應(yīng)的輸出為yi，并且函數(shù)中n個輸入全部由n個不同的參與者秘密掌握。在函數(shù)的計算過程中，參與者Pi除可以得到y(tǒng)i外，不能得到其他參與者的任何信息。

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

2 典型的理性密碼協(xié)議

2.1 理性秘密共享

b.秘密重構(gòu)階段

分組轉(zhuǎn)發(fā)階段

Round 1

Step1 A組參與者向B組參與者廣播自己的影子秘密；

Step2 B組參與者利用A組參與者公開的承諾驗證其影子秘密的正確性，如果正確，則進行下一步，否則，向其余參與者公布Ai是惡意參與者，并建議將Ai剔除出局，重新運行剩余n-1參與者的分組轉(zhuǎn)發(fā)階段；

Step3 B組參與者向C組參與者廣播自己的影子秘密；

Step4 C組參與者利用B組參與者公開的承諾驗證其影子秘密的正確性，同Step2；

Step5 C組參與者向A組參與者廣播自己的影子秘密；

Step6 A組參與者利用C組參與者公開的承諾驗證其影子秘密的正確性，同Step2。

Round 2

第二輪分組轉(zhuǎn)發(fā)階段同第一輪類似，其影子秘密的廣播變?yōu)榈诙€影子秘密。

公開階段

Step1 A組參與者計算其概率與其預(yù)期的效用，得到最優(yōu)的策略，并公開第二輪影子秘密；

Step2 C組參與者向A組參與者得到影子秘密后，驗證其正確性更新其信譽值；

Step3 同理，參與者B、C兩組參與者也根據(jù)貝葉斯規(guī)則廣播自己第二輪得到的影子秘密。

最后，當秘密重構(gòu)者得到t份秘密后根據(jù)拉格朗日差值多項式可以重構(gòu)出秘密擁有者擁有的秘密a。該協(xié)議證明了（t，n）門限理性秘密共享中參與者會存在的不合理行為，并為參與者選出了得到最大效用的最優(yōu)策略。

在理性秘密共享協(xié)議中，由于參與者的自利性可能會使理性參與者偏離協(xié)議，從而影響協(xié)議的公平性。在（t，n）門限理性秘密共享中，（2，2）理性理性秘密共享方案的公平性較難實現(xiàn)。基于不完全信息動態(tài)博弈模型，通過分析理性參與者在（2，2）秘密重構(gòu)階段可能采取的策略和信念系統(tǒng)，引入理性參與者的期望收益，研究（2，2）理性秘密共享重構(gòu)階段的完美貝葉斯均衡問題。我們將分析適用于異步通信的公平的（2，2）理性秘密共享方案。

設(shè)承諾函數(shù)為C（·）為單向函數(shù)，當共享秘密S=S1S2時，承諾函數(shù)C（S）=C（S1）C（S2）。

秘密分發(fā)協(xié)議πDis

Step1 秘密擁有者選擇拉格朗日多項式，將秘密S分為S1和S2，并計算C（S），C（S1）和C（S2）；

Step2 秘密擁有者將消息Si秘密地發(fā)送給參與者Pi，并將消息C（S），C（S1）和C（S2）進行廣播。

秘密重構(gòu)協(xié)議πRec

Step1 理性參與者Pi將收到的子秘密Si用拉格朗日插值法將子秘密Si拆分成影子秘密Si1和Si2；

Step2 其中，如果ri=min{r1，r2}，則理性參與者Pi將影子秘密Si1傳遞給P-i，否則，參與者P-i將影子秘密S-i1傳遞給Pi；

Step3 參與者P-i收到Pi傳遞的影子秘密后，傳遞影子秘密S-i1傳遞給Pi，否則，使用交互記錄機制M，并返回Step1；

Step4 參與者Pi收到P-i傳遞的影子秘密后，傳遞影子秘密Si2給P-i，否則，使用交互記錄機制M，并返回Step1；

Step5 參與者P-i收到Pi傳遞的影子秘密Si2后，重構(gòu)子秘密Si′，并驗證C（Si′）。如果C（Si）=C（Si′），則傳遞影子秘密S-i2給Pi，提升ri，否則，使用交互記錄機制M，并返回Step1；

Step6 參與者Pi收到S-i2后，重構(gòu)子秘密S-i′，并驗證C（S-i′）。如果C（S-i）=C（S-i′），則提升r-i，否則，使用交互記錄機制M，并返回Step1；

Step7 參與者P-i使用交互記錄機制M。

在上述協(xié)議中，若參與者Pi不發(fā)送影子秘密Si1或Si2或者發(fā)送錯誤的影子秘密，則參與者P-i使用交互記錄機制M，此時參與者Pi和P-i的收益都為u（13）-i；若參與者P-i不發(fā)送影子秘密S-i2或發(fā)送錯誤的影子秘密，此時參與者Pi使用交互記錄機制M，此時Pi的收益為u（15）i或者u（7）i；若參與者Pi和P-i都遵守協(xié)議，正確執(zhí)行，則Pi和P-i的收益為u（4）i和u（4）-i。即對于理性參與者Pi和P-i來說，只有當都遵守協(xié)議是收益最大，且均可提升自己的信譽值。

綜上：基于交互記錄機制M的（2，2）貝葉斯理性秘密共享方案是公平的。

許多研究者都對理性秘密共享進行了研究，2008年Maleka等[26]將博弈理論和秘密共享進行結(jié)合，他們提出了折扣因子δ∈（0，1），使得所有的理性參與者的效用為ui+δui+δui2+n，闡述了確定性理性秘密共享方案；2009年Asharov等[27]也參與研究了在博弈論的環(huán)境中秘密共享的效用問題；Micali和Shelat等[28]在秘密共享方案中引入理性的誠實參與者，設(shè)計了公平的具有常數(shù)輪的理性秘密共享方案；Tian等[29]用貝葉斯博弈研究一次理性秘密共享問題，引入了完美貝葉斯均衡，針對理性秘密共享中不可能的結(jié)果，給出了解決方案；Peng等[30]通過考慮不同參與者不同時期的效用，引入了理性參與者混合收益模型；Liu等[31]結(jié)合VCG機制設(shè)計約束理性參與者的行為，確保了（2，2）理性秘密共享的公平性；Tian等[32]通過提高理性參與者的信譽激勵函數(shù)，構(gòu)造出僅需1個秘密重構(gòu)的（2，2）的理性秘密共享方案；Harn等[33]設(shè)計了異步理性秘密共享方案，方案不需要對理性參與者和交互數(shù)量進行要求。

2.2 理性安全多方計算

多方博弈、多方安全計算、多方通信等分支的交叉催生了理性安全多方計算這個新興的研究領(lǐng)域，理性安全多方計算致力于解決理性協(xié)議運行與預(yù)期假設(shè)的一致性問題。其中，公平性、隱私性和正確性是理性安全多方計算極為重要的性質(zhì)。

2006年，Lysyanskaya等[34]提出了參與者是理性或者惡意的混合模型，分析了理性安全多方計算的問題；隨后，Groce等[35]也對兩方理性公平計算進行了研究，他們使用了不確定論數(shù)的方法，研究出當理性參與者猜出正確輪數(shù)為α<（a0-u0）/（b0-u0）的概率時，設(shè)計的協(xié)議為公平的；Wallrabenstein等[36]提出了公平理性多方安全計算方案，利用完美貝葉斯均衡解決理性多方安全計算中不可解的問題；Wang等[37]提出了社會理性多方安全計算方案，將理性參與者的信譽問題引入到多方計算的博弈中，利用理性參與者的信譽來約束其行為策略；Wang等[38]在完美信息博弈下設(shè)計了可計算序貫博弈，可以使理性安全多方計算協(xié)議的安全性更高。

本文以理性安全多方求和協(xié)議為例，其執(zhí)行過程與分析如下：

假設(shè)存在理性安全多方計算協(xié)議，有n位理性參與者Pi（i=1，…，n），每位參與者的隱私數(shù)據(jù)分別為si（i=1，…，n），其中si∈{0，1，…，m}是非負整數(shù)。協(xié)議要求所有理性參與者共同計算s=∑ni=1si的值，記為Ρ=mn+1。

Step1 理性參與者P1產(chǎn)生隨機數(shù)R（0≤R≤P），并計算a1=（s1+R）modP發(fā)送給另一位理性參與者P2；

Step2 理性參與者Pi（i=2，…，n-1）將接收數(shù)據(jù)ai-1，并計算ai=（ai-1+si）modP發(fā)送給參與者Pi+1；

Step3 理性參與者Pn接收數(shù)據(jù)an-1，并計算an=（an-1+sn）modP發(fā)送給P1；

Step4 理性參與者P1接收數(shù)據(jù)an，并計算s=（an-R）modP將計算值s進行廣播。

由于我們的參與者都是理性的，都會根據(jù)自己的效益選擇不同的策略，根據(jù)參與者不同的策略將會有不用的效用函數(shù)。在該方案中，理性參與者在不同情況下收益不同，考慮到其計算與通信收益、隱蔽攻擊收益、共謀收益以及其整體收益，最終構(gòu)造出理性安全多方計算求和協(xié)議的整體收益函數(shù)。

在安全多方計算中，當惡意參與者超過一半時，其公平性很難達到。為了體現(xiàn)聲譽對效用函數(shù)的影響，提出了合作公平均衡，并利用其實現(xiàn)理性兩方計算和多方計算的公平性，其具體協(xié)議分析如下：

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

在理想模型下，我們假設(shè)存在一個可信第三方（TTP），理性參與者Px的私有輸入為x∈X，理性參與者Py的私有輸入為y∈Y，其中X和Y是多項式長度的。其理性兩方的計算過程執(zhí)行如下，

1）理性參與者將自己的私有輸入x，y，效用函數(shù)以及其策略集合都發(fā)送給可信第三方（TTP）；

2）可信第三方（TTP）收到消息后，計算函數(shù)f（x，y）的值，并根據(jù)其效用函數(shù)為理性的參與者選擇最優(yōu)策略；

3）可信第三方（TTP）將計算的結(jié)果fi（x，y）和選擇的最優(yōu)策略ai（i∈{1，2}）發(fā)送給理性的參與者Pi。

對于兩方公平計算，在理性模型下，可信第三方（TTP）將計算結(jié)果發(fā)送給每個參與者，使得所有參與者都能得到正確結(jié)果，從而達到公平。

理性多方公平計算

為了證明理性多方計算能夠達到多方合作的均衡，從而達到公平計算，將多個理性參與者考慮為一個網(wǎng)絡(luò)，具體執(zhí)行過程如下，

1）理性參與者Pi將其私有輸入xi，策略組集合Ai和效用函數(shù)Ui發(fā)送給可信第三方（TTP）；

2）可信第三方（TTP）收到消息后，計算函數(shù)f（x，…，xn）的值，根據(jù)其效用函數(shù)為理性的參與者選擇最優(yōu)策略；

3）可信第三方（TTP）將計算結(jié)果f（x，…，xn）以及其最優(yōu)策略ai（i∈{1，…，n}）發(fā)送給理性的參與者Pi。

理性多方公平計算協(xié)議可以由參與者構(gòu)成一個網(wǎng)絡(luò)，即可以給出理性公平計算的模塊，借鑒其模塊化思想，使得每個子模塊是一個理性兩方公平計算協(xié)議，且都能達到其公平性。

2.3 理性交換協(xié)議

理性交換協(xié)議是解決小額支付的有效方法，且該協(xié)議是一個動態(tài)博弈模型。協(xié)議在完全不完美動態(tài)博弈中進行分析，用極大熵原理解決協(xié)議中理性參與者策略的推斷問題。協(xié)議主要依賴于公平交換原則和理性交換原則解決協(xié)議中不誠實參與者的不端行為。

早在1998年Asokan[39]就在歐洲密碼學會上提出將博弈論引入到公平交換協(xié)議中，并給出一個兩方理性參與者在網(wǎng)絡(luò)中相互交換數(shù)字簽名的公平協(xié)議；同年Syverson[40]首次提出了理性交換的概念，在協(xié)議中參與者不能因惡意行為而獲利，即理性參與者沒有偏離協(xié)議的理由；Buttyan等[41]在交換協(xié)議中使用博弈論給出了公平性的形式化定義，并對交換協(xié)議進行形式化分析；Ding[42]引入熵函數(shù)對交換協(xié)議的過程公平性進行描述保證過程公平性原則下運用混合策略納什均衡概念形式化定義理性公平性，在此模型基礎(chǔ)上構(gòu)造一個新的理性交換協(xié)議；Alcaide等[43]引入信念在交換協(xié)議中，并利用不完全信息動態(tài)博弈建立了貝葉斯博弈下的理性交換協(xié)議模型；Jiang[44]將信息論引入進博弈論的系統(tǒng)中，為理性交換協(xié)議的研究提供了新思路；在關(guān)于理性交換協(xié)議的研究中，研究者對理性交換協(xié)議的公平性[45]研究也得到了一定的關(guān)注，并加大對其研究力度。

本文對基于信息熵的理性交換協(xié)議進行分析，其執(zhí)行過程如下：

假設(shè)存在兩方理性參與者P1、P2，他們將在網(wǎng)上進行交易，且要交換的物品為G1、G2；其中，G1是理性參與者P1用來交換的物品，G1的價值是有關(guān)時間的線性函數(shù)，隨著時間增長而遞減；G2是理性參與者P2用來交換的物品，但是G2的價值不會隨著時間的增長而改變；在協(xié)議中設(shè)置時間保密函數(shù)h（k），在一段時間內(nèi)該協(xié)議是不可攻破的，保證參與者可以正常地進行交換交易。

Step1 參與者P1將包含m1的消息發(fā)送給參與者P2，P1用自己的私鑰進行簽名，用P2的公鑰進行加密；P1隨機選擇對稱密鑰k1對自己的物品進行加密，得到加密后的物品Ek1（G1），其限時的保密函數(shù)為h（k1），在一定時間內(nèi)對密鑰k1進行保密。

Step2 當參與者P2收到P1發(fā)送過來的加密簽名后，對其進行驗證并確定物品G1是否是自己想要的物品。根據(jù)極大熵原則，推斷參與者P1發(fā)送Ek1（G1）或者Ek1（G1）的概率。隨后參與者P2將包含m2的消息發(fā)送給參與者P1，P2用自己的私鑰進行簽名，用P1的公鑰進行加密；P2隨機選擇對稱密鑰k2對自己的物品進行加密，得到加密后的物品Ek2（G2），其限時的保密函數(shù)為h（k2），在一定時間內(nèi)對密鑰k2進行保密。

Step3 當參與者P1收到P2發(fā)送過來的加密簽名后，對其進行驗證并確定物品G2是否是自己想要的物品。如果通過驗證的話，根據(jù)極大熵原則，推斷參與者P2發(fā)送Ek2（G2）或者Ek2（G2）的概率。接下來參與者P1將消息m3發(fā)送給參與者P2，其中m3=（P2，k1，m2，t），t是對應(yīng)的時間戳。

以上是理性交換協(xié)議的過程，其協(xié)議分析如下：

如果在第一步中，參與者P1存在欺騙行為，發(fā)送虛假的物品，那么在第三輪中，參與者P2將用密鑰k解密，即能發(fā)現(xiàn)參與者P1存在的欺騙行為，并根據(jù)參與者P1的簽名致使其受到懲罰。

在第二步中，若參與者P2存在欺騙行為，發(fā)送虛假的物品，經(jīng)過一段交互P1也將發(fā)現(xiàn)P2的欺騙行為。同理，P1根據(jù)參與者P2的簽名致使其受到懲罰。

在第三步中，若參與者P1沒有給參與者P2發(fā)送消息m3，那么參與者P2將會對P1提起公訴，致使其受到懲罰；若參與者P2收到消息卻仍對參與者P1提起公訴，參與者P1可根據(jù)其時間戳t來證明自己發(fā)送過消息m3保證其交易的公平性。

在理性交換協(xié)議中，協(xié)議都具有安全性、正確性、公平性等性質(zhì)，這樣才能保證參與者在交易過程中遵循協(xié)議的執(zhí)行，若假設(shè)其加密方法安全，通信網(wǎng)絡(luò)可靠的話，引入信息論中的熵理論對協(xié)議中的不確定性進行描述，可以給出協(xié)議的公平性證明。

2.4 理性認證協(xié)議

身份認證協(xié)議結(jié)合博弈理論的思想研究，已成為研究熱點。研究者表明，在理性認證協(xié)議中，惡意的攻擊者攻擊協(xié)議所獲得的期望收益始終比不攻擊所獲得的收益低，從而使得理性的攻擊者不再選擇對協(xié)議進行攻擊，保證理性認證協(xié)議的安全性。

Gordon等[46]曾提出，要使攻擊者放棄對一個協(xié)議進行攻擊，那么必須得使其獲得一些收益，且這個收益要比不攻擊協(xié)議得到的多。在該思想影響下，NGUYEN L H[47]對認證協(xié)議進行改進，引入了博弈理論對認證協(xié)議進行分析，并提高協(xié)議的安全性；隨后，Li等[48]將NGUYEN L H的方案進行了改進，給出了誠實節(jié)點發(fā)送無用數(shù)據(jù)的前提條件，并給出了不同情況下概率α的取值范圍，該方案更具有一般性。

理性認證協(xié)議的主要思想是引入一定概率發(fā)送無用數(shù)據(jù)的行為：

1）在概率α的情況下，誠實節(jié)點A將會認證或傳送一些無用數(shù)據(jù)，這些數(shù)據(jù)可能包括公鑰PKA，但節(jié)點A并不知道其對應(yīng)的私鑰。若在發(fā)送過程中，攻擊者沒有攻擊，則認證的另一方B將接受發(fā)送的公鑰PKA并加密數(shù)據(jù)發(fā)送給A。當發(fā)送無用的數(shù)據(jù)結(jié)束后，參與者A和B將進行重新認證，發(fā)送有效的數(shù)據(jù)。

2）在概率1-α的情況下，認證方A遵守協(xié)議的執(zhí)行進行認證消息，若此過程無任何攻擊行為出現(xiàn)，此次認證協(xié)議將會成功。若此過程中攻擊者攔截或修改了傳輸?shù)臄?shù)據(jù)，認證者A不管采取什么策略，攻擊者的收益都為以下三種情況。

a.攻擊者以概率ε攻擊成功，則獲得的收益為U+。

b.攻擊者以概率1-ε攻擊失敗，且仍發(fā)起一次拒絕服務(wù)攻擊，阻礙認證者A和B之間的數(shù)據(jù)傳輸，此時獲得的收益為U-。

c.在誠實節(jié)點以概率α的情況下傳輸無用數(shù)據(jù)時，對于攻擊者而言，他比較希望認證者認證無效的數(shù)據(jù)，即代表攻擊者干擾了認證者正常執(zhí)行的目的，此時獲得的收益為U。

基于以上分析有攻擊者效益分布：U+≥U≥U-。切要考慮誠實節(jié)點的策略選擇，誠實節(jié)點不傳輸無用數(shù)據(jù)而直接執(zhí)行基于口令的認證協(xié)議時，攻擊者發(fā)起k次攻擊成功（或不成功）的概率和收益。且攻擊者的攻擊概率滿足一定值，誠實節(jié)點才會選擇發(fā)送無用數(shù)據(jù)。不論是攻擊者或者是誠實節(jié)點，哪方偏離協(xié)議后，其收益都會受到一定影響。理性參與雙方最終都不會偏離納什均衡結(jié)果，從而達到較強的安全性要求。

2.5 理性門限簽名

門限簽名是數(shù)字簽名中群體簽名的形式，也是現(xiàn)代密碼學的一種重要工具。為了使其更具有實用性，門限簽名結(jié)合博弈理論的研究使得所有的參與者都為理性的個體，無論在任何階段，理性參與者都會以最大化自己的效益為目標。理性門限簽名有效解決了單個參與者權(quán)利過于集中的問題，提高了門限簽名協(xié)議的安全性與公平性。

早在1991年，Desmedt等[49]首次提出了門限簽名方案，方案可以在不泄露任何秘密秘鑰的情況下對消息進行簽名；門限簽名是秘密共享協(xié)議在數(shù)字簽名方案中的應(yīng)用，Wang和Tian等[50]對基于博弈論的門限簽名體制進行了分析與構(gòu)造，并提出了理性秘鑰分發(fā)和理性簽名合成的解決機制；Ren等[51]提出基于社會承諾機制的理性同時生效簽名方案，利用博弈論方法解決同時生效簽名中發(fā)起方占有額外權(quán)限的不公平性問題。

門限簽名的博弈分析過程如下：

部分簽名分組轉(zhuǎn)發(fā)算法

Step1 將n位參與簽名的參與者隨機分為3個組，分別記為PA，PB和PC；

Step2 參與者PA組的成員向參與者PB組的成員廣播他們的簽名πi；

Step3 參與者PB驗證收到PA組的成員的部分簽名πi，如果驗證通過則協(xié)議繼續(xù)，否則，向n位參與者廣播Pi為惡意欺騙者，并將其剔除，重新運行n-1位參與者執(zhí)行的部分簽名分組轉(zhuǎn)發(fā)算法；

Step4 參與者PB組的成員向參與者PC組的成員廣播他們的簽名πi；

Step5 參與者PC驗證收到PB組的成員的部分簽名πi，如果驗證通過則協(xié)議繼續(xù)，否則，向n位參與者廣播Pi為惡意欺騙者，并將其剔除，重新運行n-1位參與者執(zhí)行的部分簽名分組轉(zhuǎn)發(fā)算法；

Step6 參與者PC組的成員向參與者PA組的成員廣播他們的簽名πi；

Step7 參與者PA驗證收到PC組的成員的部分簽名πi，如果驗證通過則協(xié)議繼續(xù)，否則，向n位參與者廣播Pi為惡意欺騙者，并將其剔除，重新運行n-1位參與者執(zhí)行的部分簽名分組轉(zhuǎn)發(fā)算法；

Step8 轉(zhuǎn)發(fā)協(xié)議結(jié)束。

剩余部分簽名隨機公開算法

Step1 根據(jù)部分簽名分組轉(zhuǎn)發(fā)算法中步驟1的分組情況，在此三個組PA，PB和PC中隨機選取t-3/n-1位參與者，PA中a位，PB中b位，PC中c位；

Step2 要求隨機選取的t-3/n-1位參與者同時向n位參與者廣播其子簽名；

Step3 收到子簽名后驗證其合法性，如通過驗證，則各位參與者通過拉格朗日插值多項式方法計算合成其簽名，理性門限簽名協(xié)議結(jié)束；否則，向n位參與者廣播Pi為惡意欺騙者，并將其剔除；

Step4 要求欺騙者公布其正確的子簽名；

Step5 理性參與者計算全部合理簽名，理性門限簽名協(xié)議結(jié)束。

根據(jù)以上分析，若BDH假設(shè)在協(xié)議中成立，那么理性參與者Pi博弈機制中選擇的最佳策略為合作，在協(xié)議的兩個階段都向?qū)?yīng)的理性參與者廣播其部分簽名，此時參與門限簽名的理性參與者的效益均達到最大值。

3 問題與挑戰(zhàn)

理性密碼協(xié)議的研究已經(jīng)成為當今密碼學研究領(lǐng)域的熱門，但已有的理性密碼協(xié)議因?qū)崿F(xiàn)相應(yīng)的納什均衡常常導(dǎo)致效率低下，因此理性密碼協(xié)議的相關(guān)研究還存在一些問題與挑戰(zhàn)。

3.1 存在問題

1）已有的理性密碼協(xié)議效率低下，并且理性密碼協(xié)議的優(yōu)化模型有待深入研究，在實際應(yīng)用中高效的理性密碼協(xié)議較缺乏；

2）具有公平性質(zhì)和安全性質(zhì)的理性密碼協(xié)議設(shè)計方法較復(fù)雜，缺乏理性密碼協(xié)議的安全模型和安全分析方法來設(shè)計理性公平密碼協(xié)議；

3）已有的理性密碼協(xié)議通信復(fù)雜度較高，在實際應(yīng)用中缺乏具有較低通信輪數(shù)的理性密碼協(xié)議，其輪復(fù)雜度有待進一步優(yōu)化。

3.2 面臨挑戰(zhàn)

1）對理性密碼協(xié)議效率優(yōu)化建模是理性密碼協(xié)議需要面臨的挑戰(zhàn)之一

理性密碼協(xié)議的設(shè)計過程中，為實現(xiàn)理性密碼協(xié)議的 Nash 均衡或者其他均衡，導(dǎo)致所設(shè)計的協(xié)議在實際運行中增加交互次數(shù)，這在一定程度上增加了參與者的通信開銷，從而減低了參與者的收益。在這種情況下，如何建立協(xié)議設(shè)計的優(yōu)化模型，使得參與者花費最小的“代價”實現(xiàn)相應(yīng)的理性密碼協(xié)議納什均衡結(jié)果。另外，在某些特殊的應(yīng)用領(lǐng)域，參與者更關(guān)心協(xié)議的執(zhí)行效率，如何建立這樣的優(yōu)化模型，使得犧牲較少的協(xié)議安全性質(zhì)（用戶容許的程度）而獲得協(xié)議性能的較大提高。現(xiàn)有的形式化模型或其他協(xié)議分析模型對協(xié)議的優(yōu)化缺乏支持。因此，如何對理性密碼協(xié)議優(yōu)化建模是研究理性密碼協(xié)議所要面臨的挑戰(zhàn)。

2）具有公平性的理性密碼協(xié)議的安全模型是有效實現(xiàn)公平機制設(shè)計需要面臨的挑戰(zhàn)

理性密碼協(xié)議是否滿足其期望的公平性是理性密碼協(xié)議公平機制設(shè)計和分析的目標，所以對其公平性進行正確的建模至關(guān)重要。為實現(xiàn)理性協(xié)議的公平性質(zhì)，現(xiàn)有理性密碼協(xié)議都存在公平協(xié)議的效率低下的問題，如何應(yīng)用恰當方法來進行性能優(yōu)化，是體現(xiàn)其公平機制設(shè)計方法有效性的重要方面。公平性在不同的模型下通常有不同的建模方式，例如在邏輯方法中可直接用邏輯公式來描述，在進程代數(shù)中通常用進程等價性來描述。因此，要有效設(shè)計理性密碼協(xié)議的公平機制，對具有公平性的理性密碼協(xié)議安全模型設(shè)計是研究理性密碼協(xié)議公平性所要面臨的挑戰(zhàn)。

3）構(gòu)造具有最優(yōu)通信復(fù)雜度的理性密碼協(xié)議，使理性密碼協(xié)議輪復(fù)雜度有待進一步優(yōu)化是要面臨的挑戰(zhàn)

通信輪數(shù)對協(xié)議效率的影響非常大，在理性密碼協(xié)議中更是如此。因理性計算協(xié)議為實現(xiàn)各種期望的結(jié)果（納什均衡）而導(dǎo)致協(xié)議的輪復(fù)雜度增加，極大地影響協(xié)議的可用性和效率。另一方面，在多輪協(xié)議中可能存在低效率的用戶，而其它用戶必須等待這些低效率用戶的反饋，這也會影響到整個協(xié)議的效率。因此，在理性密碼協(xié)議構(gòu)造過程中，需盡量降低協(xié)議的通信輪數(shù)，最好設(shè)計一輪或常數(shù)輪的協(xié)議。到目前為止，一輪或常數(shù)輪的理性密碼協(xié)議很難實現(xiàn)其納什均衡，各位理性參與者都不可能在這樣的機制下與對方友好合作完成協(xié)議任務(wù)。因此，具有最優(yōu)輪復(fù)雜度的理性密碼協(xié)議無論是在理論研究方面還是在實際應(yīng)用中，均是我們將要面臨的重大挑戰(zhàn)。

總之，雖然目前理性密碼協(xié)議已存在一些研究成果，但仍存在大量的具有挑戰(zhàn)性的關(guān)鍵問題需要深入研究，如理性密碼協(xié)議的安全模型問題、協(xié)議效率問題以及其通信復(fù)雜度問題等是研究理性密碼協(xié)議需要面臨的挑戰(zhàn)，因此對于理性密碼協(xié)議的研究現(xiàn)狀來說，無論是從其理論上還是實踐上都需要更深一步的探討與研究。

4 結(jié)論

理性密碼協(xié)議作為算法博弈理論的研究分支，是近些年來新興的一個研究領(lǐng)域。通過引入理性的參與者，為密碼協(xié)議的安全性和公平性提供了新的解決思路，并且在國際中也取得了迅速的發(fā)展。本文重點對理性秘密共享、理性安全多方計算、理性交換協(xié)議和理性門限簽名進行了綜述，并分析了各領(lǐng)域的研究現(xiàn)狀以及我們做的相關(guān)工作。由于理性密碼協(xié)議是新興的研究領(lǐng)域，我們對其研究與了解還比較有限，并且博弈論也結(jié)合了數(shù)學與經(jīng)濟學科，又進一步走向密碼學領(lǐng)域，可能將會為密碼學領(lǐng)域帶來一場革命。

參考文獻：

[1]JUN S， VARAIYA P. Mechanism design for networkingreseach[J]. Information Systems Frontiers， 2003， 5（1）： 29-37.

[2]HALPERN J， PASS R.Game theory with costly computation[C]. Proceedings of the Behavioral and Quantitative Game Theory： Conference on Future Directions. New York， USA： ACM， 2010： 120-142.

[3]GRADWOHL R， LIVNE N， ROSEN A. Sequential rationality in cryptographic protocols[C]. Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. New York， USA： IEEE， 2010： 623-632.

[4]FISCHER M J， WRIGHT R N. An application of game theoretic techniques to cryptography [J]. Discrete Mathematics and Theoretical Computer Science， 1993， 13：99-118.

[5]DODIS Y， HALEVI S， RABIN T.A cryptographic solution to a game theoretic problem[C]. Annual International Cryptology Conference. New York， USA： Springer Berlin Heidelberg， 2000： 112-130.

[6]BUTTYAN L， HUBAUX J P. Rational exchange-a formal model based on game theory[C]. Proceedings of the 2nd International Workshop on Electronic Commerce.New York， USA： Springer Berlin Heidelberg， 2001： 16-17.

[7]ASOKAN N， SCHUNTER M， WAIDNER M.Optimistic protocols for fair exchange[C]. Proceedings of the 4th ACM conference on Computer and Communications Security. USA： ACM， 1997： 7-17.

[8]Caballero-GilP， Henández-Goya C， Bruno-Castaeda C. A rational approach to cryptographic protocols[J]. Mathematical Computer Modelling， 2007， 46（1）：80-87.

[9]Kremer S. Game Analysis of Abuse-free Contract Signing[C]. IEEE Workshop on Computer Security Foundations. New York， USA： IEEE Computer Society， 2002：206.

[10]Sandholm T， Wang G X. （Im）possibility of safe exchange mechanism design[C]. Proceedings of National Conference on Artificial Intelligence. New York， USA： ACM， 2002： 338-344.

[11]Chadha R， Mitchell J C， Scedroy A， et al. Contract signing， optimism and advantage[M]. Marseille， France： Springer Berlin Heidelberg， 2003：366-382.

[12]Clever R. Limits on the security of coin flips when half the processors are faulty[C]. 18th Annual ACM Symposium on Theory of Computing （STOC）. New York， USA： ACM Press， 1986： 364-369.

[13]Gordon D S，Carmit H， Katz J， et al. Complete fairness in secure two-party computation[C]. Fortieth ACM Symposium on Theory of Computing. New York， USA： ACM， 2008：413-422.

[14]Gordon S D ， Katz J. Complete fairness in multi-party computation without an honest majority[C].San Francisco， CA， USA： In 6th TCC， 2009：19-35.

[15]Gordon S D， Katz J. Partial fairness in secure two-party computation [J]. Journal of Cryptology， 2012， 25（1）： 14-40.

[16]Tian Y L， Ma J F， Peng C G， et al. Secret sharing scheme with fairness[C]. IEEE TrustCom2011. Changsha： IEEE， 2011： 494-500.

[17]Groce A， Katz J. Fair Computation with Rational Players[M]. New York， USA： Springer Berlin Heidelberg， 2012：81-98.

[18]HALPEN J， TEAGUE V.Rational secret sharing and multiparty computation： extended abstract[C]. Proceedings of the 36th Annual ACM Symposium on Theory of Computing. New York， USA： ACM， 2004： 623-632.

[19]Abraham I，Dolevd D， Gonen R， et al. Distributed computing meets game theory： robust mechanisms for rational secret sharing and multiparty computation[C]. PODC 2006： Proceedings of the 25th annual ACM symposium on Principles of distributed computing. New York， USA： ACM， 2006： 53-62.

[20]Alcaide A. Rational exchange protocols[D]. Madrid： Universidad Carlos III De Madrid， 2008.

[21]田有亮， 馬建峰， 彭長根. 秘密共享體制的博弈論分析[J]. 電子學報， 2011， 39（12）： 2790-2795.

[22]Tian Y L， Ma J F， Peng C G， et al. One-time rational secret sharing scheme based on Bayesiangame[J]. Wuhan University Journal of Nature Science， 2011， 16（5）： 430-434.

[23]A. Yao. Protocols for Secure Computations [C]. Washington， DC， USA： Proc. of IEEE OGS'82， 1982：160-164.

[24]BLAKLEY G R.Safeguarding cryptographic keys[C]. Proceeding of the National Computer Conference 1979. New York， USA： IEEE Computer Society，1979：313-317.

[25]SHAMIR A. How to share asecret[J]. Communications of the ACM， 1979， 22（11）： 612-613.

[26]MALEKA S， SHAREEF A， RANGAN C P. Rational secret sharing with repeated games[C]. International Conference on Information Security Practice and Experience. Sydney， Australia： Springer Berlin Heidelberg， 2008： 334-346.

[27]ASHAROV G， LINDELL Y. Utility dependence in correct and fair rational secret sharing[C].Annual International Cryptology Conference. New York， USA： Springer Berlin Heidelberg， 2009： 559-576.

[28]MICALI S. Purely rational secret sharing[C]. Theory of Cryptography Conference.San Francisco， CA， USA： Springer Berlin Heidelberg， 2009：54-71.

[29]TIAN Y L， MA J F， PENG C G， et al. One-time rational secret sharing scheme based on Bayesiangame[J]. Wuhan University Journal of Natural Sciences， 2011， 16（5）： 430-434.

[30]彭長根， 劉海， 田有亮， 等. 混合偏好模型下的分布式理性秘密共享方案[J]. 計算機研究與發(fā)展， 2014， 51（7）：1476-1485.

[31]劉海， 彭長根， 田有亮， 等. （2， 2）貝葉斯理性秘密共享方案[J]. 電子學報， 2014， 42（12）： 2481-2488.

[32]TIAN Y L， PENG C G， LIN DD， et al. Bayesian mechanism for rational secret sharing scheme[J]. Science China Information Sciences， 2015， 58（5）： 1-13.

[33]HARN L， LIN C， LI Y. Fair secret reconstruction in （t， n） secretsharing[J]. Journal of Information Security and Applications， 2015， 23： 1-7.

[34]LYSYANSKAYA A， TRIANDOPOULOS N. Rationality and adversarial behavior in multi-party computation[C]. Annual International Cryptology Conference. Santa Barbara， California， USA：Springer Berlin Heidelberg， 2006： 180-197.

[35]GROCE A， KATZ J. Fair computation with rational players[C]. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Petersburg， Russia： Springer Berlin Heidelberg， 2012： 81-98.

[36]WALLRABENSTEIN J R， CLIFTON C. Equilibrium concepts for rational multiparty computation[C]. International Conference on Decision and Game Theory for Security. Berlin， Germany： Springer International Publishing， 2013： 226-245.

[37]WANG Y L， LIU Z， WANG H， et al. Social rational secure multi-partycomputation[J]. Concurrency and Computation Practice and Experience， 2014， 26（5）： 1067-1083.

[38]王伊蕾， 鄭志華， 王皓， 等. 滿足可計算序貫均衡的理性公平計算[J]. 計算機研究與發(fā)展， 2014， 51（07）： 1527-1537.

[39]ASOKAN N. Fairness in electronic commerce [D]. Waterloo： University of Waterloo， 1998.

[40]SYVERSON P.Weakly secret bit commitment： applications to lotteries and fair exchange[C]. The 11th IEEE Computer Security Foundations Workshop. Massachusetts： IEEE， 1998： 2-13.

[41]BUTTYAN L. Building blocks for secureservices： authenticated key transport and rational exchange protocols[D].Lausanne： Ecole Polytechnique Federale de Lausanne， 2001.

[42]丁洪. 公平交換協(xié)議的理性模型及其形式化分析[D].貴陽：貴州大學， 2016.

[43]ALCAIDE A， ESTEVEZ-TAPIADOR J M， HERNANDEE- CA-STRO J C， et al.An extended model of rational exchange based on dynamic games of imperfect information[C]. International Conference on Emerging Trends in Information and Communication Security. Freiburg， Germany： Springer-Verlag Berlin， 2006： 396-408.

[44]WONG R C W， LIJiu-yong， FU A W C， et al. （α，k） -anonymous data publishing[J]. Journal of Intelligent Information Systems， 2009，33（2）：209-234.

[45]LINing-hui， LI Tian-cheng， VENKATASUB R AMANIAN S. T-closeness： privacy beyond K-anonymity and L-diversity[C]. Proc of the 23rd International Conference on Data Engineering. Istanbul， Turkey： IEEE Press， 2007： 44-56.

[46]Gordon S D， Katz J. Rational Secret Sharing， Revisited[C].International Conference on Security and Cryptography for Networks. Amalfi， Italy： Springer Berlin Heidelberg， 2006：229-241.

[47]NGUYEN L H， Rational authentication protocols[EB/OL]. （2011）[2018-4-15].http：//eprint.iacr.org/2011/070.pdf， 2011.

[48]李興華， 鄧凌娟， 張淵，等. 基于博弈論的身份認證協(xié)議的分析——NGUYEN L H方案的改進[J]. 通信學報， 2013（8）：18-26.

[49]DESMEDT Y， FRANKEL Y.Shared generation of authenticators and signatures[J]. Advances in Cryptology. proc. Of Crypto， 1991， 576（12）：457-469.

[50]王潔， 蔡永泉， 田有亮. 基于博弈論的門限簽名體制分析與構(gòu)造[J]. 通信學報， 2015（5）：148-155.

[51]任祉靜， 彭長根， 劉海. 基于社會承諾機制的理性同時生效簽名方案及其公平性[J]. 貴州大學學報（自然科學版）， 2015， 32（2）：58-63.

（責任編輯：曾 晶）