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

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

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

 每列是接收的秘密隨機數。

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