基于博弈論的安全多方求和方法

(1.廣州美術學院 計算機基礎教研室， 廣州 510260；2.中山大學 信息科學與技術學院， 廣州 510275)

摘 要：在已知的安全求和方法基礎上，針對合作各方可能不誠實提供數據或共謀的情況，提出了一種基于博弈論的安全多方求和算法。算法中各方基于最大化收益的目標，自覺選擇誠實、不共謀的參與計算。分析表明算法能很好地完成計算，保護隱私信息。

關鍵詞：分布式計算；博弈；安全求和；共謀

中圖分類號：TP393.08文獻標志碼：A

文章編號：1001-3695(2009)04-1497-03

Multi-party secure sum computation based on game theory

ZHANG Guo-rong1，YIN Jian2

(1.Computer Staff Room， Guangzhou Academy of Fine Arts， Guangzhou 510260， China; 2.School of Information Science Technology， Sun Yat-sen University， Guangzhou 510275， China)

Abstract:On the basis of known secure sum computation， this paper concentrated on the issue of dishonesty and collusion when sharing data for secure sum computation and proposed a method based on game theory. In the method each participant consciously cooperative took a computation so that it could maximize its benefit or utility score during the entire secure sum computation process. The analysis demonstrates that the method is more efficiently and privacy information is preserved.

Key words:distributed computing; game; secure sum computation; collusion

隨著技術的進步，計算能力以及存儲能力的日益提高，數據規模的迅速增長，越來越多的數據按地理位置分布于多個場所。為了挖掘這些分布式數據且保持數據隱私性，越來越多的分布式隱私保護算法被研究出來。然而，這些保持隱私性的算法常常假設參與計算的各方有著良好的行為并嚴格按照協議執行，不為某種目的而提供虛假信息，不為了得到第三方數據而與其他方共謀。但是，在現實生活中，如果有機會得到隱私信息，計算各方很容易選擇不誠實和共謀，本文基于博弈論設計一種更符合真實情況的安全多方求和算法，在多方計算時，各方基于最大化收益的目標，自覺選擇誠實、不共謀的參與計算，從而達到保護參與各方私有信息的目的。

1 相關工作

安全求和算法是安全多方計算的一個基本操作，文獻[1]中介紹了一種簡單的安全求和方法：

假設存在三個以上的站點P1，…，Pm分別擁有數值Vi，i∈[1，m]，Vi∈[1，n]；各方之間沒有共謀現象。為了計算V=mi=1Vi，令某一方為主站點（設為P1），P1產生隨機數R并將R+V1 mod n傳給P2 ，P2計算R+2i=1Vi mod n并將其傳給P3。依此類推，Pm最終得到R+mi=1Vi mod n，并將其傳給P1，P1計算

R+mi=1Vi mod n-R，得到mi=1Vi mod n，P1得到各站點的總和，根據需要可以向其他站點發布這個總和，如圖1所示。

上面的方法能夠很好地解決安全求和的問題，通信次數為2m，每次通信傳送的消息個數為1，每個用戶做一次加法，所以計算代價為O(m)，有很好的性能。但是，它有兩個缺點：a）如果某一方相鄰的兩方共謀，則它的安全將受到破壞，如P1和P3合謀，它們知道P2接收的數據是13，發送的數據是18，那么可以推算出P2的數據是5，P2的私有數據被披露。b）如果計算的某一方存在私心，不誠實地提供數據，如P3的私有數據是2，但計算時它提供的是4，那么計算出的總和是16，P1和P2在誠實提供數據后卻得到一個不準確的和；而P3收到P1發布的這個總和16后，減去自己造假多提供的2，可以得到真實的總和14。



文獻[2]提供了一種能夠解決共謀問題的安全求和方法。主要的思想是：m（m≥3）個用戶各有一個私有數據，他們要共同秘密計算這些數據的和mi=1xi，但任何一個用戶都不愿意向其他用戶泄露自己的私有信息。基本的操作是：a）每個用戶將自己輸入的數據隨機劃分成m份；b）每個用戶把分成的m份分別發給所有的用戶（包括自己）；c）每個用戶分別計算自己收集到數據的和，然后廣播給其他用戶；d）每個用戶再次分別計算自己收集到的數據（部分和），計算出總和。算法很好地解決了共謀的問題，只有其余的各方（m-1方）共謀，剩下的一方隱私才受到威脅。但是它的通信次數為m2，計算代價為O(m2)。

