信息論安全的3個(gè)基礎(chǔ)外包計(jì)算協(xié)議及空間位置關(guān)系保密判定

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

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

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

0 引 言

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

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

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

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

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

1 模型簡介

1.1 半誠實(shí)模型

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

1.2 半誠實(shí)模型下的安全性定義

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

Alice（Bob）執(zhí)行協(xié)議π時(shí)得到的視圖為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 在外包計(jì)算環(huán)境下，如果存在概率多項(xiàng)式的模擬器S1，S2，S3，S4，S5使得表1中的5個(gè)式子同時(shí)成立，則稱協(xié)議π保密地計(jì)算了f.

表1 外包計(jì)算中安全兩方計(jì)算的安全性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個(gè)條件，則稱f為單向函數(shù)。

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

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

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

協(xié)議1 保密計(jì)算向量內(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分別選擇隨機(jī)數(shù)r1和r2，和具有正交性的單向函數(shù)f.Alice計(jì)算r1fX發(fā)送給外包服務(wù)器。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 安全性證明

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

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

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

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

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

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

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

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

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

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

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

證畢。

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

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

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

4 效率分析與比較

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

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

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

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

由于協(xié)議4是依靠文中的協(xié)議1，協(xié)議3設(shè)計(jì)的，而第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é)議做出比較和分析。為了方便比較，將模冪運(yùn)算記為Me，模乘運(yùn)算記為MN，乘法運(yùn)算記為M，向量維數(shù)記為n，統(tǒng)一使用文獻(xiàn)［21］的模數(shù)N.整個(gè)協(xié)議執(zhí)行過程中，計(jì)算開銷比較大的是模冪運(yùn)算，模乘運(yùn)算，乘法運(yùn)算，因此把這些運(yùn)算總個(gè)數(shù)作為衡量計(jì)算復(fù)雜度的指標(biāo)，其他忽略不計(jì)。

4.1 理論分析與比較

4.1.1 計(jì)算復(fù)雜度

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

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

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

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

4.1.2 通信復(fù)雜度

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

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

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

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

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

4.1.3 性能

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

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

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

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

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

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

4.2 仿真實(shí)驗(yàn)

為了直觀呈現(xiàn)以上協(xié)議的理論效率分析結(jié)果，在Java語言環(huán)境下將表2的4個(gè)協(xié)議編程實(shí)現(xiàn)。采用的計(jì)算機(jī)運(yù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主要運(yùn)算為模運(yùn)算，而文獻(xiàn)［22］協(xié)議5和［23］協(xié)議4的主要運(yùn)算為乘法運(yùn)算。因此分為2種情況進(jìn)行分析比較，第一種是將文中協(xié)議4和文獻(xiàn)［21］協(xié)議6進(jìn)行效率比較（不同模數(shù)下的耗時(shí)）；第二種是將文中協(xié)議4和文獻(xiàn)［22］協(xié)議5，文獻(xiàn)［23］協(xié)議4進(jìn)行效率比較（判斷不同位置關(guān)系的耗時(shí)）。

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

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

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

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

圖2 文中方案與文獻(xiàn)［21］協(xié)議6在不同模數(shù)下的平均耗時(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)系的的平均耗時(shí)比較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ì)和隨機(jī)數(shù)混淆方法在外包計(jì)算下設(shè)計(jì)了3個(gè)基礎(chǔ)的信息論安全向量計(jì)算協(xié)議，分別是安全外包計(jì)算的向量內(nèi)積，向量模長和向量夾角計(jì)算協(xié)議。

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

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