混合策略下的理性交換協(xié)議模型

丁洪，彭長根，鄺青青

（1. 貴州大學理學院，貴州 貴陽 550025；2. 貴州大學密碼學與數(shù)據(jù)安全研究所，貴州 貴陽550025）

混合策略下的理性交換協(xié)議模型

丁洪1，2，彭長根1，2，鄺青青1，2

（1. 貴州大學理學院，貴州 貴陽 550025；2. 貴州大學密碼學與數(shù)據(jù)安全研究所，貴州 貴陽550025）

在小額支付的交換協(xié)議中，通過TTP保證協(xié)議公平性所需代價往往高于協(xié)議本身價值，在這種情況下，理性交換協(xié)議是一種合適的選擇。應用擴展式博弈混合策略理論對交換協(xié)議進行了建模，引入熵函數(shù)對交換過程中的公平性進行了描述；在保證過程公平性原則的前提下，運用混合策略納什均衡概念形式化定義了理性公平性，并在此模型基礎上構造了一個新的理性交換協(xié)議；對協(xié)議的可追究性、理性公平性進行了證明，結果表明該協(xié)議能達到混合策略納什均衡。該協(xié)議無須可信第三方，實現(xiàn)了理性公平性并對懲罰值進行了優(yōu)化，具有更好的適應性。

理性交換協(xié)議；混合策略；過程公平；納什均衡

中文分類號：TP309

1　引言

交換協(xié)議被廣泛應用在電子合同簽署、電子郵件認證和網絡支付服務等領域，如何保證交換過程中各方參與者的公平性是交換協(xié)議的一個重要問題，目前，主要依賴于公平交換原則和理性交換原則來解決。傳統(tǒng)的公平交換協(xié)議通常以可信第三方（TTP，trusted third party）或復雜的通信為代價來保證公平性的實現(xiàn)，可信第三方容易成為瓶頸。理性交換不需要可信第三方，在實現(xiàn)理性公平性的同時提高了效率，因此理性交換逐漸成為研究熱點。在微支付協(xié)議中，保證強公平性的代價往往高于支付協(xié)議本身的價值，從而強公平性不再適用于這類協(xié)議，而理性交換能提供更合適的解決方法。

1998年，Asokan［1］首次將博弈論應用到公平交換協(xié)議的分析設計中，同年 Syverson［2］首次提出了理性交換的概念，即在交換過程中，參與者的不誠實行為可能會對其他參與者的利益造成損失，但是參與者不會因不誠實行為而獲利。換言之，理性交換不能夠完全保證公平性，但理性參與者沒有理由偏離協(xié)議。2001年，Buttyan等［3］運用博弈論的方法給出了公平性的形式化定義，基于擴展式博弈對交換協(xié)議進行了建模并對Syverson協(xié)議進行了分析。針對Syverson協(xié)議中的不足，Alcaide等［4～6］應用不完全信息動態(tài)博弈理論，在交換協(xié)議中引入信念，建立了貝葉斯博弈下的理性交換協(xié)議模型，使理性交換更加符合現(xiàn)實應用環(huán)境。在文獻［7］中，作者基于極大熵原理設計了一個新的理性交換協(xié)議，并對協(xié)議的安全性和公平性進行了證明。上述研究成果都只對交換協(xié)議的結果公平性進行了討論，并未涉及過程公平性的分析。而本文考慮用信息論中的熵理論［8］對過程公平性進行描述，并探討過程公平原則下的理性公平性。

本文應用擴展式博弈下的混合策略［9］對理性交換協(xié)議進行建模，給出此模型下的混合策略納什均衡定義；通過引入熵理論對過程公平性進行描述，給出過程公平性的定義；在過程公平性原則下，利用博弈樹對整個交換過程進行分析并給出協(xié)議的可追究性［10］、理性公平性的證明。結果表明該協(xié)議能達到混合策略納什均衡。協(xié)議交換過程無須可信第三方，該協(xié)議實現(xiàn)了理性公平性并對懲罰值進行了優(yōu)化，具有更好的適應性。

2　理性交換協(xié)議的混合策略模型

博弈論是研究決策問題的理論。在博弈過程中，參與者會極力猜測對方如何選擇，同時又不想讓對方猜到自己的選擇，在這樣的情況下，參與者往往會隨機選擇自己的策略?；旌喜呗越忉屃艘粋€參與者對其他參與者所采取行動的不確定性，它描述了參與者在給定信息下以某種概率分布隨機地選擇不同的行動或策略?？梢酝ㄟ^引用熵對這樣的不確定性進行描述。

