于寶華，鞏林明

0 引言

隨著人類信息社會(huì)的發(fā)展和分布式系統(tǒng)用戶對(duì)隱私保護(hù)需求的日益增長，安全多方幾何計(jì)算(Secure Multi-party Geometric Computation,SMGC)已經(jīng)成為安全多方計(jì)算中一個(gè)新興的研究領(lǐng)域[1].SMGC主要研究保密幾何圖形的安全計(jì)算問題或安全分析問題，目的是在互不信任的分布式用戶間實(shí)現(xiàn)協(xié)同完成某些特定的計(jì)算幾何計(jì)算任務(wù)，同時(shí)還要保護(hù)參與計(jì)算幾何協(xié)同運(yùn)算任務(wù)各用戶的隱私.能夠滿足分布式用戶隱私保護(hù)需求的計(jì)算幾何問題有著重要的應(yīng)用前景.

作為安全多方計(jì)算的熱點(diǎn)問題之一，SMGC已經(jīng)取得了相當(dāng)成果[1?25].安全幾何計(jì)算問題最初由Du等人[1,2]提出，并在文獻(xiàn)[1,2]中提出了安全兩方點(diǎn)包含問題、安全兩方線段相交問題、安全兩方凸多邊形相交問題以及安全兩方點(diǎn)的凸殼包含問題的解決方案；文獻(xiàn)[9,10,23]在Du的基礎(chǔ)上深入研究了安全兩方點(diǎn)包含問題；文獻(xiàn)[7]研究了保密凸殼挖掘問題；文獻(xiàn)[8]研究了保密凸殼相交問題；文獻(xiàn)[5]與[6]研究了保密多邊形的相交問題；文獻(xiàn)[12]研究了兩方立體幾何安全計(jì)算問題；文獻(xiàn)[13]究了密態(tài)幾何信息匹配問題；文獻(xiàn)[14]研究了保密三點(diǎn)張成面積計(jì)算問題；文獻(xiàn)[15]研究了過兩私有保密做一條直線問題；文獻(xiàn)[16]研究了隱匿拓?fù)潢P(guān)系的圖形計(jì)算問題；文獻(xiàn)[17]研究了保密空間圖形位置關(guān)系判定問題；文獻(xiàn)[18]研究了借助云計(jì)算的保密空間圖形位置關(guān)系判定問題；文獻(xiàn)[19]研究了基于點(diǎn)積保密計(jì)算的保密幾何計(jì)算問題；文獻(xiàn)[20]研究了基于保密點(diǎn)積計(jì)算的保密特殊多邊形相似判定問題；文獻(xiàn)[21]研究了基于hash函數(shù)的安全兩方保密圖形相似判定問題.

綜述所述，對(duì)于分布式環(huán)境中一些保護(hù)用戶隱私的安全幾何計(jì)算和安全幾何分析問題的相關(guān)研究已經(jīng)取得了長足進(jìn)步，但關(guān)于保密圖形相似問題的安全幾何計(jì)算問題尚屬初步，例如關(guān)于圖形相似關(guān)系的分析問題僅限于上面論述的問題；現(xiàn)有的保密圖形相似判定協(xié)議必須基于一個(gè)前提：雙方邊向量維數(shù)、角向量維數(shù)以及鄰接矩陣維數(shù)對(duì)應(yīng)相等，也就是說，雙方在進(jìn)行保密計(jì)算之前就已經(jīng)知道對(duì)方圖形的頂點(diǎn)數(shù)和邊數(shù).關(guān)于隱匿頂點(diǎn)數(shù)和邊數(shù)的保密幾何圖形相似計(jì)算和分析問題尚未研究.然而，隱匿頂點(diǎn)數(shù)和邊數(shù)的保密幾何圖形相似判定在保密地理信息查詢系統(tǒng)[24]和社交網(wǎng)絡(luò)用戶近感查詢系統(tǒng)[25]中更具有現(xiàn)實(shí)的應(yīng)用價(jià)值.因?yàn)槿绻捎矛F(xiàn)有的保密圖形相似判定協(xié)議解決地理信息系統(tǒng)以及社交網(wǎng)絡(luò)中的用戶隱私保護(hù)問題會(huì)造成先發(fā)送(哪怕是加密的)消息一方信息的泄露：先得到消息的一方會(huì)通過接收(哪怕是加密的)消息的數(shù)量事先得知另一方的邊、角、頂點(diǎn)個(gè)數(shù)，要知道這些信息都有助于圖形形狀的判定，而形狀對(duì)基于圖形相似判定的地理信息系統(tǒng)保密信息匹配至關(guān)重要，例如，地理信息系統(tǒng)中可能存在多個(gè)地理區(qū)域邊數(shù)唯一的情形.此外，如果查詢信息不匹配，雙方還可以得知是對(duì)應(yīng)邊不成比例、或是對(duì)應(yīng)角不相等、亦或是圖不同構(gòu)影響著不相似的結(jié)果，泄露了不該泄露的信息.因此，隱匿圖形頂點(diǎn)數(shù)和邊數(shù)的保密圖形相似性判定問題亟待研究.

