野王,日本xxxx片免费观看,丁香五月婷婷亚洲,六月丁香婷婷大团结

會員中心
加入VIP
微信

客服微信網(wǎng)站公眾號

　煤礦　化工　建筑
　機(jī)械　電力　冶金
　消防　交通　特種

　論壇　活動　視頻
　問答　投稿　 MSDS
　簽到　超市　招聘

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

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

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

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

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

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

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

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

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

文本預(yù)覽

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

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

基于擺度大數(shù)據(jù)的水輪…

03-05

夾巖水利樞紐壩后電站…

03-05

金沙江上游葉巴灘水電…

03-05

勘測設(shè)計(jì)分承包管理工…

03-05

奎屯河三級水電站機(jī)組…

03-05

蘭溪市水利工程標(biāo)準(zhǔn)化…

03-05

冷卻塔熱力性能評價(jià)方…

03-05

麗水通濟(jì)堰灌區(qū)水利管…

電力安全論文熱點(diǎn)內(nèi)容

41766

電力安全生產(chǎn)管理中…

24722

發(fā)電機(jī)軸電壓產(chǎn)生的…

19565

電廠值長如何做好安…

19128

淺談電力安全生產(chǎn)

17548

電子商務(wù)中存在的安…

16136

淺談電力企業(yè)班組安…

13728

工業(yè)企業(yè)電氣危險(xiǎn)源…

10243

氫站、油站重大危險(xiǎn)…

相關(guān)內(nèi)容

M2M技術(shù)要求（第一階段）H…

快遞包裝重金屬與特定物質(zhì)…

A2∕O工藝在城市生活污水…

調(diào)兵山污水處理廠運(yùn)營成本…

福建省某綜合改革建設(shè)試點(diǎn)…

創(chuàng)想安科網(wǎng)站簡介會員服務(wù)廣告服務(wù)業(yè)務(wù)合作提交需求會員中心在線投稿版權(quán)聲明友情鏈接聯(lián)系我們

<pre id="ell2u"></pre>

<input id="ell2u"></input>