陳振華，黃路琪，史曉楠，聶靖靖

（1.西安科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，陜西 西安710054；

2.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點實驗室，廣西 桂林541004）

0 引 言

安全多方計算最早由Yao提出，是指各個參與方在不泄露各自輸入隱私的情況下，能正確合作計算出某個問題。保護(hù)隱私的合作計算都可歸為安全多方計算［1］，例如，保護(hù)隱私的數(shù)據(jù)挖掘［2-4］，統(tǒng) 計 計 算［5-7］，機 器 學(xué) 習(xí)［8-10］，數(shù) 據(jù) 聚合［11-14］，外包計算［15-17］，和數(shù)據(jù)查詢［18-19］等。

安全幾何計算是安全多方計算的一個重要分支，是指各參與方在保護(hù)各自數(shù)據(jù)隱私的情況下，共同計算一個幾何問題。例如：投資公司A，B想要擴展市場，A想知道自己的投資范圍是否在B的范圍內(nèi)，但B的計劃是商業(yè)機密，而A也不想告訴B自己的投資計劃，在不暴露各自商業(yè)機密的前提下，雙方如何解決這個問題？

若將公司的投資計劃看成平面區(qū)域，對應(yīng)的數(shù)學(xué)模型是：保密判定空間中2個平面是否相交。而要判定此關(guān)系，需要先解決向量安全計算問題。外包計算是目前流行的一種計算模式，但服務(wù)器作為不可信第三方，可能會泄露用戶隱私。因此，在利用外包服務(wù)的同時，如何保護(hù)各參與方數(shù)據(jù)隱私解決向量計算問題并進(jìn)一步解決平面判定問題，成為目前一個較新的研究方向。

針對向量安全計算，以往的學(xué)者提出了一些解決方案。周素芳等人利用哥德爾編碼和同態(tài)加密解決了向量線性組合計算問題，該方案使用了公鑰加密，不是信息論安全，也不適用于外包計算［20］。陳振華等人提出了基于同態(tài)加密的向量內(nèi)積外包計算協(xié)議。該協(xié)議適用于外包計算，但不是信息論安全且復(fù)雜度較高［21］。張衛(wèi)國等人引入不可逆矩陣來保護(hù)數(shù)據(jù)隱私，計算了向量內(nèi)積［22］，Li等人借助內(nèi)積運算來判定空間位置關(guān)系［23］。雖然協(xié)議都達(dá)到了信息論安全，但并不適用于外包計算。

針對以上方案的不足，文中利用矩陣論中一些特殊函數(shù)的性質(zhì)和隨機數(shù)混淆的方法來保護(hù)數(shù)據(jù)隱私，并利用外包計算節(jié)省成本。在此基礎(chǔ)上，設(shè)計了安全外包計算的向量內(nèi)積、向量模長和向量夾角計算協(xié)議，并解決了空間面與面的保密位置判定問題。

1 模型簡介

1.1 半誠實模型

安全多方計算的協(xié)議運行環(huán)境分為半誠實參與者模型和惡意參與者模型［24-29］。文中協(xié)議都建立在半誠實模型下，因此這里只給出半誠實模型定義。半誠實參與者是指協(xié)議方誠實地執(zhí)行協(xié)議，不會篡改輸入和輸出信息，但可能會保留計算的中間結(jié)果，試圖從中間結(jié)果和最后輸出推導(dǎo)出協(xié)議之外的信息或者他人的信息。

1.2 半誠實模型下的安全性定義

外包計算中半誠實模型下的安全兩方計算的模擬范例定義如下：設(shè)Alice擁有x，Bob擁有y，Server是外包服務(wù)器，f（x，y）為概率多項式函數(shù)；π是計算f的協(xié)議。Alice，Bob和Server要在不泄露x，y給任何一方的前提下，合作計算函數(shù)f（x，y）=（f1（x，y），f2（x，y））。

Alice（Bob）執(zhí)行協(xié)議π時得到的視圖為viewπ1（x，y）（viewπ2（x，y））；viewπ3（x，y）為Server的視圖；viewπ4（x，y）（viewπ5（x，y））為Server和Alice（Bob）合謀的視圖。其中E（x），E（y）分別表示Alice和Bob發(fā)送給Server的數(shù)據(jù)，即Server獲得的輸入。

定義1 在外包計算環(huán)境下，如果存在概率多項式的模擬器S1，S2，S3，S4，S5使得表1中的5個式子同時成立，則稱協(xié)議π保密地計算了f.