本文主要研究隱匿頂點(diǎn)數(shù)和邊數(shù)的保密圖形相似性判定問題，隱匿參與方圖形頂點(diǎn)數(shù)和邊數(shù)的核心問題是如何實(shí)現(xiàn)隱匿維數(shù)的保密向量運(yùn)算.主要貢獻(xiàn)如下：

(1)提出一種隱匿向量維數(shù)的保密向量操作方法，該方法不僅可以用于解決隱匿向量維數(shù)的保密向量相等判定和保密向量對(duì)應(yīng)分量成比例判定等問題，還可以用于解決隱匿集合勢(shì)的保密集合相等問題；

(2)采用布爾矩陣的向量編碼方法、隱匿向量位數(shù)的保密向量操作方法和Paillier同態(tài)加密方案設(shè)計(jì)了隱匿頂點(diǎn)數(shù)和邊數(shù)的保密圖形相似性判定協(xié)議.解決了隱匿頂點(diǎn)數(shù)和邊數(shù)的保密圖形相似性判定這一公開問題.

1 預(yù)備知識(shí)

1.1 關(guān)于安全多方計(jì)算協(xié)議的安全性定義

定義 1文獻(xiàn)[3]中關(guān)于一個(gè)安全多方計(jì)算協(xié)議的安全性定義如下：對(duì)于概率多項(xiàng)式函數(shù)f，協(xié)議π可以保密地計(jì)算f(a,b)如果存在概率多項(xiàng)式時(shí)間模擬算法S1與S2使得

1.2 Paillier變體同態(tài)加密方案

本文設(shè)計(jì)的協(xié)議采用Gong等人[15]提出的Paillier變體同態(tài)加密方案，在此將其概述為：

(1)符號(hào)記法:p與q是大素?cái)?shù)，|p|=|q|，n=pq，λ=lcm(p?1,q?1)，g=1+n，；

(2)加密:對(duì)于明文m

(3)對(duì)于密文對(duì)(c1,c2)，其中c1,c2

該方案不僅保持了良好的加法同態(tài)性E(x+y)=E(x)·E(y),E(x×y)=Ey(x)=Ex(y)而且還具有加密底數(shù)可以由無密鑰一方計(jì)算的良好性質(zhì)(此性質(zhì)在安全多方計(jì)算中可以確保無密鑰一方私有數(shù)據(jù)的安全性).該方案在高階剩余類判定性困難假設(shè)下，具有選擇明文攻擊不可區(qū)分安全性[4]，即，其中c0與c1分別是明文m0與m1對(duì)應(yīng)的密文.

2 圖形間的相似性判定

以下四個(gè)協(xié)議的設(shè)計(jì)采用的數(shù)學(xué)常識(shí)為：

設(shè)P(·,·)是謂詞函數(shù)給定有理數(shù)0整數(shù)θ1,θ2∈Zn則有成立.反之，如果那么必有

2.1 保密圖形的同構(gòu)判定問題

