基于博弈論的安全多方計算的研究

張興蘭，鄭煒

?

基于博弈論的安全多方計算的研究

張興蘭，鄭煒

（北京工業大學信息學部，北京 100124）

在經典的百萬富翁協定中，參與者其中之一獲取到財產大小的結論后，有可能不告訴另外一個參與者，也可以不遵守這個協議，結合博弈論可以避免這個問題，一個參與者一定會選擇做出對自己有利的決定，因此，可以設計一個協議，遵循這個協議的參與者獲得的利益大于背離這個協議的利益。目前，基于博弈論的問題計算效率較低，該協議通過引入一個二叉樹大大提高了計算效率。

博弈論；百萬富翁問題；安全多方計算；排序二叉樹

1 引言

多方安全計算指在一個參與者都不信賴彼此的環境中，每位參與者通過網絡共同完成各種計算任務的同時又不會泄露自己的數據[1]。這里面的安全指既能夠通過計算得到正確的結果，又不會讓別的參與者得知輸入的各種隱私信息。多方安全計算在生活中隨處可見，尤其是在現在這個互聯網時代，如在網上的拍賣會，網絡上的投票系統[2]等。

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

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

在傳統密碼協議中，一般會從具有攻擊性的參與者和誠實參與者2個角度設計協議，這樣是不夠全面的，因為利益也會影響參與者的行為，因此博弈論的思想在信息安全上越來越重要。現階段，已經有很多結合了博弈論思想的方案。

當前，已經有安全計算協議與博弈論結合的模型。但是參數過于簡單單一，只考慮了參與者攻擊成功與否所獲得的收益，并沒有考慮攻擊所要耗費的各種代價，而且在所設計的密碼協議中需要進行多輪計算，計算效率很低，因此分析不具有全面性和一般性，計算繁瑣。

本文引入多個參數，從多個角度考慮，構建一個具有一般性和全面性的博弈模型，在此基礎上，引入一個二叉樹在不暴露參與者信息的同時簡化計算過程，提高運算效率。

2 背景知識及博弈模型分析

2.1 背景知識

排序二叉樹：一種具有特殊性質的二叉樹，它擁有如下特質。

1) 當左子樹不是空的時候，左子樹上的所有值都會小于該左子樹的根節點的值。

2) 當右子樹不是空的時候，右子樹上的所有值都會大于該右子樹的根節點的值。

3) 這個節點的左子樹和右子樹也都是排序二叉樹，具有上述特質。

公平性：在進行安全兩方計算時，如果其中的參與者都成功地得到了計算結果，或者全都沒有成功地獲得計算結果，那么這個協議就是公平的。

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

納什均衡：當參與者之間在相互對抗相互依存的時候，形成各個參與者的當前選擇都是最優選擇時的一種穩定狀態。

左0右1編碼：是指從根節點開始，如果要編碼的節點在根節點左子樹上，則記下一個0，如果在根節點的右子樹上，則記下一個1，然后進入要編碼節點所在的子樹，進行上述過程，直到子樹就是該節點自己，按先后順序組合成只含有0和1的序列，這個序列就是該節點的編碼。

2.2 博弈模型分析

在本文所設計的模型中，讓不執行協議的參與者或者計劃猜測正確值的參與者能得到的利益非常小，遠小于一個善意的并且積極遵守協議的參與者的利益。其主要思想在于以一定概率傳輸無用數據來混淆能夠判斷出比較結果的核心元素。

如果攻擊者想要發起攻擊行為，從3個角度進行考慮。

3) 參與者并沒有發起任何攻擊，他會得到作為回報。

根據情況分析，>>。

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

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

表1 博弈模型

不具有惡意的參與者在發送數據時因為混入了大量無效值，成功將真實值隱藏在其中，導致惡意的參與者無法獲知其中哪一個是真實值，所以很大程度上提高了這個協議傳輸時的安全性，因此將這樣獲得的收益設為U。但是，如果惡意參與者在此時沒有去攻擊，這種收益是不存在的。這時，不具有惡意的參與者不會有這個U收益。

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

當一個惡意參與者發現對協議進行攻擊去獲取真實值節點時所要花費的代價大于獲取真實值后的收益，那么從理性的角度考慮，其不會發動攻擊，從而有

化簡可得

3 理性的安全兩方計算協議

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

3.1 數據準備階段

輸入 令和是Alice、Bob的私有輸入值。在協議進行過程中，和的值并不會被外界以及對方知曉。

構成排序二叉樹Atree后，對樹中的進行左0右1的編碼。例如，在圖1中，如果在51的位置，那么編碼為001；如果在93的位置，那么編碼為110；Alice記下所在位置的編碼AtreeCode。

圖1 二叉排序樹

Bob對自己的隨機序列B1，B2，B3，…，，…，B?1，B做相同的準備，構成排序二叉樹BTree記下自己的所在位置的編碼BTreeCode。

3.2 數據交互計算階段

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

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

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

4 協議分析

4.1 時間復雜度和計算復雜度

本協議在數據交互階段僅需要進行一輪交互，時間復雜度較低。同時，在對排序二叉樹進行左0右1的編碼時計算簡單，便于操作。

4.2 公平性

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

4.3 安全性

本文可以保證Alice和Bob兩方在比較和大小的同時不會獲取到和的值。考慮到協議具有對稱性交互這一特點，只需要從其中一個參與者進行分析即可，因此從Alice的角度進行分析。Alice有2次從Bob處得到信息。

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

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

由上面的說明可知，Alice并不會從數據交互中獲取到Bob的任何隱私性的信息。Bob同理。

4.4 正確性

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

4.5 納什均衡

在協議的第一部分數據準備階段（3.1節），各個參與者都是單獨進行數據準備，所以不會打破公平性。在數據交互階段，交互前雙方自己并不知道比較的結果，要想知道比較的結果，都依賴于對方發送的編碼。而不履行協議單獨去猜測編碼又不符合理性參與者自身的利益，故在數據交互的整個過程中，如果參與者出現背叛而不履行協議或者不發送最后的編碼，均不能增加收益，因此協議雙方的最佳策略是相互合作，即所有參與者都能得到結果。

5 結束語

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

[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-），女，山西呂梁人，博士，北京工業大學教授，主要研究方向為密碼學和安全協議。

鄭煒（1989-），男，河北石家莊人，北京工業大學碩士生，主要研究方向為密碼學、博弈論及安全多方計算。

2017-10-22；

2017-12-09

鄭煒，sj.bill@qq.com

國家自然科學基金資助項目（No.10007016201201）

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