基于博弈論的安全多方計(jì)算的研究

張興蘭，鄭煒

?

基于博弈論的安全多方計(jì)算的研究

張興蘭，鄭煒

（北京工業(yè)大學(xué)信息學(xué)部，北京 100124）

在經(jīng)典的百萬(wàn)富翁協(xié)定中，參與者其中之一獲取到財(cái)產(chǎn)大小的結(jié)論后，有可能不告訴另外一個(gè)參與者，也可以不遵守這個(gè)協(xié)議，結(jié)合博弈論可以避免這個(gè)問(wèn)題，一個(gè)參與者一定會(huì)選擇做出對(duì)自己有利的決定，因此，可以設(shè)計(jì)一個(gè)協(xié)議，遵循這個(gè)協(xié)議的參與者獲得的利益大于背離這個(gè)協(xié)議的利益。目前，基于博弈論的問(wèn)題計(jì)算效率較低，該協(xié)議通過(guò)引入一個(gè)二叉樹(shù)大大提高了計(jì)算效率。

博弈論；百萬(wàn)富翁問(wèn)題；安全多方計(jì)算；排序二叉樹(shù)

1 引言

多方安全計(jì)算指在一個(gè)參與者都不信賴(lài)彼此的環(huán)境中，每位參與者通過(guò)網(wǎng)絡(luò)共同完成各種計(jì)算任務(wù)的同時(shí)又不會(huì)泄露自己的數(shù)據(jù)[1]。這里面的安全指既能夠通過(guò)計(jì)算得到正確的結(jié)果，又不會(huì)讓別的參與者得知輸入的各種隱私信息。多方安全計(jì)算在生活中隨處可見(jiàn)，尤其是在現(xiàn)在這個(gè)互聯(lián)網(wǎng)時(shí)代，如在網(wǎng)上的拍賣(mài)會(huì)，網(wǎng)絡(luò)上的投票系統(tǒng)[2]等。

在文獻(xiàn)[3]中，Yao首先提出了百萬(wàn)富翁比較財(cái)產(chǎn)多少的問(wèn)題，在2個(gè)人不告訴對(duì)方財(cái)產(chǎn)數(shù)額的前提下，比較出誰(shuí)更有錢(qián)。在文獻(xiàn)[4,5]中，Goldreich等設(shè)計(jì)出了一個(gè)通用性高的多方安全計(jì)算協(xié)議。在文獻(xiàn)[6]中，馮登國(guó)等設(shè)計(jì)了一個(gè)有半誠(chéng)實(shí)第三方的兩方安全比較協(xié)議。在文獻(xiàn)[7]中，李順東等運(yùn)用不經(jīng)意傳輸協(xié)議，設(shè)計(jì)出了一種有效的兩方安全比較協(xié)議。在文獻(xiàn)[8,9]中，作者利用半誠(chéng)實(shí)的模型，分別對(duì)數(shù)據(jù)庫(kù)中的隱私數(shù)據(jù)和網(wǎng)絡(luò)空間中認(rèn)證的策略進(jìn)行了深入的理論研究。綜上可知，當(dāng)前很多研究運(yùn)用都是的半可信模型。文獻(xiàn)[10]設(shè)計(jì)出了一個(gè)實(shí)際應(yīng)用具有局限性的多方計(jì)算方案。所以，大多數(shù)人所設(shè)計(jì)的協(xié)議都有一些片面，因?yàn)橐粋€(gè)參與者曾經(jīng)也許沒(méi)有背叛過(guò)協(xié)議，但是當(dāng)他能夠獲得非常大的利益時(shí)，也許他就不會(huì)像曾經(jīng)那樣嚴(yán)格遵守協(xié)議了。因此，不從利益的角度考慮是片面的。

借助博弈論思想，可以實(shí)現(xiàn)在傳統(tǒng)的協(xié)議中很難實(shí)現(xiàn)的公平性。文獻(xiàn)[11]提出了一個(gè)思想，當(dāng)人們無(wú)法預(yù)測(cè)何時(shí)得到計(jì)算結(jié)果時(shí)，他們會(huì)非常樂(lè)于去遵循協(xié)議。Naor等[12]為了使參與者嚴(yán)格地遵守協(xié)議的約定，引入了博弈論的相關(guān)概念。但該方案設(shè)計(jì)比較復(fù)雜。在文獻(xiàn)[13]中，Amjed設(shè)計(jì)了一個(gè)引入博弈論的方案，但是這個(gè)方案要求生成的多項(xiàng)式的冪次數(shù)之間的差值必須不大于1，具有局限性。文獻(xiàn)[14,15]需要在使用的時(shí)候提供一些物理性的材料，如信件等，不利于應(yīng)用。在文獻(xiàn)[16]中，同時(shí)考慮了善意的參與者和具有攻擊性的參與者，在這個(gè)基礎(chǔ)上，設(shè)計(jì)出了一種新的理性安全多方計(jì)算的方案。