隱匿邊數(shù)和頂點(diǎn)數(shù)的保密圖形同構(gòu)判定問題實(shí)質(zhì)是隱匿矩陣維數(shù)的保密圖形對(duì)應(yīng)鄰接矩陣相等判定問題.為了解決隱匿邊數(shù)和頂點(diǎn)數(shù)的保密圖形同構(gòu)判定問題，本節(jié)采用布爾矩陣的向量表示方法先將圖形的鄰接矩陣表示成向量，然后采用隱匿維數(shù)的保密向量運(yùn)算方法解決隱匿邊數(shù)和頂點(diǎn)數(shù)的保密圖形同構(gòu)判定問題.

2.1.1 協(xié)議Π1：保密圖形的同構(gòu)判定協(xié)議

輸出：P(Ma,Mb).

Step 1.Alice先運(yùn)行Paillier變體方案的密鑰生成算法產(chǎn)生公私鑰：公鑰Kpub=(n,g=1+kn)，私鑰λ；

Step 2:Alice和Bob分別按照下述步驟1)和2)工作：

1)公布公鑰后，Alice按照如下方式執(zhí)行協(xié)議：(1)采用布爾矩陣的向量表示法將其私有圖形對(duì)應(yīng)的鄰接矩陣Ma表示成向量μa←(μ1,μ2,···,μka)；

(2)對(duì)于1≤i≤ka，計(jì)算ka個(gè)分向量μi對(duì)應(yīng)的密文modn2；

(3)選擇一個(gè)隨機(jī)數(shù)k1(滿足計(jì)算k1個(gè)1的密文modn2，其中ka

(4)將密文元組(cμ1,cμ2,...,cμk1+ka)發(fā)送給Bob.

2)在Alice加密的同時(shí)，Bob按照如下方式執(zhí)行：

(1)采用布爾矩陣的向量表示法將其私有鄰接矩陣Mb表示成向量νb←(ν1,ν2,···,νkb)；

(2)對(duì)于1≤i≤kb，計(jì)算kb個(gè)分向量νi對(duì)應(yīng)的密文modn2；

(3)選擇一個(gè)隨機(jī)數(shù)2k2+k1+ka?kb?n(滿足kb+k2+k1?ka>0)，計(jì)算2k2+k1+ka?kb個(gè)密文modn2，其中1≤j≤k2；

Step 3.收到(cμ1,cμ2,...,cμk1+ka)后，Bob按照如下方式執(zhí)行：

(1)對(duì)于1≤i≤k1+ka，分別對(duì)(cμ1,cμ2,...,cμk1+ka)對(duì)應(yīng)的k1+ka個(gè)密文分量執(zhí)行同態(tài)操作：

(2)將Step 2中Bob 已經(jīng)計(jì)算好的2k2+k1+ka?kb個(gè)密文modn2，其中1≤j≤2k2+k1+ka?kb)中的k2個(gè)添加到密文組(cμ1,cμ2,...,cμk1+ka)之后，剩余的k2+k1+ka?kb個(gè)添加到密文組(cν1,cν2,...,cνkb)之后，從而得到兩個(gè)新的、等長的有序密文元組，分別記作：(cμ1,cμ2,...,cμk1+k2+ka)和(cν1,cν2,...,cνk1+k2+ka)；

(3)按照如下方式隨機(jī)組織密文對(duì):

i將cμi∈(cμ1,cμ2,...,cμk1+k2+ka)和cν1∈(cν1,cν2,...,cνk1+k2+ka)分別作為第一和第二分量構(gòu)造二元組

ii對(duì)(cμ1,cν1),(cμ2,cν2),...,(cμk1+k2+ka,cνk1+k2+ka)在對(duì)內(nèi)做隨機(jī)置換；

iii將上一步得到的密文對(duì)再做對(duì)間的隨機(jī)置換，并將得到新的密文對(duì)序列記作:

Step 4.Alice收到后按照如下方式進(jìn)行：

2.1.2 協(xié)議Π1的保密性

定理 1在半誠實(shí)模型下，協(xié)議Π1能夠保密地判定兩個(gè)圖形是否同構(gòu).

證明Π1是Alice和Bob協(xié)同計(jì)算函數(shù)：P(Ma,Mb)的協(xié)議，其中他們的輸入分別為各自圖形的鄰接矩陣：與.

