唐樂紅

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

凸多邊形相似判定問題

唐樂紅

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

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

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

0 引言

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

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

1 基礎(chǔ)協(xié)議

1.1 秘密判定相等協(xié)議

兩個用戶希望在不向?qū)Ψ叫孤蹲约簲?shù)據(jù)信息的情況下， 比較出各自所持有數(shù)據(jù)是否相等. 如果雙方數(shù)據(jù)不相等時， 則要求任何一方都不能夠知道對方的數(shù)據(jù). 這就是秘密判定問題[1].

1.2 集合相等判定協(xié)議

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

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

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

執(zhí)行過程：

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

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

1.3 數(shù)據(jù)對應(yīng)成比例判定協(xié)議

兩個用戶各自擁有一組數(shù)據(jù)， 如何在不向?qū)Ψ叫孤蹲约簲?shù)據(jù)的前提下， 秘密判斷出兩組數(shù)據(jù)是否對應(yīng)成比例， 這就是數(shù)據(jù)對應(yīng)成比例判定問題[3]. 協(xié)議具體如下.

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

輸出：X與Y是否對應(yīng)成比例.

執(zhí)行過程：

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

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

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

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

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

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

2 凸多邊形相似判定協(xié)議

2.1 問題描述

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

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

2.2 問題分析

首先， 我們對雙方的角數(shù)據(jù)要按照從大到小(或從小到大)的順序排列. 因?yàn)榻且獙?yīng)相等， 角度相同的角的個數(shù)必然一樣. 因此， 雙方的角數(shù)據(jù)先按照從大到小(或從小到大)的順序排列， 然后利用集合相等判定協(xié)議進(jìn)行判定. 如果不相等， 說明兩個凸多邊形肯定不相似. 如果相等， 再進(jìn)行角對應(yīng)相等判定.

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

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

2.3 協(xié)議描述

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

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

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

執(zhí)行過程：

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

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

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

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

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

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

2.4 協(xié)議分析

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

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

3 結(jié)語

網(wǎng)絡(luò)的興起， 使得隱私保護(hù)問題得到了越來越多的關(guān)注. 保護(hù)私有信息的計算幾何問題在很多領(lǐng)域也得到了越來越廣泛的應(yīng)用. 利用已有的秘密判定相等協(xié)議、 集合相等判定協(xié)議以及數(shù)據(jù)對應(yīng)成比例判定協(xié)議， 本文提出了凸多邊形相似判定協(xié)議， 并對協(xié)議的正確性、 安全性和復(fù)雜性進(jìn)行了分析.

[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].中國科學(xué)，2009,39(3):305-310.

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

[4] 王鏘.一些基于私有信息保護(hù)的計算幾何問題研究[D].蘭州:蘭州理工大學(xué),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—)， 女， 碩士， 講師. 研究方向： 計算機(jī)科學(xué)與技術(shù).

[責(zé)任編輯 胡廷峰]