在小額支付協(xié)議中，選擇可信第三方來保證公平性所需的代價往往高于支付協(xié)議本身。在這種情況下，理性交換協(xié)議是一種合適的選擇。而協(xié)議參與者進行信息交互的過程可以看作一個混合策略擴展式博弈過程，因此可以利用混合策略擴展式博弈理論對其進行建模。

2.1基礎知識

1）混合策略

4）混合策略Nash均衡

2.2混合策略下的交換協(xié)議模型

下面將一個交換協(xié)議記為π，其執(zhí)行的過程看作一個混合策略擴展式博弈進行的過程，則可以將交換協(xié)議描述為與擴展式博弈類似的七元組其中各元素的含義如下。

1）T：參與者集合。

4）P：參與者函數(shù)，用于計算非終點行動序列的下一個參與者。表示為對于任意非終點行動序列表示非終點行動序列q后的下一個參與者。

在對收益值進行計算的過程中，加入一個懲罰函數(shù) F。在協(xié)議執(zhí)行的每一輪中，只要參與者采取某種不誠實行為，就在他的收益值上減去相應的懲罰函數(shù)。在計算最終收益時將每一輪的懲罰值都算入收益結果中。

2.3混合策略下的理性公平性

定義3過程公平性原則。在協(xié)議執(zhí)行過程中，若每個參與者在每個自己的可選行動集上的策略熵函數(shù)相等，即則該交換協(xié)議是過程公平的。

定義4混合策略Nash均衡。將有2個參與者的交換協(xié)議記為π′，將交換協(xié)議看為一個博弈，2個參與者分別為A和B，參與者的混合策略集分別記為若一個交換協(xié)議是混合策略Nash均衡公平的，則其存在一個混合策略組合滿足

定義 5若一個交換協(xié)議在保證過程公平的前提下，能滿足混合策略Nash均衡公平性，則稱該協(xié)議為一個理性交換協(xié)議。

3　一種新的理性交換協(xié)議

3.1理性交換協(xié)議的構造

在以上的混合策略博弈模型的基礎上，構建一個新的理性交換協(xié)議。假設進行通信的網絡是可靠的，使用的加密方法是安全的，在保證過程公平的基礎上，通過對收益函數(shù)進行調整，最終達到混合策略Nash均衡點，從而實現(xiàn)理性公平交換。

協(xié)議中有2個參與者A、B，A是商家，B是顧客。他們要交換的物品分別為假設他們用于交換的物品是等價的，即若協(xié)議正常執(zhí)行，則參與者A、B的收益均為0。協(xié)議中用到弱秘密承諾函數(shù)（）w k，在一定的時間內，該函數(shù)無法破解。構造的協(xié)議如圖1所示。

圖1　理性交換協(xié)議交互過程

步驟2參與者B能觀察到參與者A選擇發(fā)送消息的概率分布，為了保證過程公平性，B采取與A相同的概率分布選擇自己要發(fā)送的消息。假設參與者B是誠實且理性的，他可以選擇發(fā)送的信息為

3.2理性交換協(xié)議的分析

下面從正確性、可追究性、公平性的角度對以上的理性交換協(xié)議進行分析。首先，分析了在混合策略下該理性交換協(xié)議的正確性；其次，用 Kailar邏輯對該協(xié)議進行了可追究性分析；最后，在過程公平性的原則下，基于博弈樹對整個協(xié)議過程進行了描述，探尋了其混合策略Nsah均衡的存在性。

1）正確性

定理 1當交換協(xié)議正常執(zhí)行完畢時，若協(xié)議主體A和B分別能夠獲得所交換的物品和，則上述基于混合策略下的理性交換協(xié)議是正確的。

證明通過協(xié)議的執(zhí)行過程，可以看到，當協(xié)議完成后，參與者A能夠獲得消息并且 A可以利用自己的私鑰通過解密算法獲得經過一定的時間后，通過弱秘密承諾函數(shù)得到從而通過計算得到想要交換的商品

綜上，當協(xié)議正常執(zhí)行完畢時，各方參與者都能得到自己想要交換的商品itemA、itemB，即該混合策略下的理性交換協(xié)議是正確的。

