摘  要： 提出了一個銷售量問題：不同的廠家有不同的商品，他們想知道相同商品在市場上的銷售總量，但各自都不透露自己的私有數(shù)據(jù)。同時提出了一個解決銷售量問題的協(xié)議，并且在半誠實(shí)模型下對協(xié)議的安全性和計算復(fù)雜度及通信復(fù)雜度進(jìn)行了分析。
關(guān)鍵詞： 多精度；安全多方求和；保密性；公平性

    目前，關(guān)于安全多方計算問題的研究主要包括保護(hù)私有信息科學(xué)計算問題、保護(hù)私有信息計算幾何問題、保護(hù)數(shù)據(jù)挖掘問題和安全多方統(tǒng)計分析問題等。前人在安全多方計算問題的實(shí)際具體研究上已經(jīng)有了很大的研究成果。本文提出了安全多方計算在統(tǒng)計中的一個新的應(yīng)用。
    例如，有n個經(jīng)營同一品牌不同產(chǎn)品的廠家，如生產(chǎn)手機(jī)、MP3和電視機(jī)等，他們想知道在市場上同一產(chǎn)品的銷售總量。在這種情況下，各個公司同一產(chǎn)品的銷售量應(yīng)該是保密的，最后要計算出同一產(chǎn)品在市場上的銷售總量。
    本文利用安全多方求和提出了一個解決上述問題的協(xié)議，并在半誠實(shí)下對該協(xié)議的正確性和安全性給出了證明，也計算出了計算復(fù)雜度和通信復(fù)雜度。本文假設(shè)參與各方都是“半誠實(shí)的”，即參與各方都能嚴(yán)格執(zhí)行協(xié)議的規(guī)定和流程，不會中途強(qiáng)行退出或惡意摻入虛假數(shù)據(jù)。但在協(xié)議執(zhí)行過程中他們可能會保留所有能搜集到的關(guān)于其他參與方的信息，以期望在協(xié)議結(jié)束后推斷出其他參與方的輸入信息。人們對安全多方協(xié)議的研究有很多是基于半誠實(shí)的，因此對基于半誠實(shí)模型下安全協(xié)議的研究是非常有意義的。
1 基本概念
1.1 多精度運(yùn)算
    機(jī)器直接處理的整數(shù)有一定的限制，當(dāng)算法中出現(xiàn)的整數(shù)超過了這個限度，就需要多精度算法[1]。多精度運(yùn)算就是用多個字節(jié)來存儲這個整數(shù)，將整數(shù)之間的運(yùn)算轉(zhuǎn)換成字節(jié)間的運(yùn)算。
1.2 安全多方計算[2]
    安全多方計算是指擁有秘密輸入的互不信任的n方，希望用各自的秘密輸入共同去計算一個約定的函數(shù)。在計算結(jié)束之后，每一方都能接收到正確的輸出，并且每一方只能了解自己的輸入和輸出，而不知道其他方的輸入和輸出。它能夠使參與者在不泄露各自輸入秘密的前提下完成協(xié)作計算的任務(wù)。
1.3 安全多方求和
    安全多方求和是指參與計算的多方成員，在保護(hù)各自輸入數(shù)據(jù)隱私的情況下，共同計算一個函數(shù)之和。假設(shè)有n個用戶(C1，C2，…，Cn)參與計算，每個用戶Ci有自己的私有數(shù)據(jù)xi，他們共同計算，但任何一方都不愿意向其他方泄露自己的私有數(shù)據(jù)[3]。
 

    以上通過安全多方求和方法進(jìn)行計算的方案協(xié)議，除了最終的計算結(jié)果外，不泄露公司的任何數(shù)據(jù)秘密，實(shí)現(xiàn)了保密計算的功能。