下面我們將構(gòu)造符合1.1節(jié)中式(1a)和式(1b)的模擬器

Alice在執(zhí)行協(xié)議Π1的過程中視圖(view)記為：

Alice執(zhí)行協(xié)議后的輸出記為：

下面構(gòu)造模擬器模擬Alice的視圖.

以及Bob的私有圖形Mb，其中則有：

從模擬器收到后，Bob按照如下方式執(zhí)行：

(1)對(duì)于1≤i≤k1+ka，分別對(duì)對(duì)應(yīng)的k1+ka個(gè)密文分量執(zhí)行同態(tài)操作：

(2)將先前已經(jīng)計(jì)算好的2k2+k1+ka?kb個(gè)密文modn2，其中1≤j≤2k2+k1+ka?kb)中的k2個(gè)添加到密文組之后，剩余的k2+k1+ka?kb個(gè)添加到密文組之后，從而得到兩個(gè)新的、等長的有序密文元組，分別記作

(3)按照如下方式隨機(jī)組織密文對(duì):

iii將上一步得到的密文對(duì)再做對(duì)間的隨機(jī)置換，并將得到新的密文對(duì)序列記作:和

綜上所述，可以構(gòu)造一個(gè)滿足：

類似地，也可以構(gòu)造一個(gè)滿足：

2.2 兩圖形對(duì)應(yīng)邊成比例與否的保密判定

本節(jié)采用隱匿維數(shù)的保密向量運(yùn)算方法解決隱匿邊數(shù)的保密圖形對(duì)應(yīng)邊是否成比例判定問題.

2.2.1 協(xié)議Π2：對(duì)應(yīng)邊是否成比例的保密判定協(xié)議

輸入：Alice輸入邊長向量=(a1,a2,...,aka)，Bob輸入邊長向量=(b1,b2,...,bkb)，系統(tǒng)安全參數(shù)‘(系統(tǒng)中可接受(一方面考慮到協(xié)議執(zhí)行效率)的最大邊數(shù))和‘0，其中ka,kb<‘，‘0?n用于限定雙方總共可以引入的隨機(jī)輸入(這些隨機(jī)輸入用于隱藏雙方頂點(diǎn)數(shù)或邊數(shù)等信息，但不影響保密計(jì)算的結(jié)果的正確性).

Step 1:Alice先運(yùn)行Paillier變體方案的密鑰生成算法產(chǎn)生公私鑰：公鑰(n,g=1+kn)，私鑰λ；

Step 2:Alice和Bob分別按照步驟1)和2)執(zhí)行協(xié)議：

1)發(fā)布公鑰后Alice按照如下方式工作

(1)將有理數(shù)形式的邊長向量的各分量表示成分?jǐn)?shù)，然后將這些分量的分子和分母分別表示成向量；

(2)對(duì)于1≤i≤ka，計(jì)算2ka個(gè)邊長對(duì)應(yīng)的密文modn2，其中

(3)選擇一個(gè)隨機(jī)數(shù)k1(滿足計(jì)算2k1個(gè)1的密文modn2，=modn2，其中

2)在Alice加密的同時(shí)，Bob按照如下方式執(zhí)行:

(1)將有理數(shù)形式的邊長向量的各分量表示成分?jǐn)?shù)，然后將這些分量的分子和分母分別表示成向量

(2)選擇一個(gè)隨機(jī)數(shù)k2?n(滿足并且k1+ka+k2?kb>0)，計(jì)算2k2個(gè)密文modn2，其中1≤j≤k2.

Step 3.收到Alice發(fā)來的后，Bob按照如下方式執(zhí)行：

(1)對(duì)于1≤i≤kb，分別對(duì)的前kb個(gè)密文執(zhí)行同態(tài)操作

(2)對(duì)于(kb+1)≤i≤(k1+ka)，分別對(duì)和的后k1+ka?kb個(gè)密文執(zhí)行同態(tài)操作

(3)將Step 2中Bob已經(jīng)計(jì)算好的2k2個(gè)密文modn2，其中1≤j≤k2)平分成兩份，并分別添加到密文組之后，得到兩個(gè)新的有序密文元組；