在傳統(tǒng)密碼協(xié)議中，一般會(huì)從具有攻擊性的參與者和誠(chéng)實(shí)參與者2個(gè)角度設(shè)計(jì)協(xié)議，這樣是不夠全面的，因?yàn)槔嬉矔?huì)影響參與者的行為，因此博弈論的思想在信息安全上越來(lái)越重要。現(xiàn)階段，已經(jīng)有很多結(jié)合了博弈論思想的方案。

當(dāng)前，已經(jīng)有安全計(jì)算協(xié)議與博弈論結(jié)合的模型。但是參數(shù)過(guò)于簡(jiǎn)單單一，只考慮了參與者攻擊成功與否所獲得的收益，并沒(méi)有考慮攻擊所要耗費(fèi)的各種代價(jià)，而且在所設(shè)計(jì)的密碼協(xié)議中需要進(jìn)行多輪計(jì)算，計(jì)算效率很低，因此分析不具有全面性和一般性，計(jì)算繁瑣。

本文引入多個(gè)參數(shù)，從多個(gè)角度考慮，構(gòu)建一個(gè)具有一般性和全面性的博弈模型，在此基礎(chǔ)上，引入一個(gè)二叉樹(shù)在不暴露參與者信息的同時(shí)簡(jiǎn)化計(jì)算過(guò)程，提高運(yùn)算效率。

2 背景知識(shí)及博弈模型分析

2.1 背景知識(shí)

排序二叉樹(shù)：一種具有特殊性質(zhì)的二叉樹(shù)，它擁有如下特質(zhì)。

1) 當(dāng)左子樹(shù)不是空的時(shí)候，左子樹(shù)上的所有值都會(huì)小于該左子樹(shù)的根節(jié)點(diǎn)的值。

2) 當(dāng)右子樹(shù)不是空的時(shí)候，右子樹(shù)上的所有值都會(huì)大于該右子樹(shù)的根節(jié)點(diǎn)的值。

3) 這個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)也都是排序二叉樹(shù)，具有上述特質(zhì)。

公平性：在進(jìn)行安全兩方計(jì)算時(shí)，如果其中的參與者都成功地得到了計(jì)算結(jié)果，或者全都沒(méi)有成功地獲得計(jì)算結(jié)果，那么這個(gè)協(xié)議就是公平的。

博弈論：其主要目的是為了深入研究參與者之間在存在利益沖突的情況下，根據(jù)對(duì)方所做出決定的不同而做出不同的決定，理性的參與者總是會(huì)做出最優(yōu)的決定。

納什均衡：當(dāng)參與者之間在相互對(duì)抗相互依存的時(shí)候，形成各個(gè)參與者的當(dāng)前選擇都是最優(yōu)選擇時(shí)的一種穩(wěn)定狀態(tài)。

左0右1編碼：是指從根節(jié)點(diǎn)開(kāi)始，如果要編碼的節(jié)點(diǎn)在根節(jié)點(diǎn)左子樹(shù)上，則記下一個(gè)0，如果在根節(jié)點(diǎn)的右子樹(shù)上，則記下一個(gè)1，然后進(jìn)入要編碼節(jié)點(diǎn)所在的子樹(shù)，進(jìn)行上述過(guò)程，直到子樹(shù)就是該節(jié)點(diǎn)自己，按先后順序組合成只含有0和1的序列，這個(gè)序列就是該節(jié)點(diǎn)的編碼。

2.2 博弈模型分析

在本文所設(shè)計(jì)的模型中，讓不執(zhí)行協(xié)議的參與者或者計(jì)劃猜測(cè)正確值的參與者能得到的利益非常小，遠(yuǎn)小于一個(gè)善意的并且積極遵守協(xié)議的參與者的利益。其主要思想在于以一定概率傳輸無(wú)用數(shù)據(jù)來(lái)混淆能夠判斷出比較結(jié)果的核心元素。

如果攻擊者想要發(fā)起攻擊行為，從3個(gè)角度進(jìn)行考慮。