表1 外包計算中安全兩方計算的安全性Table 1 Security of secure two-party computation in outsourced computation

1.3 特殊函數(shù)

1.3.1 正交變換

正交變換是指在歐式空間V中的線性變換f，若存在x，y∈V，滿足＜fx，fy＞=＜x，y＞，則稱f為正交變換。

1.3.2 單向函數(shù)

如果函數(shù)f：｛0，1｝*→｛0，1｝*滿足下列2個條件，則稱f為單向函數(shù)。

1）存在一個確定的多項式算法A，能夠接受輸入x，輸出函數(shù)值f（x），即A（x）=f（x）；

2）對任意概率多項式時間算法A′，任意的正多項式P（.）以及充分大的n都有

2 安全外包向量計算協(xié)議

協(xié)議1 保密計算向量內(nèi)積

輸入：Alice保密輸入向量X=（x1，x2，…，xn），Bob保密輸入向量Y=（y1，y2，…，yn），且n≥2.

輸出：Alice和Bob都能知道向量X和Y的內(nèi)積，但外包服務(wù)器不知道結(jié)果。

1）Alice和Bob分別選擇隨機數(shù)r1和r2，和具有正交性的單向函數(shù)f.Alice計算r1fX發(fā)送給外包服務(wù)器。

2）Bob計算r2fY發(fā)送給外包服務(wù)器。

3）云服務(wù)器收到Alice和Bob發(fā)來的數(shù)據(jù)，計算r1fX和r2fY的內(nèi)積，得到結(jié)果r1r2＜X，Y＞，即＜r1fX，r2fY＞=r1r2＜X，Y＞，并將結(jié)果傳遞給Alice.

協(xié)議2 保密計算向量的長度

輸入：Alice保密輸入向量X=（x1，x2，…，xn），且n≥2.

輸出：Alice得到向量X的長度，而外包服務(wù)器不知道結(jié)果。

1）Alice選取隨機數(shù)r和具有正交性的單向函數(shù)f，計算并傳給外包服務(wù)器。

2）外包服務(wù)器計算rfX和rfX的內(nèi)積，得到r2＜X，X＞，即＜rfX，rfX＞=r2＜X，X＞，并將結(jié)果傳給Alice.

協(xié)議3 保密計算向量夾角

輸入：Alice保密輸入向量X=（x1，x2，…，xn），Bob保密輸入向量Y=（y1，y2，…，yn），且n≥2.

輸出：Alice和Bob都能得到2個向量的夾角，但外包服務(wù)器不知道結(jié)果。

Alice和Bob分別調(diào)用協(xié)議2，保密計算向量X和Y的模長。

1）Alice和Bob分別選擇隨機數(shù)r1和r2，和具有正交性的單向函數(shù)f，計算并傳給外包服務(wù)器。

分析：在協(xié)議1中，Alice和Bob利用函數(shù)f的正交性，將對向量X和Y的內(nèi)積計算轉(zhuǎn)換成fX和fY的內(nèi)積計算。又利用f的單向性對向量X和Y保護(hù)隱私，得到fX和fX，由于f具有單向性，因此任何人都不能得到初始輸入X和Y.又因為隨機數(shù)的加入，所以數(shù)據(jù)r1fX，數(shù)據(jù)r2fY和隨機數(shù)具有了不可區(qū)分性，因此保護(hù)了X和Y的隱私。此外，Alice和Bob利用隨機數(shù)r1和r2混淆了fX和fY內(nèi)積結(jié)果，由于結(jié)果中含有Alice和Bob的隨機數(shù)乘積r1r2，因此外包服務(wù)器無法獲得真正的內(nèi)積值。即使考慮合謀，由于Alice和Bob不可能合謀，因此外包服務(wù)器無法同時獲得兩方的隨機數(shù)r1和r2，從而無法獲得合謀條件下內(nèi)積結(jié)果。即協(xié)議1保密地計算了向量的內(nèi)積。

類似的方法可以分析協(xié)議2和協(xié)議3，得到類似結(jié)論。

3 安全性證明

在本節(jié)，應(yīng)用2.2節(jié)的模擬范例我們給出以上3個協(xié)議的安全性證明，先證明協(xié)議1.

定理1 協(xié)議1保密地外包計算了2個向量X和Y的內(nèi)積。

證明 按照2.2節(jié)外包計算中半誠實模型下安全兩方計算安全性的定義，需要構(gòu)造表1中的5個模擬器S1，S2，S3，S4和S5.由于文章篇幅有限，因此安全性證明只給出了模擬器S1的詳細(xì)過程，其他模擬器可按同樣的道理得到。

