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

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

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

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

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