3) 參與者并沒(méi)有發(fā)起任何攻擊，他會(huì)得到作為回報(bào)。

根據(jù)情況分析，>>。

之前在設(shè)計(jì)博弈論模型的時(shí)候，一般只考慮攻擊者發(fā)起攻擊所得到的利益，從而忽略了惡意攻擊者在進(jìn)行攻擊的時(shí)候，準(zhǔn)備階段的人力物力以及攻擊階段的計(jì)算耗費(fèi)等消耗，但往往在實(shí)際生活中，具有惡意的攻擊者也會(huì)將攻擊成本作為一個(gè)重要的參考，因此以往的博弈論模型考慮的并不全面。

本文從兩名參與者相互博弈的角度考慮，全面引入了協(xié)議參與者不同情況下所獲得的利益。

表1 博弈模型

不具有惡意的參與者在發(fā)送數(shù)據(jù)時(shí)因?yàn)榛烊肓舜罅繜o(wú)效值，成功將真實(shí)值隱藏在其中，導(dǎo)致惡意的參與者無(wú)法獲知其中哪一個(gè)是真實(shí)值，所以很大程度上提高了這個(gè)協(xié)議傳輸時(shí)的安全性，因此將這樣獲得的收益設(shè)為U。但是，如果惡意參與者在此時(shí)沒(méi)有去攻擊，這種收益是不存在的。這時(shí)，不具有惡意的參與者不會(huì)有這個(gè)U收益。

證明 博弈模型的支付矩陣，攻擊者選擇不攻擊的收益為。

當(dāng)一個(gè)惡意參與者發(fā)現(xiàn)對(duì)協(xié)議進(jìn)行攻擊去獲取真實(shí)值節(jié)點(diǎn)時(shí)所要花費(fèi)的代價(jià)大于獲取真實(shí)值后的收益，那么從理性的角度考慮，其不會(huì)發(fā)動(dòng)攻擊，從而有

化簡(jiǎn)可得

3 理性的安全兩方計(jì)算協(xié)議

本文給出一個(gè)具有兩名參與者的計(jì)算協(xié)議，參與者都是具有理性的，他們會(huì)根據(jù)利益大小去做出能讓自己利益最大化的決定，也就是說(shuō)，都可以試圖猜測(cè)或推算其他參與者的真實(shí)值，不履行協(xié)議，以達(dá)到在不讓對(duì)方知道大小的情況下自己先知道大小。

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

輸入 令和是Alice、Bob的私有輸入值。在協(xié)議進(jìn)行過(guò)程中，和的值并不會(huì)被外界以及對(duì)方知曉。

構(gòu)成排序二叉樹(shù)Atree后，對(duì)樹(shù)中的進(jìn)行左0右1的編碼。例如，在圖1中，如果在51的位置，那么編碼為001；如果在93的位置，那么編碼為110；Alice記下所在位置的編碼AtreeCode。

圖1 二叉排序樹(shù)

Bob對(duì)自己的隨機(jī)序列B1，B2，B3，…，，…，B?1，B做相同的準(zhǔn)備，構(gòu)成排序二叉樹(shù)BTree記下自己的所在位置的編碼BTreeCode。

3.2 數(shù)據(jù)交互計(jì)算階段

1) Alice將自己的二叉排序樹(shù)ATree上的元素按照從上到下、從左到右的順序發(fā)送給Bob，Bob收到所有元素后，還原成ATree樹(shù)，將自己的值添加到ATree中，并進(jìn)行左0右1的編碼，得到值所在位置的編碼ATreeCode。

2) Bob將自己的二叉排序樹(shù)BTree上的元素按照從上到下從左到右的順序發(fā)送給Alice，Alice收到所有元素后，還原成BTree樹(shù)，將自己的值添加到BTree中，并進(jìn)行左0右1的編碼，得到值所在位置的編碼BTreeCode。

3) Alice將BTreeCode編碼發(fā)送給Bob，同時(shí)，Bob將ATreeCode編碼發(fā)送給Alice。Alice通過(guò)ATreeCode編碼結(jié)合自己的ATree樹(shù)能夠判斷出和的值的大小。例如，Bob發(fā)送的ATreeCode編碼是1100，而Alice自己的編碼ATreecode編碼為0100，可從第一位上判斷出在左子樹(shù)，在右子樹(shù)，因此必然大于，從而判斷出大小。Bob同理可以得出結(jié)論。

4 協(xié)議分析