在協(xié)議1中f1（x，y）=＜X，Y＞.S1將X，f1（x，y）作為輸入進(jìn)行模擬，并按照以下步驟執(zhí)行

第1步S1選取隨機向量Y′，f1（X，Y）=f1（X，Y′），即＜X，Y＞=＜X，Y′＞，然后用X和Y′進(jìn)行模擬。根據(jù)協(xié)議1，將向量X轉(zhuǎn)換，得到r1fX，記作X1.S1選擇任意隨機數(shù)r2′，將向量Y′轉(zhuǎn)換，得到r2′fY′，記作Y1′.

第2步S1將r1fX和r2′fY′傳給外包服務(wù)器，服務(wù)器計算r1fX和r2′fY′的內(nèi)積，即，得到r1r2′＜X，Y′＞，記作C′.

此過程證明，Alice的視圖只能從自己的輸入和輸出中得到；同理，Bob的視圖只能從自己的輸入和輸出中得到，即Alice和Bob所獲得的視圖中都不包含對方的任何信息。因此證明了整個外包計算過程中，Alice和Bob都得不到對方的隱私。

通過構(gòu)造模擬器S3，可得到

此過程證明，Server的視圖只能從自己的輸入E（X），E（Y）和輸出E（X，Y）得到，即Server的視圖中不包含Alice和Bob的任何信息。因此證明了整個外包計算過程中，Server都得不到Alice和Bob的隱私。

通過構(gòu)造模擬器S4和S5，得到：

以上過程證明了Alice和Server合謀的視圖只能從自身輸入X，E（X），E（Y）和所獲得的輸出f1（X，Y），E（X，Y）中得到，并沒有包含Bob的信息。同理，Bob和Server合謀的視圖也只能從自身的輸入和輸出中得到，并沒有包含Alice的信息。因此證明了在外包計算過程中，即使Server與其中任何一方參與者合謀，也得不到另一方的信息。

證畢。

類似的方法可證明協(xié)議2和協(xié)議3的安全性，得到以下定理。

定理2 協(xié)議2保密地外包計算了向量長度。

定理3 協(xié)議3保密地外包計算了向量夾角。

4 效率分析與比較

本節(jié)給出在外包計算的模式下，保密判斷空間面與面位置關(guān)系的協(xié)議及其效率分析比較。

協(xié)議4 保密判斷空間面與面的位置關(guān)系

2）Alice和Bob調(diào)用第3節(jié)中的協(xié)議3，求得2個方向向量的夾角，若cosθ≠±1，則平面∥1和平面∥2相交；若cosθ=0，則平面∥1和平面∥2垂直；若cosθ=±1，則平面∥1和平面∥2平行或重合，接著進(jìn)行下一步。

3）Alice在平面∥1上任取一點，得到向量X=（x0，y0，z0，1）.Bob得到向量Y=（A2，B2，C2，D2）.Alice和Bob調(diào)用第3節(jié)中的協(xié)議1，可計算出向量X與向量Y的內(nèi)積。如果內(nèi)積值為零，平面和平面重合，否則平行。

由于協(xié)議4是依靠文中的協(xié)議1，協(xié)議3設(shè)計的，而第3節(jié)的安全性證明已經(jīng)證明了協(xié)議1，協(xié)議3都是安全的，因此可以得到協(xié)議4也是安全的，這里不再詳細(xì)證明。

由于文中和文獻(xiàn)［21-23］都處理了空間面面位置關(guān)系問題，而文獻(xiàn)［20］并沒有處理該問題。因此就文獻(xiàn)［21-23］處理的共同的面面位置保密判定協(xié)議做出比較和分析。為了方便比較，將模冪運算記為Me，模乘運算記為MN，乘法運算記為M，向量維數(shù)記為n，統(tǒng)一使用文獻(xiàn)［21］的模數(shù)N.整個協(xié)議執(zhí)行過程中，計算開銷比較大的是模冪運算，模乘運算，乘法運算，因此把這些運算總個數(shù)作為衡量計算復(fù)雜度的指標(biāo)，其他忽略不計。

4.1 理論分析與比較

4.1.1 計算復(fù)雜度

文獻(xiàn)［21］的面面位置關(guān)系保密判定（協(xié)議6），整個協(xié)議計算過程中調(diào)用了2次內(nèi)積協(xié)議，用戶加解密過程中使用了模冪和模乘運算，其運算總個數(shù)為2MN+18Me.

