導(dǎo)航：安全管理網(wǎng)>> 安全論文>> 電力安全論文>>正文

安全兩方線段求交協(xié)議及其在保護隱私凸包交集中的應(yīng)用

文檔作者：孫茂華1,2 羅守山1,2,3 辛陽1,2 楊義先1,2 文檔來源： 1.北京郵電大學(xué) 2.北京郵電大學(xué) 3.北京安碼科技有限公司		點擊數(shù)：	更新時間： 2021年04月06日
下載地址：點擊這里	文件大小： 789.38 KB 共13頁	文檔格式： PDF	下載點數(shù)： 1 點（VIP免費）

全屏查看

內(nèi)容預(yù)覽 [文件共13頁]

本文件共13頁，如需編輯使用，請下載。

注：預(yù)覽效果可能會出現(xiàn)部分文字亂碼（如口口口）、內(nèi)容顯示不全等問題，下載是正常的。

	文件大?。?89.38 KB 共13頁文件格式：PDF 下載點數(shù)：1 點（VIP會員免費）

下一篇：太陽能電池用鍺單晶片加工廢料綜合回收利…

上一篇：基于分離信源信道碼的相關(guān)信源在有噪廣播…

文本預(yù)覽

僅提取頁面文字內(nèi)容，供快速閱讀使用。