4.1 時(shí)間復(fù)雜度和計(jì)算復(fù)雜度

本協(xié)議在數(shù)據(jù)交互階段僅需要進(jìn)行一輪交互，時(shí)間復(fù)雜度較低。同時(shí)，在對(duì)排序二叉樹(shù)進(jìn)行左0右1的編碼時(shí)計(jì)算簡(jiǎn)單，便于操作。

4.2 公平性

從數(shù)據(jù)交互階段可以看出，Alice和Bob都不會(huì)從步驟3)前的數(shù)據(jù)準(zhǔn)備和數(shù)據(jù)交互階段中提前得到大小的信息，只有Alice和Bob在步驟3)中同時(shí)發(fā)送數(shù)據(jù)后，彼此才能獲得大小的信息。可見(jiàn)，Alice和Bob要么都能成功獲得正確的計(jì)算數(shù)據(jù)，要么都不能成功獲得正確的計(jì)算數(shù)據(jù)，保證了協(xié)議的公平性。

4.3 安全性

本文可以保證Alice和Bob兩方在比較和大小的同時(shí)不會(huì)獲取到和的值。考慮到協(xié)議具有對(duì)稱(chēng)性交互這一特點(diǎn)，只需要從其中一個(gè)參與者進(jìn)行分析即可，因此從Alice的角度進(jìn)行分析。Alice有2次從Bob處得到信息。

1) 在協(xié)議的數(shù)據(jù)交互階段的步驟2)中，Alice從Bob處得到BTree，BTree是含有多個(gè)隨機(jī)元素的排序二叉樹(shù)，Alice想從中獲取到Bob的秘密輸入只能通過(guò)猜測(cè)，而Alice結(jié)合自身利益并沒(méi)有通過(guò)猜測(cè)而不去履行協(xié)議的動(dòng)機(jī)（定義2），因此Alice并不能獲得Bob的秘密輸入。

2) 協(xié)議的數(shù)據(jù)交互階段的步驟2)中，Alice從Bob處得到了ATree編碼，僅通過(guò)編碼Alice并不能得到Bob的真實(shí)秘密輸入值。

由上面的說(shuō)明可知，Alice并不會(huì)從數(shù)據(jù)交互中獲取到Bob的任何隱私性的信息。Bob同理。

4.4 正確性

同樣，從Alice的角度考慮。Alice得到BTree后，把自己的值添加到BTree上構(gòu)成新的排序二叉樹(shù)，然后對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行左0右1編碼得到BTreeCode，然后將BTreeCode編碼告訴Bob，這樣Bob就能通過(guò)Alice給出的編碼及自己的BTree排序二叉樹(shù)確定出節(jié)點(diǎn)在樹(shù)中的位置，由于排序二叉樹(shù)的性質(zhì)，Bob再結(jié)合BTree中自己的值的位置，就能判斷出和的大小。

4.5 納什均衡

在協(xié)議的第一部分?jǐn)?shù)據(jù)準(zhǔn)備階段（3.1節(jié)），各個(gè)參與者都是單獨(dú)進(jìn)行數(shù)據(jù)準(zhǔn)備，所以不會(huì)打破公平性。在數(shù)據(jù)交互階段，交互前雙方自己并不知道比較的結(jié)果，要想知道比較的結(jié)果，都依賴(lài)于對(duì)方發(fā)送的編碼。而不履行協(xié)議單獨(dú)去猜測(cè)編碼又不符合理性參與者自身的利益，故在數(shù)據(jù)交互的整個(gè)過(guò)程中，如果參與者出現(xiàn)背叛而不履行協(xié)議或者不發(fā)送最后的編碼，均不能增加收益，因此協(xié)議雙方的最佳策略是相互合作，即所有參與者都能得到結(jié)果。

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

從博弈論的角度考慮，對(duì)傳統(tǒng)的多方安全計(jì)算協(xié)議進(jìn)行了分析，發(fā)現(xiàn)傳統(tǒng)的安全多方計(jì)算協(xié)議一般要經(jīng)過(guò)多輪的復(fù)雜計(jì)算，實(shí)際效率很低，將其與生活實(shí)際相結(jié)合時(shí)成本很高，并且很多多方安全計(jì)算協(xié)議在設(shè)計(jì)的時(shí)候只從惡意參與者和非惡意參與者2個(gè)角度考慮，而忽略了當(dāng)利益巨大的時(shí)候，即便是非惡意的參與者也會(huì)具有攻擊傾向；當(dāng)攻擊成本昂貴，甚至超過(guò)攻擊所能獲得的利益時(shí)，即便是惡意參與者，也很有可能放棄攻擊。通過(guò)引入二叉排序樹(shù)，大大簡(jiǎn)化了運(yùn)算的復(fù)雜性，使參與者只有極少的交互便實(shí)現(xiàn)了比較大小的目的，并且協(xié)議的參與者能夠正確、安全、公平地得到計(jì)算結(jié)果。