2）可追究性

可追究性要求任何交易方必須為自己的行為負責，Kailar邏輯是專門針對電子商務可追究性進行分析的邏輯。其有如下基本原理。

用Kailar邏輯對上述協(xié)議進行形式化分析，若協(xié)議能滿足一定的目標，則說明該協(xié)議在Kailar邏輯下滿足可追究性。

定理 2在給定的初始狀態(tài)假設下，該協(xié)議在Kailar邏輯下具有可追究性。

證明根據(jù)Kailar邏輯的定義，該協(xié)議保證可追究性必須滿足的目標如下。

對于協(xié)議目標的推導有關的部分語句解釋如下。

引入如下初始狀態(tài)假設。

根據(jù)上述假設，利用Kailar邏輯進行如下推理。

當B收到消息①時，可得

由假設A3和簽名原理得

再由假設A5和推斷原理得

即滿足G2。

當A收到消息②時，可得

由假設A1和簽名原理得

在由假設A4和連結原理得

最后，由假設A6和推斷原理得

即滿足G1。

同理可證目標G3、G4能被滿足。

因此，該協(xié)議在Kailar邏輯下具有可追究性。

3）公平性

根據(jù)上述建立的模型，利用博弈樹對整個協(xié)議過程進行描述，如圖2所示。

第二輪由參與者B開始選擇行動。參與者B不能夠區(qū)分A發(fā)送的消息是還是但是，B能夠觀察到A在可選行動集上的概率分布。此時參與者B的信息集為了達到過程公平，即參與者B不想讓參與者A通過自己的行動推測到更多的信息，B選擇以和A相同的概率分布選擇自己的行動。此時在上的混合策略為，混合策略熵函數(shù)若參與者B選擇行動，則博弈終止；若B選擇第二輪結束進入第三輪，雙方受益待定。

下面分析此交換協(xié)議的公平性。在博弈過程中，每個參與者會極力猜測對方如何選擇，同時又不能讓對方猜到自己的選擇，為了使對方猜不透自己的選擇，會隨機選擇自己的策略，即以一定的概率分布去選擇自己的策略。通過分析，可以知道如下信息。

參與者A的純策略集為

相應的混合策略為

參與者B的純策略集為

相應的混合策略為

則可以得到如圖3所示的收益矩陣。

圖2　交換協(xié)議的博弈樹描述

圖3　收益矩陣

下面討論在什么條件下混合策略組合

為混合策略Nash均衡。

在過程公平的原則下，為了保證每一輪中的混合策略熵函數(shù)不變，假設θ=α=β。所以，參與者 A在混合策略組合下的期望收益為

當參與者B選擇混合策略σB時，A選擇各個純策略的期望收益為

同理，可以對參與者B在混合策略

下的期望收益進行討論。

當參與者 A選擇混合策略σA時，參與者 B選擇純策略m2、quitB的期望收益為

通過以上分析可以看到，在所構造的新的理性交換協(xié)議中，懲罰值并非越大越好。參與者遵守協(xié)議的概率與懲罰值和交換物品本身的價值之比有關。在這樣的情況下，可以通過對懲罰值的設定控制參與者遵守協(xié)議的概率分布，從而更好地促使參與者遵守協(xié)議。

3.3實例分析

表1　成本與選擇概率之間的關系

可以看到，隨著商家給出折扣的升高，顧客B在得到實惠的同時，所面臨風險的不確定度也在增大。此時商家的報價越接近商品的實際價值，則協(xié)議正常執(zhí)行的概率就越大。而這時若隨意改動懲罰值，則有可能找不到滿足條件的θ。那么，原有的協(xié)議博弈在沒有均衡解的情況下，很難保證協(xié)議的正常進行。而對于懲罰值的設定，并非越高越好。在所提出的模型中，過高的懲罰值反而會降低θ最大值的取值，讓商家望而卻步，從而降低了商家誠信參與協(xié)議的概率。

4　結束語

本文在假設加密方法安全、網絡通道可靠的前提下，引入熵理論對協(xié)議交換過程中的不確定性進行描述，進而給出過程公平的定義，并在保證過程公平的原則下，應用擴展式博弈下的混合策略理論對理性交換協(xié)議進行建模。結合所建模型和博弈論中混合策略Nash均衡的定義，本文對理性交換協(xié)議做了形式化的定義，并構造了一個新的理性交換協(xié)議。而當網絡不一定可靠以及過程不一定嚴格公平時，如何建立一個基于擴展博弈的協(xié)議博弈模型，在這樣的模型中交換協(xié)議是否依然滿足理性公平將是進一步研究的方向。

