路徑點包含安全兩方計算問題的求解

姚清芳，林柏鋼

（福州大學 數學與計算機科學學院，福建 福州 350108）

0 引言

自從姚期智[1]1982年首先通過“百萬富翁命題”提出了安全兩方計算問題，1987年戈德里克[2]等人又考慮了安全多方計算問題以來，安全多方計算也成為了國際密碼學界研究的熱點問題之一。但是因為效率的問題限制，采用通用解決方案解決某些具體的多方安全計算問題是不現實的，必須針對不同的應用對象研究高效的解決方案。

多方安全計算中集合點包含和幾何點包含等方法都是近幾年密碼學研究的一個熱點問題[3-4]。提出的路徑點包含問題是多方安全計算中一個新的研究課題。主要研究如何安全計算特定條件下兩條或者多條路徑之間的公共路徑關系，通過特殊編碼把路徑和集合對應起來，再利用集合的方法求出了兩路徑的公共路徑。最后分析證明了新方案的安全性。

1 預備知識

1.1 連接運算

這里定義一種字符串連接運算Concat,設為C()∶

其中 z = C(u1, u2, u3,… ,um)，( u1, u2,u3,… ,um)為字符串集合；z=C(u1, u2, u3,… ,um)就是把字符串 ( u1, u2,u3,… ,um)一個跟著一個放在一起得到的新字符串。連接運算不僅保存了元素的信息還保存了元素間的順序關系。

1.2 安全性考慮

提出的新方案都是建立在半誠實參與者基礎上的。即，參與者在協議執行過程中嚴格地進行協議操作，但是他們會保留協議中的中間結果來推導其他參與者的輸入。

安全性的定義：假設計算的雙方是 A和 B。設f= ( f1,f2)是一個概率多項式時間函數，p是計算f的雙方計算協議。當輸入為(x,y)時，第 i方在執行協議中得到的信息序列viewi(x,y)為，v (x,y) = ( x,ri,, … ,mi)。其中ri表示

定義1 對于一個函數f，如果存在概率多項式時間算法S1,S2使得：

其中符號“≡”表示計算不可區分，則認為p保密地計算f。如果要證明一個方案是保密的，就必須構造出滿足這個式子的模擬器S1,S2[5]。

2 新方案原理描述

問題描述：假設有兩條路徑 G1∶x1→ x2→…→xn，G2∶y1 → y 2→…→y m ，其中 ( x 1 , x2,… ,x n), (y1,y2,… ,ym)為路徑上的點，箭頭表示路徑的方向。現在問題是需要計算出G1,G2的公共路徑而不泄漏G1, G2的信息。

如圖1所示，有兩條路徑G1∶A→C→F→H→Z，G2∶C→F →H→K→P ，需要安全的計算出G1, G2的公共路徑C→F→H。

圖1 G1, G2路徑示意

2.1 基本思想

對路徑進行特殊編碼，把路徑包含問題轉化為集合包含問題，利用求集合交集得到兩路徑的公共路徑。

2.2 問題分析

情形 1：G1,G2中任意兩個點不相同，即每個點只經過一次

解決方案一：

①先對路徑的點按照約定的規則進行數字化，對 G1,G2作如下編碼：

這樣A,B集合中的元素為G1,G2中所有長度為2的路徑編碼；

②連接運算。對A,B作連接運算：

注意連接時，以最大值的位數為準，少于位數的補0，例如：最大值的位數為3，x1=20,x2=2, x1x2=02000。這樣就確保了連接完編碼的唯一性；

③利用集合交集的保密計算[4]：

A，B都得到： Eb( Ea(A′))和 Ea( Eb(B′))，A，B各自計算：C = Eb(Ea(A′))∩Ea(Eb(B′))，求出的C為G1,G2中所有長度為2的公共路徑。因為每個點只經過一次，所以把C中頭尾相等的點拼在一起即可求出G1,G2的所有公共路徑。

情形2：G1,G2中每個點可經過多次。

解決方案二：

①先對路徑的點進行數字化，然后編碼如下：

該編碼實質是得到G1,G2中所有長度≥2的路徑；

②同樣對他們進行鏈接運算：

③因為位數太長了，所以對他們進行HASH運算：

④利用集合交集的保密計算：

A,B都得到：Eb(Ea(A′))和Ea(Eb(B′))，

A,B各自計算：C = Eb(Ea(A′))∩Ea(Eb(B′))，C為G1,G2中所有長度≥2的公共路徑。

情形3: G1,G2中點可以經過多次，但是只需求最長的公共路徑

解決方案三：