(4)隨機(jī)組織密文對(duì):

ii先對(duì)上步得到的k1+ka+k2個(gè)密文對(duì)實(shí)施對(duì)內(nèi)隨機(jī)置換；

iii對(duì)已經(jīng)實(shí)施對(duì)內(nèi)隨機(jī)置換的k1+ka+k2個(gè)密文對(duì)再實(shí)施對(duì)間隨機(jī)置換，并將得到的密文對(duì)序列記作:；

Step 4.Alice收到后按照如下方式進(jìn)行：

2.2.2 協(xié)議Π2的私密性

定理 2在半誠實(shí)模型下，Alice和Bob利用協(xié)議Π2能夠保密地判定他們私有圖形對(duì)應(yīng)邊是否成比例.

證明Π2是Alice和Bob協(xié)同計(jì)算函數(shù)P()的協(xié)議，其中他們的輸入分別為各自圖形的邊向量：=(a1,a2,...,aka)與=(b1,b2,...,bkb).

下面我們將構(gòu)造符合1.1節(jié)中式(1a)和式(1b)的模擬器.

Alice執(zhí)行協(xié)議Π2時(shí)的視圖(view)記為：

Alice執(zhí)行協(xié)議Π2的輸出記為：

下面構(gòu)造模擬Alice視圖的模擬器.

模擬器的輸入為：隨機(jī)選取一個(gè)具有個(gè)有理分量的向量以及Bob的私有圖形對(duì)應(yīng)的邊長向量=(b1,b2,...,bkb)，其中.則有：

(1)對(duì)于1≤i≤kb，分別對(duì)和的前kb個(gè)密文執(zhí)行同態(tài)操作=

(2)對(duì)于(kb+1)≤i≤(k1+ka)，分別對(duì)和的后k1+ka?kb個(gè)密文執(zhí)行同態(tài)操作上述兩步完成后，得到兩個(gè)新的有序密文元組和

(3)將先前已經(jīng)計(jì)算好的2k2個(gè)密文modn2，其中1≤j≤k2)平分成兩份，并分別添加到密文組之后，從而得到兩個(gè)新的有序密文元組

(4)隨機(jī)組織密文對(duì):

ii對(duì)k1+ka+k2個(gè)密文對(duì)實(shí)施對(duì)內(nèi)隨機(jī)置換；

iii將上一步得到的密文對(duì)再實(shí)施對(duì)間隨機(jī)置換，并將得到新的密文對(duì)序列記作:

綜上所述，可以構(gòu)造一個(gè)滿足：

類似地，也可以構(gòu)造一個(gè)滿足：

2.3 對(duì)應(yīng)角相等與否的保密判定問題

2.3.1 協(xié)議Π3：對(duì)應(yīng)角相等與否的保密判定協(xié)議

輸入：Alice輸入角向量∠=(∠A1,∠A2,...,∠Aka)，Bob輸入角向量∠(∠B1,∠B2,...,∠Bkb).

Step 1.Alice先運(yùn)行Paillier變體方案的密鑰生成算法產(chǎn)生公私鑰：公鑰(n,g=1+kn)，私鑰λ；

Step 2.

1)Alice公布公鑰后按照如下方式執(zhí)行

(1)將有理數(shù)形式的邊長向量的各分量表示成分?jǐn)?shù)，然后將這些分量的分子和分母分別表示成向量；

(2)對(duì)于1≤i≤ka，計(jì)算2ka個(gè)邊長對(duì)應(yīng)的密文

(3)選擇一個(gè)隨機(jī)數(shù)k1(滿足計(jì)算2k1個(gè)1的密文=modn2，其中ka

2)在Alice加密的同時(shí)，Bob按照如下方式執(zhí)行:

(1)將有理數(shù)形式的邊長向量的各分量表示成分?jǐn)?shù)，然后將這些分量的分子和分母分別表示成向量