文獻[3]也提供了一種能夠解決共謀問題的安全求和方法。主要的思想是：考慮一個有s個站點的網絡，這些站點可能是誠實的，也可能是懷有惡意的，懷有惡意的站點共謀起來去暴露其他站點的信息，而誠實的站點按照正確的安全求和協議執行。在安全求和協議開始之前，為了共謀，懷有惡意的站點在網絡中隨機發送一個一起共謀的請求，如果這樣一個信息被一個誠實的的點收到，那么它知道在網絡中有一群共謀的站點存在，為了去處罰這些共謀的站點，保護自己私有信息，誠實的站點把本地值分成隨機的k份，這里k是一個共謀組最大數目的估計值，一個可能的方法是基于一個誠實站點收到的共謀邀請數目做出估計。另一方面，一個懷有惡意站點，在收到這樣一個邀請信息后，就形成了一個聯系共謀組，在安全求和協議開始之后，正如傳統的安全求和協議[1]，站點增加一個隨機值和作了模運算后把值傳送出去；然而，誠實的站點不會一次送出所有的完整數據，他們每次只送出數據的一部份，因此，需要循環k次，安全求和才結束。這樣，懷有惡意的站點通過共謀不能得到其他站點的私有信息，但是求和計算的代價從不共謀的情況下的O（s）增加為O(ks)，如果站點是理性的，它將選擇不共謀。但算法沒有考慮懷有惡意的站點提供不準確數據的情況。

本文基于博弈論的思想[4，5]，同時考慮懷有惡意站點提供不準確數據和共謀的情況，利用廉價磋商(cheap talk)的機制，通過多次求和后比較結果的方法防止懷有惡意的站點提供不準確數據，從而使安全求和順利進行。

2 基于博弈論的安全多方求和方法

博弈是指利益存在沖突的決策主體在相互對抗（或合作）中，雙方（或多方）相互依存的一系列策略和行動的過程集合。在決策過程中，假設各方是理性的，并根據自己掌握的知識和對其他方決策的預期選擇自己的策略和行動。本文考慮的是最簡單的博弈模型——完全信息靜態博弈。

2.1 相關定義

定義1 完全信息靜態博弈。如果所有參與者對他們的收益的信念都是確定的，那么這個博弈就是完全信息的；如果博弈的任何一方參與者在采取行動時，并不知道對手采取了什么樣的行動，博弈與參與者行動的時間先后無關，那么這個博弈就是靜態的；如果一個博弈具有完全信息和靜態的特征就是完全信息靜態博弈。

定義2 博弈基本式。博弈表達的基本式由參與者N、策略空間S和收益函數u三個要素組成，即G={N，S，u}。其中：N={1，2，…，n}；S={S1，S2，…，Sn}；u={u1，u2，…，un}。收益函數ui:S→R，它表示第i位參與者在不同策略組合下所得到的收益。

定義3 納什均衡。如果一個策略組合s*=(s1*，…，sn*)是博弈G=(S，u)的一個納什均衡，那么對任一參與者i=1，2，…，n，對其任一個策略si∈Si，不等式成立ui(si*，s-1)≥ui(si，s-1)。

2.2 安全多方求和的博弈分析

按照博弈論的基本知識，本文考慮懷有惡意站點提供不準確數據和共謀兩種情況，因為這兩種情況屬于不同的階段，為了容易表達，可以分為兩個不同的博弈過程。

博弈基本式1（不誠實提供數據）：

a）參與者集合。n個站點，N={1，2，…，n}。

b）策略空間。每個站點的策略空間為Si={誠實，欺騙}。

c）收益。如果所有其他站點都誠實提供數據，而第i個站點也選擇誠實提供數據，那么，所有站點都得到相同的收益，不妨假設為3。如果第i個站點選擇不誠實提供數據，那么，他得到正確結果，在以后的競爭中具有優勢，所以他的收益更高一些，假設為4，而別的站點得到不正確的結果，且在競爭中處于劣勢，所以收益為-1；如果有兩個或兩個以上的站點選擇不誠實提供數據，那么欺騙的站點得到也是不正確的結果，即所有站點均得到不正確的結果，收益為0。表1是以有三個站點進行合作為例，分別列出他們各種情況下的收益。

表1 三個站點合作時選擇不同策略的收益

P1P2P3收益1收益2

誠實誠實誠實（3，3，3）（3，3，3）

誠實誠實欺騙（-1，-1，4）（2，2，2）

誠實欺騙誠實（-1，4，-1）（2，2，2）

誠實欺騙欺騙（0，0，0）（1，1，1）

欺騙誠實誠實（4，-1，-1）（2，2，2）

欺騙誠實欺騙（0，0，0）（1，1，1）

欺騙欺騙誠實（0，0，0）（1，1，1）