［1］ASOKAN N. Fairness in electronic commerce［D］. Waterloo：University of Waterloo，1998.

［2］SYVERSON P. Weakly secret bit commitment：applications to lotteries and fair exchange［C］//The 11th IEEE Computer Security Foundations Workshop. c1998：2-13.

［3］BUTTYAN L. Building blocks for secure services：authenticated key transport and rational exchange protocols［D］. Lausanne：Ecole Polytechnique Federale de Lausanne，2001.

［4］ALCAIDE A，ESTEVEZ-TAPIADOR J M，HERNANDEECASTRO 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. c2006：396-408.

［5］ALCAIDE A. Rational exchange protocols［D］. Leganés：Universidad Carlos III de Madrid，2008.

［6］ESTEVEZ-JAPIADOR J M，ALCAIDE A，HERMANDEZCASTRO J C，et al. Bayesian rational exchange［J］. International Journal of Network Security，2008，7（1）：85-100.

［7］呂楨，彭長根，劉海. 基于極大熵原理的理性公平交換協(xié)議［J］.計算機應用研究，2014，31（2）：563-567. LV Z，PENG C G，LIU H. Rational fairness exchange protocols based on maximum entropy principle［J］. Application Research of Computers，2014，31（2）：563-567.

［8］陳運. 信息論與編碼［M］. 北京：電子工業(yè)出版社，2007. CHEN Y.Information theory and coding［M］. Beijing：Publishing House of Electronics Industry，2007.

［9］朱·弗登博格，讓·梯若兒. 博弈論［M］. 黃濤，譯. 北京：中國人民大學出版社，2010. FUDENBERG D，TIROLE J. Game theory［M］. Translated by HUANG T. Beijing：China Renmin University Press，2010.

［10］王可心，韓芳溪. Kailar邏輯推理中初始狀態(tài)假設［J］. 大連理工大學學報，2003，43（1）：193-196. WANG K X，HAN F X. Initial state assumptions in Kailar logic reasoning［J］. Journal of Dalian University of Technology，2003，43（1）：193-196.

Rational exchange protocol model based on mixed strategy

DING Hong1，2，PENG Chang-gen1，2，KUANG Qing-qing1，2

（1. College of Science，Guizhou University，Guiyang 550025，China；2. Institute of Cryptography & Data Security，Guizhou University，Guiyang 550025，China）

In the exchange of micropayment protocol，the cost of ensuring fairness by TTP is higher than the value of protocol，in this case the rational exchange protocol is a appropriate choice. Exchange protocol was modeled by extensive mixed strategy game and the entropy function was introduced to discuss the fairness in the process of exchange. In addition，the rational fairness was formally defined by using the concept of mixed strategy Nash equilibrium under the principle of the fairness in the process，and on the basis of this model to construct a new rational exchange protolcol. The protocol's accountability and rational fairness were proved，the results show that the proposed protocol can achieve mixed stratrgy Nash equilibrium. Without the participation of the trusted third party，the protocol can achieve rational fairness and optimize the penalty values，it is beautifully adapted to the real environment.

rational exchange protocol，mixed strategy，process fairness，Nash equilibrium

A

10.11959/j.issn.2096-109x.2016.00016

2015-11-11；

2016-01-09。通信作者：彭長根，peng_stud@163.com

國家自然科學基金資助項目（No.61262073）；全國統(tǒng)計科學研究計劃基金資助項目（No.2013LZ46）；貴州省統(tǒng)計科學研究課題基金資助項目（No.201511）

Foundation Items：The National Natural Science Foundation of China（No.61262073），The National Statistical Scientific Research Project（No.2013LZ46），The Guizhou Provincial Statistical Science Research Project（No.201511）

丁洪（1991-），女，貴州安順人，貴州大學碩士生，主要研究方向為密碼學理論與工程。

彭長根（1963-），男，侗族，貴州錦屏人，博士，貴州大學教授、博士生導師，主要研究方向為密碼學、信息安全。

鄺青青（1988-），男，貴州安順人，貴州大學碩士生，主要研究方向為密碼學理論與工程。