于寶華，鞏林明

0 引言

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

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

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

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

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

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

1 預備知識

1.1 關于安全多方計算協(xié)議的安全性定義

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

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

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

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

(2)加密:對于明文m

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

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

2 圖形間的相似性判定

以下四個協(xié)議的設計采用的數(shù)學常識為：

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

2.1 保密圖形的同構判定問題

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

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

輸出：P(Ma,Mb).

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

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

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

(2)對于1≤i≤ka，計算ka個分向量μi對應的密文modn2；

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

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

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

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

(2)對于1≤i≤kb，計算kb個分向量νi對應的密文modn2；

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

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

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

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

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

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

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

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

Step 4.Alice收到后按照如下方式進行：

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

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

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

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

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

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

下面構造模擬器模擬Alice的視圖.

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

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

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

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

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

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

綜上所述，可以構造一個滿足：

類似地，也可以構造一個滿足：

2.2 兩圖形對應邊成比例與否的保密判定

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

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

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

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

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

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

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

(2)對于1≤i≤ka，計算2ka個邊長對應的密文modn2，其中

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

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

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

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

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

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

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

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

(4)隨機組織密文對:

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

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

Step 4.Alice收到后按照如下方式進行：

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

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

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

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

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

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

下面構造模擬Alice視圖的模擬器.

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

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

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

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

(4)隨機組織密文對:

ii對k1+ka+k2個密文對實施對內(nèi)隨機置換；

iii將上一步得到的密文對再實施對間隨機置換，并將得到新的密文對序列記作:

綜上所述，可以構造一個滿足：

類似地，也可以構造一個滿足：

2.3 對應角相等與否的保密判定問題

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

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

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

Step 2.

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

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

(2)對于1≤i≤ka，計算2ka個邊長對應的密文

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

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

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

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

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

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

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

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

(4)隨機組織密文對:

iii再對上一步得到的密文對實施對間隨機置換，并將得到新的密文對序列記作:

Step 4.Alice收到后按照如下方式進行：

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

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

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

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

2.4 圖形間的相似性判定

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

雙方如何形成相同的圖形拓撲關系，即構成對應邊、對應角和對應矩陣：雙方保密圖形的對應需要根據(jù)實際應用而定，比方說在保密地理信息匹配應用中可以指定某個地點所在的邊為起始邊，然后按照該地點的南向為逆時針走向的起始方向依次編排邊向量.以下都假定雙方已經(jīng)在具體應用中已經(jīng)確定了圖形的拓撲關系.

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

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

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

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

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

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

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

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

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

3 性能對比分析

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

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

4 結束語

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