欺騙欺騙欺騙（0，0，0）（0，0，0）

從表1中收益1的值可以看出，如果三個站點都選擇誠實提供數據，那么他們可以得到收益3；如果有兩個站點誠實提供數據，那么選擇欺騙的站點得到更高的收益4，而誠實的站點收益為-1；如果只有一個站點誠實提供數據，那么大家都得不到正確的結果，收益為0。所以，基于收益最大化的目標，站點容易選擇欺騙，因為如果別人誠實，則可以得到收益4，如果別人欺騙，則合作無效，收益為0，比選擇誠實時的-1高。最后，由于互相不信任，所有站點選擇了不誠實的提供數據，合作無法進行。

為了解決不可能合作的問題，有很多方法被提供，方法之一是存在強制執行的協議，要求每一個合作方必須按照協議的要求執行，否則將受到法律的懲罰。本文則從技術上提供一種可以杜絕不誠實提供數據的算法，算法假設存在一個大家都可以信任的發起者，發起者將自己的數據加上一個隨機數后發送出去，最后把收到的總和減去隨機數就是可能的結果。為了杜絕其他方不誠實提供數據，發起者再次把自己的數據加上一個不同第一次的隨機數發送出去，最后把收到的總和減去隨機數與第一次得到的結果比較，如果相同，則其他方沒有不誠實提供數據，結果有效，可以公布出去；如果不同，則存在不誠實提供數據的其他方。所以，只能必須重新計算，至到連續兩次結果相同，計算才結束。這樣，如果有存在不誠實提供數據的合作方，那么計算無效，一直循環下去，欺騙方最后沒有得到正確的結果，也沒有取得競爭的優勢；但不停的計算會浪費時間，消耗自己，收益更低，如表1中的收益2，所以各方從一開始就選擇合作誠實的提供數據。

博弈基本式2（共謀）：

a）參與者集合。n個站點，N={1，2，…，n}。

b）策略空間。每個站點的策略空間為Si={誠實，共謀}。

c）收益。如果所有站點均按協議提供數據，不與其他站點共謀以得到別人的隱私信息，那么，所有站點都得到相同的收益，不妨假設為3，如果第i個站點希望與別的站點共謀，但不存在另一個站點與其共謀，那么，共謀行為無法執行，所有站點得到相同的收益3。但是，如果有兩個或兩個以上的站點發生共謀，那么他們可能得到別的站點的隱私信息，所以共謀站點的收益更高一些，假設為4，而被侵犯隱私的站點雖然得到正確的結果，但卻丟失了自己的隱私信息，因為隱私信息比正確的結果更重要，所以收益為-1；如果所有的站點選擇都選擇共謀，那么合作無法進行，即所有站點都無法得到求和的結果，收益為0。表2是以有三個站點進行合作為例，分別列出他們各種情況下的收益。

表2 三個站點合作時選擇不同策略的收益

P1P2P3收益1收益2

誠實誠實誠實（3，3，3）（3，3，3）

誠實誠實共謀（3，3，3）（3，3，3）

誠實共謀誠實（3，3，3）（3，3，3）

誠實共謀共謀（-1，4，4）（2，2，2）

共謀誠實誠實（3，3，3）（3，3，3）

共謀誠實共謀（4，-1，4）（2，2，2）

共謀共謀誠實（4，4，-1）（2，2，2）

共謀共謀共謀（0，0，0）（0，0，0）

從表2中的收益1可以看出，如果站點中有兩個站點選擇共謀，那么共謀站點可以得到更高的收益4，不共謀的站點雖然得到正確的結果，但隱私信息被侵犯，所以收益為-1；如果不共謀站點也選擇了共謀，那么合作無法進行，所有站點的收益為0。由于互相不信任，所有站點擔心自己的隱私信息被侵犯，而且在其他站點誠實時，共謀有可能得到更高的收益，所有站點選擇了共謀，合作無法進行。

為了解決問題，本文從技術上提供一種可以杜絕不誠實提供數據的算法，算法假設在程序運行之前，所有站點進行一次廉價磋商，為了共謀，懷有惡意的站點在網絡中隨機發送一個一起共謀的請求，如果這樣一個信息被一個誠實的站點收到，那么他知道在網絡中有一群共謀的站點存在，為了去處罰這些共謀的站點，保護自己私有信息，誠實的站點把本地值分成隨機的k份，這里k是一個共謀組最大數目的估計值，一個可能的方法是基于一個誠實站點收到的共謀邀請數目作出估計。另一方面，一個懷有惡意站點，在收到這樣一個邀請信息后，就形成了一個聯系共謀組，在安全求和協議開始之后，站點增加一個隨機值傳送出去，然而，誠實的站點不會一次送出所有的完整數據，他們每次只送出數據的一部分，因此，需要循環k次，安全求和才結束。這樣，懷有惡意的站點通過共謀不能得到其他站點的私有信息，但是求和計算的代價從不共謀的情況下O（s）的增加為O(ks)，收益減小，如表2中的收益2。如果站點是理性的，他將選擇不共謀。