[1] GOLDREICH O. Secure multi-party computation[EB/OL]. http:// theory.lcs.mit.edu/.

[2] CRAMER R. Introduction to secure computation[M]//Lectures on Data Security. Berlin Heidelberg: Springer. 1999:16-62.

[3] YAO A C. Protocols for secure computation[C]//The 23rd IEEE Symposium on Foundations of Computer Science(FOCS 1982). 1982:160-164.

[4] GOLDREICH O, MICALI S, WIGDERSON A. How to play any mental game[C]//The 19th Annual ACM Symposium on Theory of Computing(STOC 1987). 1987:218-229.

[5] GOLDREICH O. Foundations of cryptography: basic application[M]. Cambridge: Cambridge University Press, 2004.

[6] QIN J, ZHANG Z F, FENG D G, et al. A protocol of comparing information without leaking[J]. Journal of Software, 2004, 15(3): 421-427.

[7] LI S D, DAI Y Q, YOU Q Y. An efficient solution to Yao’s millionaires’problem[J]. Acta Electronica Sinica, 2005, 33(5): 769-773.

[8] ZHOU S G, LI F, TAO Y F, et al. Privacy preservation in database applications: a survey[J]. Chinese Journal of Computers, 2009, 32(5): 847-861.

[9] ZHANG F, CHANG H Y. Privacy-preserving qutlier detection with oblivious third party[J]. Journal of Computer Research and Development, 2007, 44(S): 226-231.

[10] GORDON D, HAZAY C, KATZ J, et al. Complete fairness in secure two-party computation[C]//The 40th Annual ACM Symposium on Theory of Computing (STOC 2008). 2008: 413-422.

[11] HALPERN J,TEAGUE V. Rational secret sharing and multiparty computation[C]//The 36th Annual ACM Symposium on Theory of Computing(STOC 2004). 2004: 623-632.

[12] KOL G, NAOR M. Cryptography and game theory: designing protocols for exchanging information[C]//The 5th Theory of Cryptography Conf (TCC 2008). 2008: 317-336.

[13] MALEKA S,AMJED S,RANGAN C P. The deterministic protocol for rational secret sharing[C]//The 22th IEEE International Parallel and Distributed Processing. 2008: 1-7.

[14] IZMALKOV S,MICALI S,LEPINSKI M. Rational secure computation and ideal mechanism design[C]//The 46th Annual Symposium on Foundations of Computer Science (FOCS 2005). 2005: 585-595.

[15] FUCHSBAUER G, KATZ J, NACCACHE D. Eficient rational secret sharing in the standard communication networks[C]//Theory of Cryptography Conf (TCC 2010). 2010: 419-436.

[16] ASHAROV G, LINDELL Y. Utility dependence in correct and fair rational secret sharing[J].Journal of Cryptology, 2011, 24(1): 157-202.

Research on security multi-party computing based on game theory

ZHANG Xinglan, ZHENG Wei

Department of Information Science, Beijing University of Technology, Beijing 100124, China

In the classic millionaire agreement, one party can get the final wealth comparison results, you can not tell the other party, you can not comply with this agreement, combined with game theory can avoid this problem, you can make the participants away from the agreement proceeds less than compliance with the agreement, compliance with the agreement is the optimal strategy for the participant. At present, the problem of computational efficiency based on game theory is low, and the protocol greatly improves the computational efficiency by introducing a binary tree.

game theory, millionaire problem, secure multi-party computation, binary sort tree

TP309

A

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

張興蘭（1970-），女，山西呂梁人，博士，北京工業(yè)大學(xué)教授，主要研究方向?yàn)槊艽a學(xué)和安全協(xié)議。

鄭煒（1989-），男，河北石家莊人，北京工業(yè)大學(xué)碩士生，主要研究方向?yàn)槊艽a學(xué)、博弈論及安全多方計(jì)算。

2017-10-22；

2017-12-09

鄭煒，sj.bill@qq.com

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.10007016201201）

The National Natural Science Foundation of China (No.10007016201201)