唐樂紅

(福州陽光學院， 福建福州 350015)

凸多邊形相似判定問題

唐樂紅

(福州陽光學院， 福建福州 350015)

本文通過利用已有的秘密判定相等協議、 集合相等判定協議、 數據對應成比例判定協議， 設計出凸多邊形相似判定協議， 并分析了其正確性、 安全性和復雜性.

計算幾何； 集合相等； 凸多邊形； 相似判定

0 引言

如果一個多邊形的所有邊中， 任意一條邊向兩方無限延長成為一條直線時， 其他各邊都在這條直線的同一側， 那么我們就稱這個多邊形為凸多邊形(邊數大于3). 生活中常見的正多邊形等都是凸多邊形. 判定兩個凸多邊形是否相似， 在數學、 物理等學科上都有很多的實際應用.

本文假定雙方的計算環(huán)境是安全的， 且前提 是雙方都能嚴格遵守協議的規(guī)程. 在滿足以上條件的情況下， 利用秘密判定相等協議、 集合相等判定協議、 數據對應成比例判定協議， 本文設計出凸多邊形相似判定協議.

1 基礎協議

1.1 秘密判定相等協議

兩個用戶希望在不向對方泄露自己數據信息的情況下， 比較出各自所持有數據是否相等. 如果雙方數據不相等時， 則要求任何一方都不能夠知道對方的數據. 這就是秘密判定問題[1].

1.2 集合相等判定協議

兩個用戶各自擁有一個集合， 如何在不泄露雙方各自集合信息的情況下， 判定出兩個集合是否相等[2]， 這就是集合相等判定問題. 協議具體如下：

輸入： Alice擁有集合X={x1,…,xm},Bob擁有集合Y={y1,…,ym}.

輸出： 謂詞P(X,Y).

執(zhí)行過程：

(3) Alice和Bob各自在本地利用商量好的散列函數， 計算出S′=hash(S)和T′=hash(T).

(4) Alice和Bob共同調用秘密判定相等協議判定S′與T′是否相等. 如果相等， 則返回結果為P(X,Y)=1； 否則P(X,Y)=0.

1.3 數據對應成比例判定協議

兩個用戶各自擁有一組數據， 如何在不向對方泄露自己數據的前提下， 秘密判斷出兩組數據是否對應成比例， 這就是數據對應成比例判定問題[3]. 協議具體如下.

輸入： Alice擁有數據X=(x1,…,xn)， Bob擁有數據Y=(y1,…,yn).

輸出：X與Y是否對應成比例.

執(zhí)行過程：

(1) 對每一個i(i=1,…,n-1)， Alice和Bob完成以下任務：

①Alice和Bob各自在本地計算， 分別得到Xi=(xi,-xi+1)和Yi=(yi+1，yi).

②利用Xi和Yi， Alice和Bob共同執(zhí)行點積協議， Alice得到ui=xiyi+1-xi+1yi+vi， 隨機數vi則是由Bob選定的.

(2) Alice得到U=(u1，u2， …，un-1)， Bob得到V=(-2v1， -2v2， …， -2vn-1).

(4) Alice和Bob各自在本地計算， 分別得到

(5)利用s和t， Alice和Bob共同執(zhí)行秘密判定相等協議. 如果相等， 則說明X與Y對應成比例； 否則說明X與Y不對應成比例.

2 凸多邊形相似判定協議

2.1 問題描述

Alice擁有角數據為A=(α1,α2,…,αn)， 邊數據為X=(x1,…,xn)的凸n邊形； Bob擁有角數據為B=(β1,β2,…,βm)， 邊數據為Y=(y1,…,ym)的凸m邊形. 雙方希望在不向對方透露自己數據的情況下， 合作判定出這兩個凸多邊形是否相似. 判定完成后， 雙方只能知道兩個凸多邊形是否相似， 而不能從中得知對方的其他信息.

對于兩個凸多邊形， 如果能同時滿足： ①角對應相等； ②邊對應成比例， 則說明這兩個凸多邊形是相似的. 角對應相等且邊對應相等的兩個凸多邊形， 我們稱為全等凸多邊形[4].

2.2 問題分析

首先， 我們對雙方的角數據要按照從大到小(或從小到大)的順序排列. 因為角要對應相等， 角度相同的角的個數必然一樣. 因此， 雙方的角數據先按照從大到小(或從小到大)的順序排列， 然后利用集合相等判定協議進行判定. 如果不相等， 說明兩個凸多邊形肯定不相似. 如果相等， 再進行角對應相等判定.

角對應相等判定方法： 先找出凸多邊形中角度最大的角(假設存在這么一個角)， 讓其作為角數據中的第一個元素. 然后不按照時針方向， 而是按照向著鄰近此角的兩個角當中的較大角的方向， 對所有的角進行排列. 這樣排列后， 就可以把角數據可能的對應方式找出來了， 所以只要進行一次角對應相等判定即可. 如果角對應相等判定不成立， 則兩個凸多邊形肯定不相似； 如果角對應相等判定成立， 則要繼續(xù)判定邊是否對應成比例.