(2)選擇一個(gè)隨機(jī)數(shù)k2?n(滿足計(jì)算2k2個(gè)密文modmodn2，其中1≤j≤k2.

Step 3.收到Alice發(fā)來的和后，Bob按照如下方式執(zhí)行：

(1)對(duì)于1≤i≤kb，分別對(duì)的前kb個(gè)密文執(zhí)行同態(tài)操作modn2=modn2；

(2)對(duì)于(kb+1)≤i≤(k1+ka)，分別對(duì)的后k1+ka?kb個(gè)密文執(zhí)行同態(tài)操作modn2=(1+modn2；由上述兩步得到兩個(gè)新的有序密文元組；

(3)將先前Step 2中已經(jīng)計(jì)算出的2k2個(gè)密文其中ka

(4)隨機(jī)組織密文對(duì):

iii再對(duì)上一步得到的密文對(duì)實(shí)施對(duì)間隨機(jī)置換，并將得到新的密文對(duì)序列記作:

Step 4.Alice收到后按照如下方式進(jìn)行：

2.3.2 協(xié)議Π3的保密性

定理 3在半誠實(shí)模型下，協(xié)議Π3能夠保密地判定兩個(gè)圖形對(duì)應(yīng)角是否相等.

證明:Π3是Alice和Bob協(xié)同計(jì)算函數(shù)P(∠∠)的協(xié)議，其中他們的輸入分別為各自圖形的角向量：∠=(∠A1,∠A2,...,∠Aka)與∠=(∠B1,∠B2,...,∠Bkb).

本定理以下部分的證明和定理2基本上一樣，為了節(jié)省篇幅在此不再贅述.采用定理2的構(gòu)造方法構(gòu)造模擬器滿足：

2.4 圖形間的相似性判定

保密圖形相似性判定問題：Alice和Bob分別有一個(gè)私有圖形Ga與Gb，二人想?yún)f(xié)同判定兩個(gè)圖形是否相似，但不泄露各自的頂點(diǎn)數(shù)或邊數(shù)在內(nèi)的圖形信息(邊、角、鄰接矩陣).協(xié)議的基本思想：協(xié)議Π4同時(shí)調(diào)用協(xié)議Π1、Π2和Π3，實(shí)現(xiàn)保密圖形相似性判定.

雙方如何形成相同的圖形拓?fù)潢P(guān)系，即構(gòu)成對(duì)應(yīng)邊、對(duì)應(yīng)角和對(duì)應(yīng)矩陣：雙方保密圖形的對(duì)應(yīng)需要根據(jù)實(shí)際應(yīng)用而定，比方說在保密地理信息匹配應(yīng)用中可以指定某個(gè)地點(diǎn)所在的邊為起始邊，然后按照該地點(diǎn)的南向?yàn)槟鏁r(shí)針走向的起始方向依次編排邊向量.以下都假定雙方已經(jīng)在具體應(yīng)用中已經(jīng)確定了圖形的拓?fù)潢P(guān)系.

協(xié)議Π4：圖形間的相似性保密判定

輸入：Alice輸入各邊長構(gòu)成的元組(a1,a2,...,aka)、各角大小構(gòu)成的元組(∠A1,∠A2,...,∠Aka)以及圖的鄰接矩陣對(duì)應(yīng)的向量表示(μ1,μ2,···,μka)；Bob輸入邊長向量(b1,b2,...,bkb)、角向量(∠B1,∠B2,...,∠Bkb)以及圖的鄰接矩陣對(duì)應(yīng)的向量表示(ν1,ν2,···,νkb)；系統(tǒng)安全參數(shù)‘(系統(tǒng)中可接受(一方面考慮到協(xié)議執(zhí)行效率)的最大邊數(shù))和‘0，其中ka,kb<‘，‘0?n用于限定雙方總共可以引入的隨機(jī)輸入(這些隨機(jī)輸入用于隱藏雙方頂點(diǎn)數(shù)或邊數(shù)等信息，但不影響保密計(jì)算結(jié)果的正確性).

輸出：如果兩個(gè)圖形相似，則置T=1，否則，置T=0.

Step 1:輸入安全參數(shù)1n,‘,‘0；

Step 2:調(diào)用協(xié)議1、協(xié)議2和協(xié)議3，并計(jì)算+P(Ma,Mb)；

協(xié)議Π4的保密性