文獻(xiàn)［22］的安全計算面與面的位置關(guān)系（協(xié)議5），整個協(xié)議計算過程中調(diào)用了4次內(nèi)積協(xié)議，每調(diào)用一次內(nèi)積協(xié)議，用戶進(jìn)行2次矩陣相乘，需16次乘法，因此運算總個數(shù)為64M.

文獻(xiàn)［23］的保密判定面與面的位置關(guān)系協(xié)議（協(xié)議4），整個協(xié)議計算過程沒有調(diào)用內(nèi)積協(xié)議，而是進(jìn)行了3個3階矩陣行列式運算，和3個3維向量內(nèi)積運算，即9個乘法運算，因此運算總個數(shù)為36M.

文中面面位置關(guān)系保密判定（協(xié)議4），整個協(xié)議計算過程需要調(diào)用1次保密計算夾角和1次保密計算內(nèi)積協(xié)議，用戶運算總個數(shù)8MN+6M.

4.1.2 通信復(fù)雜度

衡量通信復(fù)雜度的指標(biāo)用協(xié)議交換信息的比特數(shù)，或者用通信輪數(shù)，在多方保密計算研究中通常使用輪數(shù)。

文獻(xiàn)［21］的面面位置關(guān)系保密判定（協(xié)議6），整個協(xié)議計算過程中調(diào)用了2次保密計算內(nèi)積協(xié)議和1次比較協(xié)議，內(nèi)積協(xié)議每調(diào)用一次需要3輪交互，比較協(xié)議需要2次交互。則用戶和外包服務(wù)器總共進(jìn)行了8輪交互。

文獻(xiàn)［22］的安全計算面與面的位置關(guān)系（協(xié)議5），整個協(xié)議計算過程中調(diào)用了4次內(nèi)積協(xié)議，內(nèi)積協(xié)議每調(diào)用一次需要2輪交互，用戶之間總共進(jìn)行了8輪交互。

文獻(xiàn)［23］的保密判定面與面的位置關(guān)系協(xié)議（協(xié)議4），整個協(xié)議計算過程中沒有調(diào)用內(nèi)積協(xié)議，用戶之間總共進(jìn)行了2輪交互。

文中面面位置關(guān)系保密判定（協(xié)議4），整個協(xié)議計算過程調(diào)用了1次保密計算夾角協(xié)議和1次保密計算內(nèi)積協(xié)議，分別需要進(jìn)行5輪和3輪交互。則用戶和外包服務(wù)器之間的總輪數(shù)為8輪。

4.1.3 性能

以各個協(xié)議取得的安全性級別，是否適用于外包計算和能夠解決的空間位置問題作為衡量性能的標(biāo)準(zhǔn)。以“√”代表協(xié)議能夠解決的空間位置問題。

綜合以上，得到文中協(xié)議4和文獻(xiàn)［21-23］的效率比較見表2，性能比較見表3.

由文獻(xiàn)［30］可知，1個模冪運算等價于logN個模乘運算。假設(shè)這里所有協(xié)議都采用和文獻(xiàn)［30］同樣的操作平臺，可將表2中文獻(xiàn)［21］方案的計算個數(shù)換算為2MN+36logNM.因此由表2可以看到，相比于文中協(xié)議4，以往的方案［21-23］計算開銷較大。由于文中利用矩陣論中一些特殊函數(shù)的性質(zhì)保護(hù)數(shù)據(jù)，并沒有使用公鑰加密的方法，因此計算復(fù)雜度和通信復(fù)雜度較低，更具有實踐意義。從表3可以看出，方案相比以往的方案，不僅實現(xiàn)了信息論安全，也適合外包計算，并且所能處理的空間位置關(guān)系也更加廣泛。

表2 文中方案與現(xiàn)有方案的效率比較Table 2 Efficiency comparison of proposed approach and existing approaches

表3 文中方案與現(xiàn)有方案的性能比較Table 3 Performance comparison of proposed approach and existing approaches

4.1.4 傳統(tǒng)模式和外包模式下計算成本比較

由于保密內(nèi)積計算是整個安全外包計算的核心基礎(chǔ)，為了方便其他復(fù)雜安全多方計算問題架構(gòu)于此，因此文中協(xié)議1提供了外包模式下簡潔的保密內(nèi)積計算方案。這里仍采用和上文相同的標(biāo)記符號，計算復(fù)雜度記為O，得到協(xié)議1在傳統(tǒng)模式（非外包）下的計算成本為3MN+M，計算復(fù)雜度為O（1）；外包模式下計算成本為2MN+（n+1）M，計算復(fù)雜度為O（n），得到協(xié)議1在2種計算模式下的計算復(fù)雜性對比如圖1所示。

