陳振華,黃路琪,史曉楠,聶靖靖
(1.西安科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,陜西 西安710054;
2.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室,廣西 桂林541004)
安全多方計(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ò)展市場(chǎng),A想知道自己的投資范圍是否在B的范圍內(nèi),但B的計(jì)劃是商業(yè)機(jī)密,而A也不想告訴B自己的投資計(jì)劃,在不暴露各自商業(yè)機(jī)密的前提下,雙方如何解決這個(gè)問題?
若將公司的投資計(jì)劃看成平面區(qū)域,對(duì)應(yīng)的數(shù)學(xué)模型是:保密判定空間中2個(gè)平面是否相交。而要判定此關(guān)系,需要先解決向量安全計(jì)算問題。外包計(jì)算是目前流行的一種計(jì)算模式,但服務(wù)器作為不可信第三方,可能會(huì)泄露用戶隱私。因此,在利用外包服務(wù)的同時(shí),如何保護(hù)各參與方數(shù)據(jù)隱私解決向量計(jì)算問題并進(jìn)一步解決平面判定問題,成為目前一個(gè)較新的研究方向。
針對(duì)向量安全計(jì)算,以往的學(xué)者提出了一些解決方案。周素芳等人利用哥德爾編碼和同態(tài)加密解決了向量線性組合計(jì)算問題,該方案使用了公鑰加密,不是信息論安全,也不適用于外包計(jì)算[20]。陳振華等人提出了基于同態(tài)加密的向量?jī)?nèi)積外包計(jì)算協(xié)議。該協(xié)議適用于外包計(jì)算,但不是信息論安全且復(fù)雜度較高[21]。張衛(wèi)國(guó)等人引入不可逆矩陣來保護(hù)數(shù)據(jù)隱私,計(jì)算了向量?jī)?nèi)積[22],Li等人借助內(nèi)積運(yùn)算來判定空間位置關(guān)系[23]。雖然協(xié)議都達(dá)到了信息論安全,但并不適用于外包計(jì)算。
針對(duì)以上方案的不足,文中利用矩陣論中一些特殊函數(shù)的性質(zhì)和隨機(jī)數(shù)混淆的方法來保護(hù)數(shù)據(jù)隱私,并利用外包計(jì)算節(jié)省成本。在此基礎(chǔ)上,設(shè)計(jì)了安全外包計(jì)算的向量?jī)?nèi)積、向量模長(zhǎng)和向量夾角計(jì)算協(xié)議,并解決了空間面與面的保密位置判定問題。
安全多方計(jì)算的協(xié)議運(yùn)行環(huán)境分為半誠(chéng)實(shí)參與者模型和惡意參與者模型[24-29]。文中協(xié)議都建立在半誠(chéng)實(shí)模型下,因此這里只給出半誠(chéng)實(shí)模型定義。半誠(chéng)實(shí)參與者是指協(xié)議方誠(chéng)實(shí)地執(zhí)行協(xié)議,不會(huì)篡改輸入和輸出信息,但可能會(huì)保留計(jì)算的中間結(jié)果,試圖從中間結(jié)果和最后輸出推導(dǎo)出協(xié)議之外的信息或者他人的信息。
外包計(jì)算中半誠(chéng)實(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.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)對(duì)任意概率多項(xiàng)式時(shí)間算法A′,任意的正多項(xiàng)式P(.)以及充分大的n都有
協(xié)議1 保密計(jì)算向量?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ì)算向量的長(zhǎng)度
輸入:Alice保密輸入向量X=(x1,x2,…,xn),且n≥2.
輸出:Alice得到向量X的長(zhǎng)度,而外包服務(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的模長(zhǎng)。
1)Alice和Bob分別選擇隨機(jī)數(shù)r1和r2,和具有正交性的單向函數(shù)f,計(jì)算并傳給外包服務(wù)器。
分析:在協(xié)議1中,Alice和Bob利用函數(shù)f的正交性,將對(duì)向量X和Y的內(nèi)積計(jì)算轉(zhuǎn)換成fX和fY的內(nèi)積計(jì)算。又利用f的單向性對(duì)向量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é)論。
在本節(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ì)算中半誠(chéng)實(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所獲得的視圖中都不包含對(duì)方的任何信息。因此證明了整個(gè)外包計(jì)算過程中,Alice和Bob都得不到對(duì)方的隱私。
通過構(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ì)算了向量長(zhǎng)度。
定理3 協(xié)議3保密地外包計(jì)算了向量夾角。
本節(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.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維向量?jī)?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í)別,是否適用于外包計(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]同樣的操作平臺(tái),可將表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提供了外包模式下簡(jiǎn)潔的保密內(nèi)積計(jì)算方案。這里仍采用和上文相同的標(biāo)記符號(hà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ù)雜性對(duì)比如圖1所示。
圖1 協(xié)議1在傳統(tǒng)模式和外包模式下的計(jì)算復(fù)雜度對(duì)比Fig.1 Computation complexity comparison of protocol 1 in traditional model and outsourced model
從圖1可以看出,未借助外包計(jì)算的內(nèi)積協(xié)議(曲線1)不僅用戶計(jì)算成本較大,且計(jì)算復(fù)雜度隨著向量維數(shù)的增大呈線性增長(zhǎng),因此為了節(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ì)算成本。
為了直觀呈現(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
1)利用矩陣論中一些特殊函數(shù)的性質(zhì)和隨機(jī)數(shù)混淆方法在外包計(jì)算下設(shè)計(jì)了3個(gè)基礎(chǔ)的信息論安全向量計(jì)算協(xié)議,分別是安全外包計(jì)算的向量?jī)?nèi)積,向量模長(zhǎng)和向量夾角計(jì)算協(xié)議。
2)利用這些基礎(chǔ)協(xié)議解決了空間面與面位置關(guān)系保密判斷問題,可進(jìn)一步解決金融投資等實(shí)際問題。
3)將提出的保密判定面與面的位置關(guān)系協(xié)議與其他已有方案進(jìn)行了理論分析和仿真實(shí)驗(yàn)比較。結(jié)果顯示文中提出的方案效率更高,可判斷的空間位置關(guān)系更加廣泛。