定理 4在半誠實(shí)模型下，如果協(xié)議Π1、Π2以及Π3能夠各自的保密計(jì)算任務(wù)，則協(xié)議Π4能夠?qū)崿F(xiàn)保密圖形相似性判定.

證明協(xié)議Π4實(shí)質(zhì)是Alice和Bob協(xié)作保密計(jì)算=P()+P(∠∠)+P(Ma,Mb).這就是說，協(xié)議Π4的私密性完全依由協(xié)議Π1、Π2和Π3決定，考量Π4的私密性就是要看計(jì)算P()、P(∠∠)和P(Ma,Mb))時(shí)，有無造成Alice和Bob雙方信息泄露.

因?yàn)槲覀円呀?jīng)證明：在半誠實(shí)模型下，協(xié)議Π1能夠保密判定兩個(gè)圖形是否同構(gòu)、Π2能夠保密判定兩個(gè)圖形對(duì)應(yīng)邊是否成比例、Π3能夠保密判定兩個(gè)圖形的對(duì)應(yīng)角是否相等；即協(xié)議Π4的輸入P()、P(∠∠)與P(Ma,Mb)沒有造成參與各方信息的泄露，所以采用Π4計(jì)算=P()+P(∠∠)+P(Ma,Mb)不會(huì)造成Alice和Bob雙方私有圖形信息的泄露.因此，定理4成立.

3 性能對(duì)比分析

本文研究的是隱匿頂點(diǎn)數(shù)和邊數(shù)的保密圖形判定問題，在此之前沒有這方面的研究，因此在效率方面與先前的保密圖形相似判定協(xié)議不具有可比性.在安全性方面，最新研究成果[21]雖然很好地解決了圖形相似判定問題中的隱私保護(hù)問題，我們發(fā)現(xiàn)以hash函數(shù)抗碰撞性做為用戶信息安全的保障保密圖形相似協(xié)議的安全性還可以進(jìn)一步提高：hash函數(shù)通常被用于信息認(rèn)證和數(shù)字簽名中，通常將非定長信息映射為定長信息，而成果[21]中用hash函數(shù)將定長圖形信息映射為另一定長信息，這種情形難于抵抗攻擊者暴力破解圖形私密信息；而本文采用基于高階剩余類困難問題Paillier變體同態(tài)加密方案為保密工具，可以抵抗敵手暴力破解圖形私密信息；此外，協(xié)議[21]只適用于解決頂點(diǎn)數(shù)相同，即協(xié)議執(zhí)行之初就已經(jīng)泄露了參與方的頂點(diǎn)數(shù)、邊數(shù)信息，而本文協(xié)議不會(huì)造成參與各方頂點(diǎn)數(shù)、邊數(shù)信息的泄露.表1是協(xié)議[21]和本文協(xié)議在保密向量操作是否泄露向量的維數(shù)、解決問題的程度(以隱匿頂點(diǎn)數(shù)和邊數(shù)體現(xiàn))以及二者所采用的保密工具三個(gè)方面的對(duì)比：

表1 本文協(xié)議與協(xié)議[21]的對(duì)比分析

4 結(jié)束語

本文首先設(shè)計(jì)一種隱匿向量維數(shù)的保密向量操作方法，然后采用這兩種方法與Paillier同態(tài)變體加密方案，設(shè)計(jì)了一個(gè)隱匿雙方頂點(diǎn)數(shù)和邊數(shù)的保密圖形相似判定協(xié)議.該協(xié)議由隱匿鄰接矩陣維數(shù)的保密圖形同構(gòu)判定協(xié)議、隱匿頂點(diǎn)數(shù)的保密圖形對(duì)應(yīng)角相等判定協(xié)議和隱匿邊數(shù)的保密圖形對(duì)應(yīng)邊成比例判定協(xié)議三個(gè)子協(xié)議組成.較之于采用Hash函數(shù)設(shè)計(jì)的協(xié)議，本文設(shè)計(jì)的協(xié)議具有隱匿頂點(diǎn)數(shù)的優(yōu)點(diǎn)，更符合地理信息系統(tǒng)和社交網(wǎng)絡(luò)用戶隱私保護(hù)的需求.