2.3 安全多方求和算法

2.3.1 假設

a）包含個人數值型數據的多個站點進行安全求和計算，站點1為各方多認可的誠實站點，他將按照協議要求發起每一輪求和計算，并公布最終的結果。

b）每一個站點是理性的，他們根據自己收益的最大化選擇計算策略。

2.3.2 算法

基于博弈論的安全多方求和算法同時考慮懷有惡意站點提供不準確數據和共謀的情況，通過多次求和后比較結果的方法防止懷有惡意的站點提供不準確數據，利用廉價磋商的機制估計企圖共謀的站點數目，然后站點把數據分成多份發送出去，從而防止因為部分站點共謀而泄露隱私信息，使安全求和順利進行。方法步驟如下：

a）確認站點1為發起站點，負責發起每一輪的計算。

b）各個站點進行廉價磋商，估計可能的共謀站點數目k。

c）每個站點把自己的數據隨機分成k份。

d）站點1把自己的數據加上一個隨機值r1后發送給下一個站點，每一個站點接收上一個站點的數據后加上自己的一部分再發送到下一個站點，完成k輪后站點1得到最后的和S1，站點1把S1減去r1得到可能的和sum1。

e）站點1重新發起一次求和運算，把自己的數據加上一個不同于r1的隨機值r2后發送到下一個站點，每一個站點接收上一個站點的數據后加上自己的一部分再發送到下一個站點，完成k輪后站點1得到最后的和S2，站點1把S2減去r2得到可能的和sum2。

f）站點1比較sum1和sum2，如果相等，站點把sum1作為最后的求和結果發布出去；如果不相等，則說明有站點提供不真實數據，站點1重新發起求和運算，直到連續兩次運算得到的和一樣。

2.3.3 討論

文獻[2]提供的方法中每個用戶需要將自己輸入的數據隨機劃分成m份并發給所有的用戶（包括自己），這樣需要通信次數為m2，計算代價為O(m2)。與文獻[2]中算法不同的是，在存在共謀組時，站點只需把數據分成k份（k<

文獻[3]的實驗表明，算法能夠有效地防止共謀的發生，在多次實驗中，試圖共謀的站點在付出巨大代價后并沒有得到希望得到的結果，所以在下一輪計算中選擇轉變成不共謀的點，這樣，共謀站點的數字下降，計算得代價也逐漸降低，直到趨于平衡[3]（圖2）。與文獻[3]中算法不同的是，本文考慮了不誠實提供數據的情況，通過多運算一次，檢驗是否存在不誠實提供數據的情況，基于收益最大化的目標，站點可能選擇誠實提供數據，則運算進行兩次就可以，并不會增加太多的開銷。

3 結束語

為了適應分布式數據挖掘對數據的隱私性的要求，基于隱私保持的分布式數據挖掘正成為新的研究方向。安全多方求和是隱私保護數據挖掘算法中常用的一個基本運算。本文考慮計算時參與各方不誠實提供數據和共謀的情況，提出一種基于博弈論的算法。分析表明算法能很好的隱藏數據，保護隱私信息，且復雜度沒有提高。

參考文獻：

［1］

CLIFTON C，KANTARCIOGLU M，VAIDYA J，et al.Tools for privacy preserving distributed data mining[J].SIGKDD Explorations，2002，4(2):28-34.

[2]羅永龍，徐致云，黃劉生.安全多方的統計分析問題及其應用[J].計算機工程與應用，2005，41(24):141-143.

[3]BHADURI K，DAS K，KARGUPTA H.Peer-to-peer data mining，privacy issues，and games[C]//Lecture Notes in Computer Science，vol 4476.Berlin:Springer，2007：1-10.

[4]KARGUPTA H，DAS K，LIU K.A game theoretic approach toward multi-party privacy-preserving distributed data mining，TR-CS-0701[R].[S.l.]:UMBC，2007.

［5］ KARGUPTA H，DAS K，LIU K.Multi-party， privacy-preserving data mining using a game theoretic framework[C]//Proc of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD’07).Berlin，Heidelberg:Springer-Verlag，2007：523-531.