圖1 協(xié)議1在傳統(tǒng)模式和外包模式下的計算復(fù)雜度對比Fig.1 Computation complexity comparison of protocol 1 in traditional model and outsourced model

從圖1可以看出，未借助外包計算的內(nèi)積協(xié)議（曲線1）不僅用戶計算成本較大，且計算復(fù)雜度隨著向量維數(shù)的增大呈線性增長，因此為了節(jié)省用戶的計算成本，以按需付費的方式將保密內(nèi)積計算外包出去。由于該部分的計算量已經(jīng)由外包服務(wù)器計算，因此不再包含在用戶計算成本之內(nèi)，那么架構(gòu)于此基礎(chǔ)協(xié)議（即文中協(xié)議1）的協(xié)議4也不需要保密計算內(nèi)積，這樣就極大地節(jié)省了用戶的計算成本。

4.2 仿真實驗

為了直觀呈現(xiàn)以上協(xié)議的理論效率分析結(jié)果，在Java語言環(huán)境下將表2的4個協(xié)議編程實現(xiàn)。采用的計算機運行環(huán)境如下：操作系統(tǒng)為Windows 7旗艦版，CPU為Intel i5-5200U 2.20 GHz，內(nèi)存為4.00 GB.文中協(xié)議4和文獻(xiàn)［21］協(xié)議6主要運算為模運算，而文獻(xiàn)［22］協(xié)議5和［23］協(xié)議4的主要運算為乘法運算。因此分為2種情況進(jìn)行分析比較，第一種是將文中協(xié)議4和文獻(xiàn)［21］協(xié)議6進(jìn)行效率比較（不同模數(shù)下的耗時）；第二種是將文中協(xié)議4和文獻(xiàn)［22］協(xié)議5，文獻(xiàn)［23］協(xié)議4進(jìn)行效率比較（判斷不同位置關(guān)系的耗時）。

1）將文中協(xié)議4和文獻(xiàn)［21］協(xié)議6在不同模式下進(jìn)行耗時比較。在實驗中分別取不同的模數(shù)N為143，437，899，1 517 bits，得到2個協(xié)議的平均耗時，如圖2所示。

2）將文中協(xié)議4和文獻(xiàn)［22］協(xié)議5，文獻(xiàn)［23］協(xié)議4判斷不同位置關(guān)系進(jìn)行耗時比較，分別得到3個協(xié)議平行、相交、垂直、重合情況下的平均耗時，見表4.

從圖2和表4可以看出，文中協(xié)議4的平均耗時低于文獻(xiàn)［21］協(xié)議6，文獻(xiàn)［22］協(xié)議5和文獻(xiàn)［23］協(xié)議4的平均耗時。此外，從表4還可以看出文中協(xié)議4能判斷的面面位置關(guān)系更多（文獻(xiàn)［22］協(xié)議5不能判斷面面重和，文獻(xiàn)［23］協(xié)議4既不能判斷面面重和，也不能判斷面面垂直）。

綜合以上實驗結(jié)果，得到如下結(jié)論：無論理論分析還是實驗分析，本文協(xié)議效率較高，而且能判斷的空間位置關(guān)系更加廣泛。

圖2 文中方案與文獻(xiàn)［21］協(xié)議6在不同模數(shù)下的平均耗時比較Fig.2 Average time cost comparison of proposed approach and protocol 6 in reference［21］under different modulus

表4 文中方案與文獻(xiàn)［22］協(xié)議5，［23］協(xié)議4判斷不同位置關(guān)系的的平均耗時比較Table 4 Average time cost comparison of proposed approach and protocol 5 in reference［22］、protocol 4 in reference［23］under different determinations

5 結(jié) 論

1）利用矩陣論中一些特殊函數(shù)的性質(zhì)和隨機數(shù)混淆方法在外包計算下設(shè)計了3個基礎(chǔ)的信息論安全向量計算協(xié)議，分別是安全外包計算的向量內(nèi)積，向量模長和向量夾角計算協(xié)議。

2）利用這些基礎(chǔ)協(xié)議解決了空間面與面位置關(guān)系保密判斷問題，可進(jìn)一步解決金融投資等實際問題。

3）將提出的保密判定面與面的位置關(guān)系協(xié)議與其他已有方案進(jìn)行了理論分析和仿真實驗比較。結(jié)果顯示文中提出的方案效率更高，可判斷的空間位置關(guān)系更加廣泛。