當只需求兩路徑中最長的公共路徑時，可以利用以下方案(方案三)減少時間復雜度。方案二中，把所有長度≥2的路徑一次性全部拿去判斷，這里進行了一些粗略的判斷，例如當不存在長度為 k的公共路徑時，就不必判斷那些長度≤k的路徑了。而方案三是在[1, min(n, m)]這個區間內利用二分思想進行交互，先交互長度為 m in(n, m)/2的路徑，看看是否有，如果有則繼續判斷是否有長度為3·min(n,m)/4的路徑；若沒有的話，判斷長度為 m in(n, m)/4的路徑，就這樣一直循環下去。這里的長度都需要取下整數。

循環停止的情況有兩種，一種是求出的交集里面只有1個元素，這個時候該元素就為最長的公共路徑；還有一種是取整完之后該長度的交集已經求過了，這個時候操作到了二分的終點，取最近求得的存在的長度路徑。這樣停止的時候就可以求出最長的公共路徑。結果可極大的減少了時間復雜度，但是增加了通信復雜度。

2.3 性能分析

方案一中A,B集合的元素個數為n，編碼、連接運算和集合交集保密計算的時間復雜度都是 O(n)，總共的時間復雜度為O(n)。通信復雜度是集合交集保密計算的通信復雜度為2。

方案二中因A,B集合中的元素個數為O(n2)，總共的時間復雜度為 O(n2)。通信復雜度也為 2。這里用到了 HASH運算，但是匹配錯誤的概率是可忽略的。

方案三中利用二分思想，時間復雜度可以由O(n2)降為O(n·log2n)，但是用到了O(log2n)次的交互，所以通信復雜度為O(log2n)。

綜上所述，表1給出3種方案的時間復雜度和空間復雜度的比較。

表1 各方案的復雜度比較

在安全性方面，只要上述方案的零知識的，則方案的安全性等價于集合交集中所用的同態公鑰體制的安全性，零知識的證明將在下面統一給出。

3 安全性證明

直觀上看，因為A和B都不知道對方的密鑰，都無法獲得對方的路徑信息，如果要知道對方的路徑信息就必須獲得對方的密鑰，假定雙方的密鑰都是安全的，那么該方案就是保密的。下面針對方案一進行以下定理證明。

定理1 解決路徑點包含兩方問題的方案一是保密的。證明：證明的思路是通過構造模擬器S1,S2使得：

來證明方案的安全性。

在協議的執行過程中，A和 B觀察到的過程與輸出分別為：

構造兩個模擬器 S1,S2分別用于模擬 v1(A,B ) )和v2(A,B)。

首 先 構 造 S1， 使 得 ｛S1( A,f1( A,B ) ), f2(A,B ) ｝≡｛v1(A,B),o2(A,B ) ｝。

S1的模擬過程如下：

S1首先選擇一個可交換加密算法 E和加密密鑰 a,并根據硬幣拋擲的結果 ( r1)′選擇另一個密鑰b′,根據A和B的公共路徑C，生成一個新的路徑對它進行編碼使得 C中的元素與 D中前面的元素相等。對它進行連接運算得到的對A進行連接運算得到A′。

S1用a加密A′得到 Ea(A′),用 b′對 D′加密得到 Eb′(D ′)。

S1用a加密得到，再用b′對加密,得到

S1單獨比較 Ea(′(D′))和′ ((A′))，根據前面構造A 和 D′的 方 法 ， 一 定 存 在 交 集 C 使 得，從而得出A∩B=C，C對應的路徑集合為G1,G2的公共路徑。.

不妨令：

則有：

又因：

所以：

類似的可以構造一個模擬器 S2,使得：｛f1(A,B),S2( A, f2( A,B ) )｝ ≡｛o1(A ,B),v2(A,B)｝滿足條件成立，這樣就完成了定理的證明。同理，方案二、方案三的安全性證明類似方案一。

5 結語

針對路徑點包含問題的兩種不同的情況提出了幾種解決方案，應用時可根據具體的應用環境選擇方案。后續的工作可以圍繞在不提高通信復雜度的情況下降低針對第二種情況下的時間復雜度，以及把兩方計算擴展到多方計算，提出路徑點包含安全多方計算的高效解決方案算法。

[1] YAO A. Protocols for Secure Computations[C]Los Alamitos: IEEE Computer Society Press, 1982:160-164

[2] GOLDREICH O,MICALI S,WIGDERSON A. How to Play ANY Mental Game[C].United States:ACM,1987:218-229.

[3] LUO Y L, HUANG L S, ZHONG H. Secure Two-party Point-circle Inclusion Problem[J].Journal of Computer Science and Technology,2007,22(01):88-91.

[4] 李順東,司天歌,戴一奇. 集合包含與幾何包含的多方保密計算[J].計算機研究與發展,2005,42(10):1647-1653.

[5] GOLDWASSER S. Multi-party Computations: Past and Present[D]Santa Barbara CA：[s.n.],1997.