邊對應成比例判定方法： 我們可以利用前面角對應相等的信息， 對邊也進行按角對應關系的順序排列好. 把角對應信息應用到邊對應上， 也就是把邊的可能對應方式找出來. 這同樣可以減少很多不必要的判斷， 最后只需要進行一次邊對應成比例判定就可以了. 如果邊對應相等判定成立， 則說明兩個凸多邊形肯定相似， 否則說明兩個凸多邊形不相似.

2.3 協議描述

假設Alice和Bob的角數據是按從小到大的順序排列好的. 通過上面的分析， 可以得到協議描述如下：

輸入： Alice擁有一個凸n邊形， 角數據為A=(α1,…,αn)， 邊數據為X=(x1,…,xn). Bob擁有擁有一個凸m邊形， 且角數據為B=(β1,…,βm)， 邊數據為Y=(y1,…,ym).

輸出： 兩個凸多邊形是否相似.

執(zhí)行過程：

(1) Alice和Bob共同利用秘密判定相等協議，判定兩個凸多邊形的邊數是否相等。如果相等，則協議繼續(xù)。如果不相等，說明兩個凸多邊形不相似，協議結束。

(2) Alice和Bob共同利用集合相等判定協議，判定集合A,B是否相等。如果相等，則協議繼續(xù)。如果不相等，說明兩個凸多邊形不相似，協議結束。

(3) Alice和Bob各自在本地找出角數據中角度不重復的最大角，然后以此角作為新的角數據中的第一個元素，并按照向著鄰近此角的兩個角當中較大的方向，對所有角進行重新排列，得到新的角數據A′和B′。

(4) Alice和Bob共同利用集合相等判定協議，判定集合A′和B′是否相等。如果相等，則協議繼續(xù)。如果不相等，說明兩個凸多邊形不相似，協議結束。

(5) Alice和Bob各自在本地根據角數據的排列順序，對邊數據也按此順序重新排列，得到新的邊數據X′和Y′。

(6) Alice和Bob共同利用數據對應成比例判定協議判定X′,Y′是否對應成比例。如果對應成比例，則說明兩個凸多邊形相似，協議結束；如果不對應成比例，則說明兩個凸多邊形不相似，協議結束。

2.4 協議分析

正確性分析： 根據上面的分析以及協議的內容， 我們可以很容易看出， 兩個邊數相等的凸多邊形， 只要角數據相等且邊對應成比例， 則兩個凸多邊形必然相似的. 綜上所述， 本協議是正確的.

復雜性分析： 本協議調用了1次秘密判定相等協議、 1次的數據對應成比例判定協議、 2次集合相等判定協議. 若所采用的秘密判定相等協議是基于可交換加密的， 則此協議的通信次數為3， 數據對應成比例判定協議的通信次數為3mn+2， 集合相等判定協議的通信次數為3， 所以本協議的通信次數為3+6+3mn+2. 本協議的計算代價主要為執(zhí)行12次可交換加密方案中的加密運算， 以及4mn次同態(tài)加密方案中的加密運算和2mn次同態(tài)加密方案中的解密運算.

3 結語

網絡的興起， 使得隱私保護問題得到了越來越多的關注. 保護私有信息的計算幾何問題在很多領域也得到了越來越廣泛的應用. 利用已有的秘密判定相等協議、 集合相等判定協議以及數據對應成比例判定協議， 本文提出了凸多邊形相似判定協議， 并對協議的正確性、 安全性和復雜性進行了分析.

[1] Du W,Atallah J.Privacy-preserving cooperative scientific computations[C].Nova ,Scotia Canada:The 14th IEEE Computer Security Workshop,2001:273-282.

[2] 李順東,王道順,戴一奇.兩個集合相等的多方保密計算[J].中國科學，2009,39(3):305-310.

[3] 羅永龍,黃劉生,荊巍巍,等.空間幾何對象相對位置判定中的私有信息保護[J].計算機研究與發(fā)展,2006,43(3):410-416．

[4] 王鏘.一些基于私有信息保護的計算幾何問題研究[D].蘭州:蘭州理工大學,2009.

Similarity Judgment Problem of Convex Polygons

TANG Le-hong

(Yango College, Fuzhou 350015, China)

Convex polygon, as a relatively common geometric figure, has a wide range of applications in daily life, and it has become a research direction in the Privacy-Preserving Computational Geometry (PPCG). In this paper, by using secret decision equality protocol, set equality decision protocol and proportional agreement protocol, we propose a protocol in similarity judgment problem of convex polygons. And furthermore analyze correctness, security and complexity.

computational geometry; set equality; convex polygon; similarity judgment

TP309

A

1009-4970(2017)11-0013-03

2017-04-09

唐樂紅(1985—)， 女， 碩士， 講師. 研究方向： 計算機科學與技術.

[責任編輯 胡廷峰]