2013 年1 月 Journal on Communications January 2013
第34 卷第1 期 通 信 學(xué) 報 Vol.34 No. 1
安全兩方線段求交協(xié)議及其在保護隱私凸包交集中的應(yīng)用
孫茂華1,2，羅守山1,2,3，辛陽1,2，楊義先1,2
(1.北京郵電大學(xué) 信息安全中心，北京 100876；2.北京郵電大學(xué) 災(zāi)備技術(shù)國家工程實驗室，北京 100876；
3.北京安碼科技有限公司，北京 100876)
摘 要：研究了現(xiàn)有安全多方計算幾何協(xié)議，提出了安全多方計算幾何的模型和框架，從數(shù)學(xué)模型、安全模型和
通信模型3 個維度展開描述。針對現(xiàn)有安全兩方線段關(guān)系判定協(xié)議都忽略求解交點坐標的問題，在半誠實模型下
基于Paillier 同態(tài)加密技術(shù)提出了安全兩方線段求交協(xié)議，使用Goldreich 證明法進行了理論安全性分析，并在惡
意模型下進行了推廣。分析結(jié)果表明，該半誠實模型下的算法在效率上優(yōu)于現(xiàn)有算法。作為安全兩方線段求交協(xié)
議的應(yīng)用，結(jié)合O’Rourke 算法提出了保護隱私的凸包求交集協(xié)議，彌補了安全計算幾何領(lǐng)域僅實現(xiàn)了凸包并集
算法的缺陷。
關(guān)鍵詞：密碼學(xué)；安全多方計算幾何；安全兩方線段求交；保護隱私；凸包交集
中圖分類號：TN918.1 文獻標識碼：A 文章編號：1000-436X(2013)01-0030-13
Secure two-party line segments intersection scheme and its
application in privacy-preserving convex hull intersection
SUN Mao-hua1,2, LUO Shou-shan1,2,3, XIN Yang1,2, YANG Yi-xian1,2
(1. Information Security Center，Beijing University of Posts and Telecommunications, Beijing 100876, China;
2. National Engineering Laboratory for Disaster Backup and Recovery, Beijing University of Posts and Telecommunications, Beijing 100876, China;
3. Beijing Safe-Code Technology Co.,Ltd. , Beijing 100876, China)
Abstract: The model and framework of secure multi-party computational geometry were presented based on the existing
protocols. The new framework has three dimensions, the math model, the security model and the communication model.
Using the new model and framework, a secure two-party line segments intersection protocol based on Paillier homomorphic
encryption scheme is proposed. This protocol solves the problem that the existing secure two party intersect-
determination schemes of line segments cannot output the exact coordinates of the intersection. The security of the
protocol is demonstrated using Goldreich method. The results show that this protocol has better efficiency than the existing
ones. In addition, the secure two-party line segments intersection in malicious model is also designed. As an application,
a privacy-preserving convex hull intersection protocol is proposed based on the O’Rourke scheme. This application
makes up for the gap in privacy-preserving convex hull intersection protocol in the area of secure multi-party computational
geometry.
Key words: cryptography; secure multi-party computational geometry; secure two-party line segments intersection
scheme; privacy-preserving; convex hull intersection scheme
1 引言
隨著信息技術(shù)的推廣，越來越多的機構(gòu)采用信
息技術(shù)實現(xiàn)辦公和通信。不同機構(gòu)之間利用信息技
術(shù)進行合作，但是，在合作過程中，出于利益考慮，
機構(gòu)往往不愿意透露自己的商業(yè)信息，這就為合作
的順利進行帶來了不便。考慮如下2 個問題，問題
1：戰(zhàn)爭期間，A 國和B 國都打算在C 國修建鐵路。
在鐵路完工之前，修建路線是保密的。為了防止將
來發(fā)生火車相撞，A 國和B 國希望在不泄露自己路
收稿日期：2012-07-13；修回日期：2012-11-20
基金項目：國家自然科學(xué)基金資助項目（61121061, 61161140320）
Foundation Item: The National Natural Science Foundation of China (61121061, 61161140320)
doi:10.3969/j.issn.1000-436x.2013.01.004
第1 期 孫茂華等：安全兩方線段求交協(xié)議及其在保護隱私凸包交集中的應(yīng)用 ·31·
線的前提下，確定2 條路線是否有交匯，并根據(jù)交
匯位置進行協(xié)商談判。問題2：跨國公司A 和B 都
打算在C 國拓展新市場，兩公司分別擬定了其在C
國展開業(yè)務(wù)的新區(qū)域，并作為一級商業(yè)機密保護。
現(xiàn)在，兩公司希望在不泄露各自區(qū)域信息的前提下
確定新區(qū)域是否有重合以及重合區(qū)域的信息。
上述問題本質(zhì)上是在分布式環(huán)境下，不同參與
方在不泄露自己私有信息的前提下共同完成某種
計算。為了解決這些問題，安全多方計算(SMC,
secure multi-party computation)應(yīng)運而生。
安全多方計算是指在分布式網(wǎng)絡(luò)中，多個用戶
在不泄露自己秘密的情況下，以自己的秘密作為輸入
共同計算某個函數(shù)[1]。Yao 在文獻[2]中首次提出了安
全兩方計算協(xié)議。后來，Goldreich 對SMC 做了比較
完整的總結(jié)，并提出了SMC 的安全性定義[3]。近幾
年來，安全多方計算取得了眾多研究成果[4~20]。文
獻[4]中構(gòu)造了一種安全多方計算協(xié)議用于分享公
共安全網(wǎng)絡(luò)中的秘密信息。文獻[5]中利用秘密共享
構(gòu)造了一種安全多方排序協(xié)議，該協(xié)議可在一定程
度上同時抵抗主動和被動敵手攻擊。劉文等利用
ElGamal 密碼體制解決了安全多方數(shù)據(jù)排序問題[6]。
文獻[7]中利用安全多方計算技術(shù)，針對可嵌套共
謀，提出可信防共謀協(xié)議模型。2011 年，Maheshwari
和Kiyawat 將安全多方計算和云計算結(jié)合，提出了
安全多方云計算的概念、應(yīng)用場景和框架結(jié)構(gòu)[8]。
2012 年，Dima 等利用安全多方計算實現(xiàn)了數(shù)據(jù)挖
掘中的? ? differential隱私保護[9]。2012 年，Wang
等研究了安全多方計算中的惡意模型，提出了制約
性反攻擊的概念，保證了惡意模型下安全多方計算
協(xié)議的安全性[10]。Goldreich 等基于密碼學(xué)安全模型
提出了可以計算任意函數(shù)的安全多方計算協(xié)議[11]。
理論上講，任何安全多方計算問題都可以使用電路
估值方案解決。但是，出于效率和復(fù)雜度的考慮，
這種方案在實際應(yīng)用中并不可行。針對不同應(yīng)用環(huán)
境，需要研究不同的解決方案。
作為安全多方計算在計算幾何領(lǐng)域的應(yīng)用，安
全多方計算幾何的概念首先由Mikhail 等提出[12]。安
全多方計算幾何是指在分布式環(huán)境中多方共同解
決計算幾何問題，計算結(jié)束后，除了結(jié)果信息外各
參與方不能獲知額外的信息。目前，安全多方計算
幾何主要研究下列四類問題：點包含問題、多邊形
相交問題、最近點對問題以及凸包問題。文獻[13]
基于Monte Carlo 方法和Cantor 編碼分別設(shè)計了判
斷任意幾何圖形點包含問題協(xié)議以及判斷任意幾
何圖形相交、包含關(guān)系的協(xié)議。文獻[14]提出了安
全兩方向量叉積協(xié)議和安全兩方三點叉積協(xié)議，并
在此基礎(chǔ)上實現(xiàn)了安全兩方點包含協(xié)議。文獻[15]
基于坐標系秘密交換協(xié)議和不同坐標系下兩點距
離計算協(xié)議，首次解決了不同坐標系下圓是否包含
點的判定問題。文獻[16]基于茫然傳輸實現(xiàn)了可以
判定2 個任意多邊形以及2 個任意幾何圖形相交關(guān)
系的協(xié)議。文獻[17]設(shè)計了一個蒙特卡洛偏真算法，
用于判斷多邊形的位置關(guān)系。文獻[18]解決了安全
多方最近點對問題，但是引入了茫然第三方，因此
該協(xié)議的實用性不高。文獻[19]基于向量差最小值
協(xié)議和同態(tài)加密方案實現(xiàn)了安全多方最近點對協(xié)
議，協(xié)議效率高于文獻[18]，且不需要茫然第三方
的參與。文獻[20]基于Graham 算法、安全叉積協(xié)議、
姚氏百萬富翁協(xié)議設(shè)計了一個安全兩方凸包求解
算法。文獻[21]基于裹包法、姚氏百萬富翁協(xié)議、
叉積協(xié)議解決了安全兩方凸包問題。
文獻[12, 13, 16, 17, 22]雖然給出了安全多方線段
求相交協(xié)議，但是只能判斷線段是否有交點，無法計
算交點的坐標信息。因此，不能完全解決問題1。從
文獻[20]和文獻[21]可以看出，目前在凸包運算的隱
私保護研究中，主要解決凸包并集操作，還沒有實現(xiàn)
凸包交集操作的隱私保護。因此，無法解決問題2。
表1 分析了近幾年來提出的安全多方多邊形相
交協(xié)議和安全多方凸包求解協(xié)議的原理和貢獻。
本文首先研究安全多方計算幾何模型和框架，
從數(shù)學(xué)模型、安全模型、通信模型3 個維度展開描
述。為了解決問題1，本文分別提出了半誠實模型
和惡意模型下的安全兩方線段求交協(xié)議，不僅可以
確定2 條線段是否有交點，還可以輸出交點坐標信
息；為了解決問題2，本文首先利用O’Rourke 算法
將求解凸包交集問題轉(zhuǎn)換為求解2 個凸多邊形相交
邊的交點問題，然后利用本文提出的安全兩方線段
求交協(xié)議給出具體的交點坐標。
2 預(yù)備知識
2.1 Goldreich 安全證明法
Goldreich 給出了半誠實模型下安全性證明方法，
被廣泛應(yīng)用在安全多方計算幾何的安全性分析中。
定義1 （Goldreich 安全證明法）[3]
設(shè)* * '* '*
1 1 :{0,1} {0,1} {0,1} {0,1} m m f ?L ? ? ?L ? ，其
中， 1 2 ( , , , ) i m f x x L x 是 1 2 ( , , , ) m f x x L x 的第 i個元素。
·32· 通 信 學(xué) 報 第34 卷
定義
1 2 1 1 2 1 ( , , , ) { ( , , , ), , ( , I m i m ij f x x L x ? f x x L x L f x 2x ,L ,
)} m x 其中， 1 2 { , , , } {1,2, , } j I ? i i L i ? L m 。設(shè)? 為計
算f 的 m 方協(xié)議，當(dāng)輸入為1 2 ( , , , ) m x ? x x L x 時，
第i 方在執(zhí)行? 的過程中得到信息序列
1 2 ( , , i , i , , i )
i i k x r m m L m ，記為 ( ) i view? x ，其中 ri 表示
第i 方獨立的擲幣輸出； i
j m 表示第i 方收到第j 次
的信息。當(dāng)輸入為1 2 ( , , , ) m x ? x x L x 時，執(zhí)行協(xié)議?
以后，第 i 方的輸出結(jié)果記為output (x) i
? 。對于一個
函數(shù)f，如果存在概率多項式時間算法（或者稱為
模擬器 S），使得對于所有的I ?[m]，有
1 2 1 ({0,1}* ) { ( , ( , , , ), ( )), ( )} t m
c
i i i x S I x x x f x f x ? L ?
({0,1}* ) { (), ()} i x m view? x output? x
?
則認為? 秘密計算了f，其中
c?
表示多項式電路計
算不可區(qū)分。要證明一個安全多方計算協(xié)議是安全
的，就必須構(gòu)造滿足上述條件的模擬器S。
該定義可以直觀地理解為對于一個半誠實參
與者，如果可以直接利用自己的輸入與協(xié)議的輸出
通過單獨模擬整個協(xié)議的執(zhí)行過程而得到在執(zhí)行
協(xié)議過程中所能得到的任何信息，那么協(xié)議就能保
證輸入的私密性。如果一個計算協(xié)議能被這樣模
擬，參與者就不能從協(xié)議的執(zhí)行過程中得到有價值
的信息，這樣的協(xié)議就是安全的。
目前，在安全多方計算協(xié)議領(lǐng)域，Goldreich 證
明法是公認的一種安全性證明方式。本文亦采用這
種方法進行安全性證明。
2.2 保護隱私的基礎(chǔ)協(xié)議
2006 年，羅永龍等在文獻[23]中提出了保護隱
私的向量叉積問題，并給出了解決方案，該解決方
案被稱為是保護隱私的向量叉積協(xié)議CPP_V(cross
product protocol for two vector)。
2007 年，羅永龍等又在文獻[22]中提出了保護
隱私的點線叉積問題，并給出了解決方案，該解決
方案被稱為是保護隱私的點線叉積協(xié)議CPP_PL
(cross products protocol for a point with a line)。
羅永龍等在文獻[14]中給出了一個安全兩方點
包含協(xié)議PIP (point inclusion protocol)。該協(xié)議的原
理是如果一個點在一個多邊形內(nèi)，假設(shè)多邊形的邊
按逆時針方向排序，則該點在這個多邊形每一條邊
的左側(cè)。因此只需要利用安全叉積協(xié)議，即可判斷
點是否在多邊形內(nèi)。
2.3 Paillier 加密方案
Paillier 加密方案[24]的安全性依賴于合數(shù)剩余
判定假設(shè)（DCRA, decisional composite residuosity
assumption），即沒有多項式時間算法來區(qū)分一個
模數(shù)是否是模n2 的n 次剩余。具體描述如下。
系統(tǒng)參數(shù)：選取n ? pq，其中 p 與q 為2 個大
素數(shù)。選取隨機整數(shù) g，滿足gcd(l(g modn2),n) ?1 ? ，
則公鑰為(n, g)，私鑰為? (n) ? lcm(( p ?1),(q ?1))，
M 為明文消息。
加密：選擇隨機數(shù)r?Z*p，E(M) ? gmrn mod n2。
解密：
( ) 2
( ) 2
( mod )mod
( mod )
N
N
M L C n n
L g n
?
? ? 。
Paillier 加密方案具有加同態(tài)特性，即1 1 D(E(m,r )?
2 2 1 2 E(m , r )) ? m ? m 。
3 安全多方計算幾何模型和框架
安全多方計算幾何模型（如圖1 所示）可以
描述為一個黑盒子。從盒子外看，各參與方輸入
自己的信息，僅能得到函數(shù)的輸出結(jié)果。而在盒
子內(nèi)部，各參與方進行交互操作，共同計算函數(shù)
的輸出。
一個安全多方計算幾何協(xié)議可以從數(shù)學(xué)模型、
安全模型、通信模型3 個維度展開描述。
表1 安全多方計算幾何相關(guān)研究
類別 文獻 原理 主要貢獻
安全多方多邊
形相交問題
[12] 利用點積協(xié)議和向量控制協(xié)議判斷2 條線段是否相交，
進而判斷2 個多邊形是否相交
首次提出了安全多方計算幾何問題并給出了解決方案
[13] 基于Monte Carlo 方法和Cantor 編碼 可以判斷任意幾何圖形的相交、包含關(guān)系
[16] 基于茫然傳輸協(xié)議 可以判定2 個任意多邊形以及2 個任意幾何圖形的相交關(guān)系
[17] 基于線段相交判定協(xié)議 文章算法是一個蒙特卡洛偏真算法；文章首次實現(xiàn)了安全
多方計算幾何領(lǐng)域中協(xié)議的實驗分析
[22] 基于安全兩方叉積協(xié)議判斷線段是否相交 文獻給出了安全兩方點線叉積協(xié)議，該協(xié)議是安全多方計
算幾何的常用協(xié)議
安全多方凸包
求解問題
[20] 基于Graham 算法、安全叉積協(xié)議、姚氏百萬富翁協(xié)議基于Graham 算法解決了安全凸包問題
[21] 基于裹包法、姚氏百萬富翁協(xié)議、叉積協(xié)議 基于裹包法解決了安全凸包問題
第1 期 孫茂華等：安全兩方線段求交協(xié)議及其在保護隱私凸包交集中的應(yīng)用 ·33·
圖1 計算模型
數(shù)學(xué)模型是指運用數(shù)學(xué)的語言和方法，通過抽
象、簡化建立能近似刻畫并“解決”實際問題的一
種模型。在安全多方計算幾何領(lǐng)域，常用的數(shù)學(xué)模
型有：多邊形求交點模型、多邊形相似的模型、最
近點對模型以及凸包并集模型。
安全模型分為半誠實模型和惡意模型[3]。這2
種安全模型是按照參與者的不同來區(qū)分的。在安全
計算幾何協(xié)議中，參與者分為誠實參與者、半誠實
參與者和惡意參與者。誠實參與者在協(xié)議執(zhí)行過程
中，完全按照協(xié)議要求完成各個步驟，同時保密自
己的所有輸入、輸出以及中間結(jié)果。半誠實參與者
在協(xié)議執(zhí)行過程中，完全按照協(xié)議要求完成各個步
驟，不會中途強行退出或惡意摻入虛假數(shù)據(jù)，但在
協(xié)議執(zhí)行過程中，他們可能會保留所有可以收集到
的關(guān)于其他參與者的信息，以期望在協(xié)議結(jié)束后推
斷出對方的輸入信息或泄露給攻擊者。惡意參與者
在協(xié)議的執(zhí)行過程中，完全按照攻擊者的意志執(zhí)行
協(xié)議的各個步驟，他不但將自己的所有輸入、輸出
以及中間結(jié)果泄露給攻擊者，還可以根據(jù)攻擊者的
意圖改變輸入信息、中間結(jié)果信息，甚至終止協(xié)議。
如果所有參與者都是半誠實或誠實的，稱此模型為
半誠實模型。半誠實模型中的攻擊者都是被動的。
存在惡意參與者的模型稱為惡意模型。惡意模型中
的攻擊者是主動的。
目前，在安全多方計算協(xié)議的研究中，幾乎所
有的協(xié)議都是建立在半誠實模型下。同時，半誠實
模型下的各種安全多方計算協(xié)議也具有很強的應(yīng)
用背景。本文首先在半誠實模型下進行討論，然后
將協(xié)議推廣到惡意模型下。
通信模型：安全多方計算幾何協(xié)議中使用的通
信模型包括同步和異步2 種模型。同步通信模型是
指所有參與方共同使用一個時鐘服務(wù)器，同時接收
或發(fā)送消息；異步通信模型是指各參與方按照不同
的時鐘周期接收或者發(fā)送消息。
可以用如圖2 所示表示一個安全多方計算幾何
協(xié)議的框架。
圖2 安全幾何計算框架
4 安全兩方線段求交協(xié)議
4.1 問題分析
問題1 中的路線如果是線段，則問題1 可以描
述為：Alice 擁有線段 A: y ? a1 x ? b1 1 (m ≤x
1 ≤n ) ，Bob 擁有線段 2 2 B : y ? a x ? b 2 (m ≤x
2 ≤n )。Alice 和Bob 希望計算2條線段的交點。計
算結(jié)束后，除了交點的坐標信息，對方不能獲知其
他任何信息。上述問題稱為安全兩方線段求交點問
題。解決該問題的協(xié)議稱為安全兩方線段求交協(xié)
議，記作STPP_IL(secure two party protocol for intersection
of line)。
在二維空間中，2 條線段的位置關(guān)系有如下幾
種情況：圖3(a)中，2 條線段相交于一點；圖3(b)
中，2 條線段所在的直線相交于一點，但是2 條線
段無交點；圖3(c)中，2 條線段平行，無交點；圖3(d)
中，2 條線段在同一條直線上，且滿足n2 ? m1 ，此時
線段無交點；圖3(e)中，2 條線段在同一條直線上，
且滿足1 2 n ≤m ，此時線段無交點；圖3(f)中，2 條
線段在同一條直線上，且滿足1 2 2 1 m ≤m ,m ≤n ,
1 2 n ≤n ，此時線段的交構(gòu)成一條線段： 1 1 y ? a x ? b
2 1 (m ≤x≤n )；圖 3(g)中，2 條線段在同一條直線
上，且滿足2 1 1 2 m ≤m ,n ≤n ，此時線段的交構(gòu)成一
條線段： 1 1 1 1 y ? a x ? b (m ≤x≤n )，圖 3(h)中，2
條線段在同一條直線上，且滿足2 1m ≤m , 1 2m ≤n ,
2 1 n ≤n ，此時線段的交構(gòu)成一條線段： 1 1 y ? a x ? b
1 2 (m ≤x≤n )；圖 3(i)中，2 條線段在同一條直線
上，且滿足1 2m ≤m , 2 1 n ≤n ，此時線段的交構(gòu)成
·34· 通 信 學(xué) 報 第34 卷
一條線段： y ? a1 x ? b1 2 2 (m ≤x≤n )。
圖3 二維空間中的線段位置關(guān)系
安全兩方線段求交點問題的數(shù)學(xué)模型就是已知2
條線段求交點，歸屬于多邊形求交點模型一類。下面
使用異步通信模型和半誠實安全模型設(shè)計解決該問
題的協(xié)議。圖4 中用灰色表示本節(jié)協(xié)議使用的模型。
圖4 SP_IL 框架
4.2 協(xié)議描述
本文使用Luo 等在文獻[23]中提出的SMC協(xié)議
的符號，如表2 所示。
系統(tǒng)參數(shù)：Alice 擁有Paillier 同態(tài)加密系統(tǒng)的
密鑰對(pk,sk)，公鑰pk 是公開的。
STPP_IL(A,B):
{
A1:
Compute: E(a1 ),E(?b1 ) ;
//Alice 使用公鑰加密a1 和 ? b1
表2 系統(tǒng)符號
符號名稱 符號意義
Ai Alice 在本地執(zhí)行第i 步
Bi Bob 在本地執(zhí)行第i 步
Ai|Bi Alice 和Bob 各自在本地執(zhí)行第i 步
Ai ^ Bi Alice 和Bob 共同協(xié)作執(zhí)行第i 步
Generate 構(gòu)造一個對象
Compute 執(zhí)行一個基本操作
Send(A->B,s1,…,sm) A 向B 發(fā)送消息s1,…,sm
Receive(A->B,s1,…,sm) B 接收A 發(fā)送的消息s1,…,sm
Send(Alice->Bob, E(a1 ),E(?b1 ) );
B2:
Generate: r // Bob 選擇隨機數(shù)r
Compute: [E(a1 )]r E(?ra2 ) ? E(ra1 ? ra2 )；
Compute: [E(?b1 )]r E(rb2 ) ? E(rb2 ? rb1 ) ;
Send(Bob -> Alice, E(ra1 ? ra2 ) , E(rb2 ? rb1 ) );
A3:
Compute: D(E(ra1 ? ra2 )) ;
Compute: D(E(rb2 ? rb1 )) ;
if( ( ( 1 2 )) 0 D E ra ? ra ?? )
{//2 條線段斜率相等
if( D(E(rb2 ? rb1 )) ?? 0 )
go to A4^B4
//2 條線段在同一條直線上，進入A4^B4
else
{
Send(Alice->Bob, (0,0));
go to B5;
//此時2 條線段平行，進入B5
}
}
else //2 條線段不平行
{
Compute:
1 2
2 1
1 2
2 1
( ( ))
( ( ))
a a
b b
D E ra ra
x D E rb rb
?
?
?
?
?
? ;
if( 1 1 m ≤x≤n )
{
Send(Alice->Bob, (x,1));
go to B5;
第1 期 孫茂華等：安全兩方線段求交協(xié)議及其在保護隱私凸包交集中的應(yīng)用 ·35·
}
else
{
Send(Alice->Bob, (x,2));
go to B5;
}
}
A4^ B4:
//2 條線段在同一條直線上
if(MillionaireProtocol( m1 ,m2 )==1)
//使用百萬富翁協(xié)議判斷數(shù)據(jù)的大小，當(dāng)
// 1 2 m ≥m 時，協(xié)議返回1，否則返回0；
{
if(MillionaireProtocol( m1 ,n2 )==1)
End;//圖3(d)的情況，無交點；
else
{
if(MillionaireProtocol( n1 , n2 )==1)
{
Send(Alice->Bob, m1 );
Send(Bob-> Alice, n2 );
Alice: 1 1 1 2 y ? a x ? b (m ≤x≤n ) ;
Bob: 2 2 1 2 y ? a x ? b (m ≤x≤n ) ;
//圖3(h)的情況，交點構(gòu)成一條線段；
}
else
{
Send(Alice->Bob, m1 ,n1 );
Alice: 1 1 1 1 y ? a x ? b (m ≤x≤n ) ;
Bob: 2 2 1 1 y ? a x ? b (m ≤x≤n ) ;
//圖3(g)的情況，交點構(gòu)成一條線段；
}
}
}
else
{// 1 2 m ≤m
if(MillionaireProtocol( m2 , n1 )==1)
End;//圖3(e)的情況，無交點；
else
{
if(MillionaireProtocol( 1 2 n ,n )==1)
{
Send(Bob->Alice, m2 , n2 );
Alice: 1 1 2 2 y ? a x ? b (m ≤x≤n ) ;
Bob: 2 2 2 2 y ? a x ? b (m ≤x≤n ) ;
//圖3(i)的情況，交點構(gòu)成一條線段；
}
else
{
Send(Alice->Bob, n1 );
Send(Bob-> Alice, m2 );
Alice: 1 1 2 1 y ? a x ? b (m ≤x≤n ) ;
Bob: 2 2 2 1 y ? a x ? b (m ≤x≤n ) ;
//圖3(f)的情況，交點構(gòu)成一條線段；
}
}
}
End;
B5:
Receive(Alice->Bob, (x, k1 ) );
if( k1 ?? 0 )
End; //2 條線段無交點，協(xié)議結(jié)束
elseif( k1 ??1 )
{
if( 2 2 m ≤x≤n )
{
Send(Bob-> Alice, (x,1));
Compute: y ? a2 x ? b2 ;
}
else
Send(Bob-> Alice, (0,2));
}
A6:
Receive(Bob -> Alice, (x, k2 ) );
if( k2 ?? 2 )
End; //2 條線段無交點，協(xié)議結(jié)束
elseif( k2 ??1 )
Compute: y ? a1 x ? b1 ;
End;
}
4.3 性能分析
1) 正確性分析
定理1 半誠實模型下，上述協(xié)議是正確的。
證明
·36· 通 信 學(xué) 報 第34 卷
上述問題實際上就是求解式(1)在式(2)中的解
1 1
2 2
y a x b
y a x b
? ? ? ?
?
?? ? ?
(1)
取值范圍： 1 1 m ≤x≤n 并且 2 2 m ≤x≤n （2）
求解式（1 ）的解分為以下幾種情況：當(dāng)
1 2 a ? a ? 0 時 ， 式 （ 1 ） 的 解 為 2 1
1 2
x b b
a a
?
?
?
，
1 1 y ? a x ? b 。求解 x 的值后驗證是否滿足式（2）
即可；由于Alice 選用了滿足加法同態(tài)性的加密系
統(tǒng)，有
[ ( )] ( )
[ ( )] ( )
( ( ))
( ( ))
1 2
1 2
1 2
2 1
1 2
2 1
E a E ra
E b E rb
D E ra ra
D E rb rb
a a
b b
x r
r
?
?
?
?
?
?
?
?
? 。
當(dāng) 1 2 0 a ? a ? 時，若b1 ? b2 ? 0，則此時 2 條線段平
行，無交點；由于Alice 選用了滿足加法同態(tài)性的
加密系統(tǒng)，此時滿足 D([E(a1 )]r E(?ra2 )) ? 0 并且
D([E(?b1 )]r E(rb2 )) ? 0。因此，A1、B2、A3是正確的。
B5 和A6 中Alice 和Bob 進行通信，均發(fā)送數(shù)據(jù)對
(x,k)。其中，當(dāng)k=0 時，代表2 條直線平行，無交
點；當(dāng)k=1 時, x 有效并代表式（1）的解，Alice 和
Bob 只要確定x 的值滿足式（1）以及式（2）后，通
過各自的線段方程即可確定y 的值；當(dāng)k=2 時，代表
一方確定x 不在其取值范圍內(nèi)，因此線段無交點。
當(dāng)2 條線段在同一條直線上時，A4^B4 利用百
萬富翁協(xié)議比較x 的取值范圍，根據(jù)4.1 節(jié)中討論
的幾種情況進行驗證，因此是正確的。
綜上所述，上述協(xié)議是正確的。
2) 安全性分析
定理2 半誠實模型下，上述協(xié)議是安全的。
證明 當(dāng)2 條線段在同一條直線上時，上述
協(xié)議調(diào)用百萬富翁協(xié)議完成計算。由于半誠實模
型下百萬富翁協(xié)議是安全的，因此本協(xié)議也是安
全的。下面證明當(dāng)2 條線段不在同一條直線上時
的安全性。
Alice 輸入線段1 1 1 1 A: y ? a x ? b (m ≤x≤n )，
Bob 輸入線段2 2 2 2 B : y ? a x ? b (m ≤x≤n )。協(xié)議輸
出output? ? (x, y)。Bob 的信息序列
viewI? (A,B,M, N) ? (B,N, pk,r,E(a1 ),E(?b1 ),E(ra1 ? ra2 ),
E(rb2 ? rb1 )),(x, k1 ),(x, k2 ),(x, y))
下面構(gòu)造模擬器S 模擬Bob 的協(xié)議執(zhí)行過程。
步驟 1 S 的輸入為(B, N, pk, f1 (A,B,M, N))。其
中， f1 (A, B,M, N) ? (r, E(ra1 ? ra2 ), E(rb2 ? rb1 ), (x, k2 ),
(x, y))。
步驟2 S 利用系統(tǒng)公鑰pk 執(zhí)行加密操作，可
得 到 ( 2 ), ( 2 )
E' ?ra E rb 。 則 r
E ra
E ra ra
E a
( )
( )
( )
2
'
1 2
1
'
?
?
? ,
'
1 E (?b ) 2 1
'
2
( )
( )
r
E rb rb
E rb
?
?
?
。由于半誠實模型下同態(tài)加密
系統(tǒng)是安全的，有 ( 1 ) ( 1 )
' E a
c
E a
?
， ( 1 ) ( 1 )
' E b
c
E b ?
?
? 。
步驟 3 S 判斷 f1 (A, B,M, N)中(x,y)是否為有效
值，如果是有效值，則 1 '
1 ? k ;否則 0 '
1k ? 。易知， 1
'1
k ? k 。
綜上所述，
( , , , ( , , , )) ( , , , , ( ), ( 1 ))
'
1
'
S B N pk f1 A B M N ? B N pk r E a E ?b
( ), ( ),( , ),( , 2 ),( , ))
'1
E ra1 ? ra2 E rb2 ? rb1 x k x k x y 。
因為 f (A, B,M, N) ? (x, y) , output? ? (x, y) ,所以
1 ( , , , ( , , , )) c
S B N pk f A B M N ?
{viewI (A, B,M, N),output (A,B,M, N)}
? ? 。
同樣地，可以為Alice 構(gòu)造模擬器。
3) 效率分析
計算復(fù)雜度：本協(xié)議中，共執(zhí)行加密操作4 次，
解密操作2 次，加密數(shù)據(jù)乘法操作2(r+1)次，乘法
操作5 次，加法操作2 次，百萬富翁協(xié)議至多3 次。
Paillier 加密算法的計算復(fù)雜度為O(2logn)，解密算
法的復(fù)雜度為O(2logn)，每次自乘操作的復(fù)雜度為
O(2logn)[24], 選用基于Paillier 加同態(tài)加密方案的百
萬富翁協(xié)議[25]，則計算復(fù)雜度為O(nlogN)。忽略乘
法操作和加法操作，則本協(xié)議的計算復(fù)雜度為
O(rlogn)。
通信復(fù)雜度：本協(xié)議中，Alice 和Bob 共通信
4+3Ca 次，Ca 代表百萬富翁協(xié)議的通信次數(shù)。
4.4 算法比較
在安全多方計算幾何領(lǐng)域，很多文獻給出的協(xié)
議都調(diào)用了現(xiàn)有的安全多方基礎(chǔ)算法，但是沒有明
確使用哪個具體的算法。這就為算法的性能比較帶
來了不便。本文在進行算法比較時，選用了經(jīng)典的
基礎(chǔ)算法進行比較。表3 是算法比較時使用的符合
說明。
選用基于Paillier 加同態(tài)加密方案的百萬富翁
協(xié)議[25]，則計算復(fù)雜度為O(nlogN)?；邳c積協(xié)議
的保護隱私的點線叉積協(xié)議[22] 計算復(fù)雜度為
O(n2)。加同態(tài)加密系統(tǒng)采用Paillier 協(xié)議，加密和
解密操作的計算復(fù)雜度[24]均為O(2logn)。
第1 期 孫茂華等：安全兩方線段求交協(xié)議及其在保護隱私凸包交集中的應(yīng)用 ·37·
表3 系統(tǒng)符號
符號名稱 符號意義
Ta 百萬富翁協(xié)議的算法復(fù)雜度
Tc 保護隱私的點線叉積協(xié)議的算法復(fù)雜度
Th 加同態(tài)加密操作的復(fù)雜度
Td 加同態(tài)解密操作的復(fù)雜度
Ca 百萬富翁協(xié)議的通信次數(shù)
Cc 保護隱私的點線叉積協(xié)議的通信次數(shù)
通過表4 可以看出，本文提出的方案計算復(fù)雜
度低于文獻[17, 22]，略高于文獻[26]；通信復(fù)雜度
低于文獻[22, 26]，略高于文獻[17]。
表4 復(fù)雜度對比
文獻
計算復(fù)雜度
（一般化）
計算復(fù)雜度
（實例化）
通信次數(shù)
本文 O(rlogN) O(rlogN) 4+3Ca
[17] O(n2) O(n2) 6
[22] 4Ta+4Tc O(nlogN+n2) 4Ca +4Cc
[26] 4(4Th+3Td+ Ta) O(ClogN) 8+12Ca
表5 將近幾年來提出的安全兩方線段求交協(xié)議
和本文提出的協(xié)議進行了功能對比。
表5 功能比較
文獻 計算交點坐標 判斷出
圖3(a)~圖3(c)
判斷出
圖3(d)~圖3(i)
本文 是 是 是
[17] 否 是 是
[22] 否 是 是
[26] 否 是 否
4.5 惡意模型下的推廣
惡意模型下的安全兩方線段求交協(xié)議和半誠
實模型下的協(xié)議思想是一致的。由于私有數(shù)據(jù)在進
行交互之前都進行了數(shù)據(jù)加密，因此，即使對方是
不誠實的，也無法得知對方私密數(shù)據(jù)。但是，在惡
意模型下一方需要通過驗證得知對方是否是惡意
的，一旦發(fā)現(xiàn)對方是惡意的，需要及時終止協(xié)議。
下面在半誠實模型協(xié)議的基礎(chǔ)上，Alice 和Bob 需
要進行多次驗證性的交互，防止對方提供虛假數(shù)
據(jù)。Alice 仍然采用Paillier 加密系統(tǒng)，協(xié)議的第一
步、第二步和半誠實模型下是一樣的。
下面，根據(jù)二維空間中線段位置關(guān)系的不同分
別進行討論。
1) 2 條線段平行：Alice計算 ( ( 1 2 )) 0 D E ra ? ra ?
并且D(E(rb2 ? rb1 )) ? 0 后，得知2 條線段平行不相
交，此時通知Bob 結(jié)果，雙方進行交互性驗證,驗證
方式如下。
Ai|Bi:
Compute： a
j
A ? g j , b
j
B ? g j
Generate: u j?R Z n
Generate: c j?R Zn
Compute: gu
j
K ? j
//Alice 計算j=1 的值，Bob 計算j=2 的值；
Send(Alice->Bob, A1 , B1 ,K1 , c1 );
Send(Bob->Alice, A2 ,B2 ,K2 ,c2 );
Ai+1|Bi+1:
Compute: s j ? u j ? c j a j ;
Compute: t j ? u j ? c j b j ;
Compute: Ha H(ai) i ? ;
Compute: Hb H(bi) i ? ;
//Alice 計算j=1 的值，Bob 計算j=2 的值；
Send(Alice->Bob, s t Ha1 Hb1 1 , 1 , , );
Send(Bob -> Alice, s t Ha2 Hb2 2 , 2 , , );
Ai+2:
if(( gs2 K Ac2
?? 2 2 )&amp;amp;&amp;amp;( 2 ( 1) H H a a ?? )
&amp;amp;&amp;amp;( gt2 K Bc2
?? 2 2 )&amp;amp;&amp;amp;( 2 ( 1) H H b b ? ))
End;//此時Alice 得知Bob 是誠實的
else
END;//Bob 提供虛假數(shù)據(jù)，結(jié)束協(xié)議。
Bi+3:
if(( gs1 K Ac1
?? 1 1 )&amp;amp;&amp;amp;( 1 ( 2) Ha H a ?? )
&amp;amp;&amp;amp;( gt1 K Bc1
?? 1 1 )&amp;amp;&amp;amp;( 1 ( 2) H H b b ? ))
End;//此時Alice 得知Bob 是誠實的
else
END;//Bob 提供虛假數(shù)據(jù)，結(jié)束協(xié)議。
2) 2 條線段所在直線交于一點：Alice 計算
D(E(ra1 ? ra2 )) ? 0后，得知2 條線段所在直線交于一
點，此時通知Bob 結(jié)果，雙方進行交互性驗證,驗證
方式如下。
Ai|Bi:
if( j j m ≤x≤n )
{
Compute: y j ? a j x ? b j
Generate: rj //選擇隨機數(shù)
//Alice 計算j=1 的值，Bob 計算j=2 的值；
Send(Alice->Bob,(x,1), r1 );
·38· 通 信 學(xué) 報 第34 卷
Send(Bob->Alice,(x,1), r2 );
}
else
{
Send(Alice->Bob,(0,2),0);
Send(Bob->Alice, (0,2),0);
}
Ai+1|Bi+1:
Receive(Alice->Bob, (x, k1 ), 1 r ) ;
Receive(Bob -> Alice, (x, k2 ), 2 r ) ;
//Alice 計算j=2, i=1 時的值;
//Bob 計算j=1,i=2 時的值；
if( k j ==2)
{
t1 =MillionaireProtocol(x, ) j n ;
t2 =MillionaireProtocol(x, ) j m ;
//調(diào)用惡意模型下的百萬富翁協(xié)議
if( t1 ?t2 ? 0 )
End; //對方是誠實的，協(xié)議結(jié)束
else
End;//對方提供虛假數(shù)據(jù)，協(xié)議結(jié)束
}
elseif( k j ==1)
{
Compute: yi ? ai x ? bi ;
Compute: Yi ? H(r j yi ) ;
Send(Alice->Bob, Y1 );
Send(Bob -> Alice, Y2 );
}
Ai+2:
Receive(Bob -> Alice, Y2 );
if( ( ) Y2 ?? H r1 y1 )
End;//此時Alice 得知Bob 是誠實的;
else
End; //Bob 提供虛假數(shù)據(jù)，協(xié)議結(jié)束
Bi+3:
Receive(Alice -> Bob, Y1 );
if( ( ) Y1 ?? H r2 y2 )
End;//此時Bob 得知Alice 是誠實的;
else
End; //Alice 提供虛假數(shù)據(jù)，協(xié)議結(jié)束
3) 2 條線段在同一條直線上：Alice 計算
1 2 D(E(ra ? ra )) ? 0并且 2 1 D(E(rb ? rb )) ? 0 后，得
知2 條線段在同一條直線上，此時通知Bob 結(jié)果。
Alice 和Bob 使用2 條直線平行時驗證數(shù)據(jù)ai 的方
法驗證a1 是否等于a2，b1 是否等于b2，使用惡意模
型下的百萬富翁協(xié)議驗證2 條線段是否有交點。
5 保護隱私的凸包交集協(xié)議
5.1 問題分析
問題2 中的區(qū)域如果描述為凸多邊形，則問題2
可以表述為：Alice 擁有凸多邊形1 P ? {p , 2, , n p L p ，
Bob 擁有凸多邊形1 2 { , , , } m Q ? q q L q ，頂點為逆時針順
序。Alice 和 Bob 希望求解P ?Q形成的凸包 new P 。同
時，除了結(jié)果之外，Alice 和Bob 不希望對方得到其他
信息。該問題稱為保護隱私的凸包交集問題。
保護隱私的凸包交集問題的數(shù)學(xué)模型是已知2
個凸多邊形求交集。本文選用凸包交集模型半誠實
模型和異步通信模型設(shè)計保護隱私的凸包交集協(xié)
議（如圖5 所示）。
圖5 保護隱私凸包交集協(xié)議框架
5.2 數(shù)學(xué)原理
定義1 所有內(nèi)角都小于π 的多邊形稱為凸多
邊形。凸多邊形的所有頂點均為凸點[27]。
定理3 如果一個凸多邊形的頂點在另一個凸
多邊形內(nèi)，則該頂點也是交集的一個頂點。
證明 假設(shè)i p 是凸多邊形P的一個頂點，并且i p
在凸多邊形Q 內(nèi)部，則頂點i p 對應(yīng)的內(nèi)角?1? ?。
利用反證法，假設(shè)pi 不是交集的頂點，存在一
點 t 是交集的頂點，并且nt, tm分別是交集多邊形上
逆時針方向的2 條邊。由于i p 是凸多邊形P 的一個
頂點，并且在凸多邊形Q 內(nèi)部，則( ) ip ? P ?Q 。
因此， i p 在nt,tm的左邊。又由于nt, tm都屬于凸多
第1 期 孫茂華等：安全兩方線段求交協(xié)議及其在保護隱私凸包交集中的應(yīng)用 ·39·
邊形 P 內(nèi)部或邊上，因此?2是凸多邊形 P 的一個
內(nèi)角，所以?2 ? ?。但這與?1? ?矛盾。因此，pi
肯定是交集的一個頂點(如圖6 所示)。
圖6 交集的頂點
得證。
求2 個凸多邊形的交集，也就是求出交集頂點
的坐標?？紤]如下情況。
圖7(a)中，交集的頂點均為兩凸多邊形的邊相交
產(chǎn)生的交點；圖7(b)中，除了兩凸多邊形的邊相交產(chǎn)
生的交點外，交集的頂點還包括原凸多邊形的某些頂
點，例如4 p ；圖7(c)中，交集的頂點就是被包含的凸
多邊形的頂點；圖7(d)中，交集的頂點是原凸多邊形
的一個頂點。即交集的頂點是原凸多邊形的頂點或者
是由兩凸多邊形的邊相交產(chǎn)生的交點。
圖7 交集的頂點
2 個凸多邊形相交，則交集可能是一個點、一
條線段或者一個多邊形。
定理4 如果2 個凸多邊形的交是一個多邊形，
則該多邊形為凸多邊形。
證明
假設(shè)凸多邊形1 2 { , , , } n P ? p p L p 和凸多邊形
1 2 { , , , } m Q ? q q L q 相 交 ， 交 集 的 頂 點 坐 標 為
new 1 2 { , , , } k T ? t t L t ，k≥1。
對于頂點ti，如果ti 是凸多邊形P 或者Q 的一
個頂點(例如ti 是凸多邊形P 的頂點pj)，則
?ti?1ti ti?1 ? ? pi?1 pi pi?1。因為 i 1 i i 1 p pp ? ? ? ?? ，所以
i 1 i i 1 t tt ? ? ? ? ? 。
如果ti 不是凸多邊形P 或者Q 的一個頂點，則
ti是由 P 和 Q 的邊相交形成的交點。假設(shè) p pm n 和
q qa b 相交形成交點 ti，則?ti?1ti ti?1 ? ? pmti qa或者
i 1 i i 1 n i a ?t ? t t ? ? ?p t q 。由于 m i a ?p t q ? ? ， n i a ?p t q
? ? ，因此i 1 i i 1 t tt ? ? ? ? ? （如圖8 所示）。
圖8 2 條線段的交點
綜上所述，交集的每個內(nèi)角的度數(shù)都小于? ，
因此交多邊形是一個凸多邊形。得證。
由于交集的頂點是原凸多邊形的頂點或者是
由兩凸多邊形的邊相交產(chǎn)生的交點，因此，關(guān)鍵問
題是如何確定凸多邊形的邊何時相交以及交點的
坐標。O’Rourke 在文獻[28]中給出了一個高效地確
定兩凸多邊形的邊何時相交的算法，第4 節(jié)給出了
如果安全求解線段交點的算法。
假設(shè)凸多邊形1 2 { , , , } n P ? p p L p ，凸多邊形
1 2 { , , , } m Q ? q q L q ，頂點為逆時針順序。 i 1 i A p p ? ?
uuuuur
和
j 1 j B q q ? ?
uuuuuur
分別代表2 個多邊形上的有向邊。
O’Rourke 算法讓A 和B 相互追趕，以便在有交點的
時候相遇。有向邊“追逐”的幾種情況如圖9 所示。
1) 有向邊B 擋在A 的正前方，此時如果讓A
前進，則有可能產(chǎn)生交點；
2) 有向邊A 擋在B 的正前方，此時如果讓B
前進，則有可能產(chǎn)生交點；
3) 有向邊B 在A 的外側(cè)，此時如果讓B 前進，
則有可能產(chǎn)生交點；
4) 有向邊A 的終點在B 的外側(cè)且A 的起點在
B 的內(nèi)側(cè)，此時如果讓A 前進，則有可能產(chǎn)生交點；
5) 有向邊A 的終點在B 的外側(cè)且A 的起點在
B 的外側(cè)，此時如果讓A 前進，則有可能產(chǎn)生交點。
用數(shù)學(xué)語言描述為：令H(A)代表A 的左側(cè)半平
面。如果 A? B≥0 且 ( ) j q ?H A 或者 A? B ? 0 且
( ) i p ?H B ，則讓A前進；如果A? B ? 0且 ( ) i p ?H B
或者 A? B≥0且 ( ) j q ?H A ，則讓 B 前進。
5.3 協(xié)議描述
for i=1 to n
·40· 通 信 學(xué) 報 第34 卷
{
if(PIP(pi,Q)==1)
Send(Alice->Bob, pi);
}
for i=1 to m
{
if(PIP(qi,P )==1)
Send(Bob->Bob, qi);
}
令i=j=1;
p pi i A ?1 ? 和 q q j j B ?1 ? 分別為多邊形P 和Q 的
第一條邊；
do{
STPP_IL(A,B)；//Alice 和Bob 利用安全兩方
//線段求交協(xié)議計算并輸出邊A 和B 的交點，
//并插入到各自輸出點序列的相應(yīng)位置。
if(CPP_V(A,B)) >0) //調(diào)用保護隱私的向量叉
//積協(xié)議，判斷向量叉積是否為正
{
if(CPP_PL (qj+1,A)==?1)
// qj+1 在A 的左側(cè)
i=i+1;
else
j=j+1;
}
else
{
if(CPP_PL (pi+1,B)==-1)
// pi+1 在B 的左側(cè)
j=j+1;
else
i=i+1;
}
}while((i

網(wǎng)友評論 more

電力安全論文最新內(nèi)容

03-05