3 實(shí)例說明
    現(xiàn)有6個公司對同一品牌的3個不同產(chǎn)品(手機(jī)、MP3和電視機(jī))進(jìn)行銷售量的計算。M值為10萬。銷售情況如表1所示。

 每列是接收的秘密隨機(jī)數(shù)。

  (3)計算結(jié)果
    C1從傳送矩陣中得到第一列隨機(jī)數(shù){4 456，6 783，
5 672，4 672，5 623，10 234}，求出它們之和是37 440。C1公開把37 440發(fā)送給所有其他的Cj(j∈[1，n],j≠i)，類似地，C2～C6分別都公開發(fā)送自己得到的隨機(jī)數(shù)之和。那么，每個Ci(i∈[1，n])得到的隨機(jī)數(shù)之和為{37 440，38 333，35 307，27 269，38 485，26 854}，得到它們之和是203 688，即是所有產(chǎn)品的銷售總量，其對應(yīng)的二進(jìn)制序列為{110001101110101000}，則P1、P2、P3對應(yīng)的二進(jìn)制分別為{110001}、{101110}和{101000}。因此可知產(chǎn)品P1、P2、P3的銷售總量分別為49萬、46萬、40萬。
4 性能分析
    性能分析主要從安全性和計算復(fù)雜度及通信復(fù)雜度來進(jìn)行。
4.1 安全性分析
    定理1 如果參與評審的成員是半誠實(shí)的，則上述協(xié)議是安全的。
    (1)公平性：n方可以獨(dú)立同時完成計算并知道結(jié)果。單個成員不與其他成員合作，無法提前計算，因此協(xié)議具有公平性。
    (2)保密性：由于n方對數(shù)據(jù)先隨機(jī)拆分，再利用安全多方求和方法計算。每方只能接收到數(shù)據(jù)拆分后的一小部分，無法得到整個數(shù)據(jù)，因此數(shù)據(jù)具有完全保密性。
4.2 復(fù)雜度分析
    （1）計算復(fù)雜度
    由于上述協(xié)議的計算復(fù)雜度是多精度運(yùn)算的，每方在準(zhǔn)備階段對數(shù)據(jù)隨機(jī)劃分進(jìn)行了n-1次，所以多精度減法就執(zhí)行了n-1次，在計算結(jié)果階段計算接收到的所有數(shù)據(jù)之和，多精度加法執(zhí)行了n-1次，此方案中多精度整數(shù)的比特位數(shù)為mt(t=[log2(n×M)]+1)，則每一方的計算位復(fù)雜度為O(nmlog2(n×M))，總的計算位復(fù)雜度為O(n2mlog2(n×M))。
    （2）通信復(fù)雜度
    上述方案在發(fā)送數(shù)據(jù)和計算結(jié)果階段各進(jìn)行了n(n-1)次通信，則通信復(fù)雜度為 O(n2)，而每個數(shù)據(jù)的長度不超過m([log2(n×M)]+1)，所以通信的位復(fù)雜度為 O(n2log2(n×M))。
    本協(xié)議是一個新的安全多方計算協(xié)議的實(shí)際應(yīng)用，可以用于電子評審系統(tǒng)、統(tǒng)計學(xué)中的數(shù)據(jù)求和問題，此外還可以用于計算學(xué)生的總（平均）成績卻不泄露自己的任何消息給其他學(xué)生。在本協(xié)議中，若參與方的成員增多或數(shù)據(jù)值增大，計算復(fù)雜度和通信復(fù)雜度也會增大，但數(shù)據(jù)的保密性卻更好。因此如何降低計算復(fù)雜度和通信復(fù)雜度還需進(jìn)一步研究[5]。
參考文獻(xiàn)
[1] ROSEN K H.Elementary number theory and its applications[M].New York：Addition Wesley，1984.
[2] 馮登國.安全協(xié)議——理論與實(shí)踐[M].北京：清華大學(xué)出版社，2011.
[3] 曹天杰，張永平，汪楚嬌.安全協(xié)議[M].北京：北京郵電大學(xué)出版社，2009.
[4] 仲紅，黃劉生，羅永龍.基于安全多方求和的多候選人電子選舉方案[J].計算機(jī)研究與發(fā)展，2006，43(8)：1405-1410.
[5] 仲紅，黃劉生，羅永龍.一個實(shí)用的電子評審方案[J].小型微型計算機(jī)系統(tǒng)，2007，28(1)：178-181.