一个点与矩形区域包含关系的安全判定协议.pdf

第 9期计算 机 技 术 与发 展v0I．19No．92009年 9月COMPUTERTECHNOLOGYANDDEVELOPMENTSep． 2009一 个点与矩形区域包含关系的安全判定协议张彩云，罗永龙 ，石 磊(安徽师范大学 计算机科学技术系，安徽 芜湖 241003)摘 要：点与矩形区域包含关系的安全判定是指两个用户基于各 自的输入信息，共同完成矩形区域是否包含点的判定，并且双方都不能获得对方的输入信息，该问题是一个安全两方计算问题，广泛应用于竞标、拍卖等不泄露信息的商业领域。通过对点与矩形区域位置关系的分析 ，得到一个判定点与矩形区域位置的公式，然后基于点积协议设计了一个点与矩形区域包含关系的安全判定协议 ，并且分析了协议的正确性、安全性和复杂性。在保护用户私有输入信息的条件下，解决了点与矩形区域的位置关系判定问题。关键词 ：安全两方计算；计算几何；点积协议中图分类号：1]P309文献标识码：A文章编号：1673—629X(2009)09—0140—03A SecurityProtocolforPoints_’’RectangleAreaInclusionZHANGCai—yun，LUO Yong-long，SHILei(DepartmentofComputerS．cienceandTechnology，AnhuiNormalUniversity，Wuhu241003，China)Abstract：Therelationshipofapointandarectangleareaisthattwopartiesbasedontheinputofinformationtocompletethesecurityofthepoints—rangeinclusionproblem ．andtheyBan’tgetinformationfrom eachother．Itisasecuretwo—partycomputatoinproblem ，nadcanbeappliedino0mmercefield．Inthispaper．aprotocolforthepo ints—rectangleareainclusionproblme whichisbasedonscalarproductprotocolisdeveloped，naditsCOrl"ectne88，securitynadcomplexityareanalyzed，andthecorrespondingalgorithmsfordeterminingtherelativepositoinofpointnadrectangleareaarealsopresentde ．Keywords：securetwo—partyocmputatoin；compuattionalgeometry；scalra productprotocol O 引 言点对及凸包问题，并分别基于茫然传送协议及置换协自从ACYao【]在 1982年首次提出了安全多方计议设计了两个不同的点积协议，在此基础上提出了解 算L2J(SecureMulti—PartyComputation，简称 SMC)问 决点在多边形中的包含判定及两个多边形相交判定的 题以来 ，其已经得到较多的理论研究[3--6】。

近年来，传初步方法。我们已经很好地解决了一类点的包含问 统的数据挖掘l7’8]领域也被不少学者将 SMC技术引题 [13～l5l。 人[，以及计算几何[10--15】、统计分析、电子选举[】等点和矩形区域包含关系是一类点包含问题，它广 领域，促进了安全多方计算朝着能够解决各类实际应泛应用于竟标、拍卖等商业领域。例如：A单位需要引 用问题的方向发展。进某件产品，其规格要求为 [l，2]×[Yl。Y2]。而B保护私有信息的计算几何 (privacy—preserving 单位的产品规格为(，)，在不泄露双方信息的情况 computationalgeometry，PPCG)问题是一类特殊的安全下，A需要知道 B的产品是否满足其要求。该问题的数 多方计算问题，文献[17]中首先提出了安全多方计算学模型是在不泄露双方信息的情况下，安全判定点 几何的概念，介绍了点的包含、多边形相交判定、最近(，Y)是否在矩形区域[1，,272]×[Y1，Y2]内。原先用来解决点是否包含在矩形区域内，将矩形看作凸多边 收稿 日期：2009一O1—13；修回日期：2009—03一O】形，文献[1I]采用设计的叉积协议来解决该问题。

基金项 目：国家 自然科学基金项 目(60703071)；安徽省优秀青年科 技基 金项 目(08040106806)；安 徽 省 自然科 学 基 金项 目 (O7o412043)；安徽高校省级 自然科学研究重点项 目(2oo6K2024A) l 预备知识 作者简介：张彩云(1984一)，女，山东青州人，硕士研究生，研究方向文中采用的计算模型是半城实模型。计算模型是 为信息安全、分布式计算；罗永龙，博士，教授，研究方向为可信计安全两方计算模型，下面介绍点积协议(scalarproduct 算、分布式计算、信息安全等。protoco1)。’ 第9期张彩云等：一个点与矩形区域包含关系的安全判定协议·141 ·点积问题描述为Alice有一个私有向量 = ( ， 0= 口 + b 一 c < 0： ．7C2，…，z)， 有另一个私有 向量 Y= (l，2，…，(3)点N在矩形左上点或者右下点时(图l(d))，卫 )，Alice需要得到值 “=x ·Y十 =∑z + ， 是直角，N0ccos0：：0 口2+62一c2： 这里 是Bob选取的一个随机数。同时满足：(])Alice不0； 能从 U中得到x，y的值 ，也不能从结果得到任何 的(4)点N在矩形外 ，并且与线段 加 共线时(图 信息；②Bob不能得到 的值，也不能得到任何 矗的信l(e))，fa～bf=c (Ia—bf)。

：f。 口0+b。一2ab2+ b2一f2= 2ab > 0： 息。c 盘点积协议在文献 [17]首先提出来以后，近年来被(5)点 N在矩形外时(图 1(f))，0是锐角，因此 广泛应用于保护私有信息的各类协作计算，并已经成cos0：> o 口2+ 62一 c > 0；ZaO 为SMC的一个基本协议。根据上面的分析 ，由(1)(2)(3)得到：点N在矩形内时，a+b。一C。≤0；由(4)与(5)得到 ：点N不在矩 2 矩形区域包含点判定协议形内时 ，a +b2一C2>0。因此，只要判断出a。+b0一 2．1 问题描述c 的符号就可以了。此外，在平面上， ice拥有一个矩形区间，可用左下点口2+b2一c2= ( — 1)2+(j，一Y1)2+( — 2)2+ p(x1，1)和右上点q(x2，2)来表示：[zl点是否在矩形中判断，2]×[l，( — 2)2～((l— 2)2+(Yl一 )2)=2x2+2y2— 2]，Bob拥有一点N(z，Y)，在不泄露双方信息的情况2sc(xl+ 2)一2y(y1+ 2)+2x12+2y】2=2(x 下，Alice想知道Bob这一点是否在它的区间内。

+ )一2(x，)·(1+ 2，1十 2)十2(zlz2+j点是否在矩形中判断，12)判断点是否在矩形 内，点与矩形的关系可 以有下 面五种情况(如图 1所示)：首先，设令 “== ( z)_( )．(z。a=Np=~／(—z1)2+(— 1)2，+．2c2，1+ 2)十(zlz2+YlY2)，“跟口。十6。一C的符b=Nq：~／(z—z2)2+(．)，一 2)2，号是相同的，从而将判断 a+6。一C的符号转化为判断 U的符号。c=Pq=~／(z1一z2)+(Y1一 2)，2．2 判定协议pNq = 0， 根 据 余 弦 定 理 ，cosO =通过2．1的分析 ，问题转化为解决 (zl+ 2，l+ 堡：±垒!=￡12ab 。Y2)·(z，)的大小问题，因为是两个 向量相乘 ，因此(1)点N在线段加 (包括点P、口)上 (图1(a))，此下面介绍的协议调用点积协议来实现。具体协议如表 时 a+b=f (a十b)=c 口十6 +2ab=c 口1所示。 +b 一C =一2ab≤ 0；2．3 性能分析(2)点N在矩形内或者在矩形边上(不包括顶点，(1)正确性。协议PRISPP能使AliceN断出N是否在矩形区域 图 l(b)())时 ，0是钝角 ，因此cos0：<内。

p N(a)点Ⅳ在线段 上(c)点Ⅳ在矩形边上／(d)点^r在矩形左(ee))点点N在在矩矩形形外外，，(D点Ⅳ在矩形外上点或者右下点并且与线段pg共线图 1 点与矩形 的关系· 142 ·计算机技术与发展第l9卷Science．L0sAlamitos：IEEECo mputerSocietyPress。1982：160—164．[2] GoldreichO．Securemulti—partyocmputation(manuscriptversion1．3)[EB／O】]．2002．http：／／theory．1os．mit．edu／-oded．[3] Ca&inC．Efficientprivatebiddingandauctionswithaflobliv-iousthirdparty[C]／／In：Proe．6thACM Con／．ComputerandCommunicationsSecurity．New York：ACM Press，1990：120—127．[4] YaoAC．Howtogenerateand~changesecrets[C]∥In：Proc 27th IEEE Smy posimu onFoundationsofCo mputerScience．LosAlamito~：IEEECo mputerSocietyPress，1986：162—167．证明：因为 U U1一U2+ “3=z】2十YlY2一[5] GoldrcichO，MicaliS，Wigdersno A．HowtOplayanymen— ((1+z2，Y1+Y2)·(z，Y)+ )+(z2+Y2+ )=talgame[cJ／／In：Proc．19thAnnt~ACM Symposiumon (2+Y2)一 (，Y)·(l+ 2，Y1+ 2)+ (lz2+TheoryofComputing．New York-ACM Press，1987：218— YlY2)，因此协议是正确的。

229．(2)安全性。[6] GoldwasserS．Multi—partycomputations：Pastandpresent协议 PRISPP是安全的，计算双方均不能从协议[C]∥In：Proc．16thAnnualACMSymposimu onPrinciples 中得到对方的具体输人信息。Step2中 ice和BOb调用ofDistributedC~mputing．New York：ACM Press．1997：1— 6． 了一次点积协议，由于计算双方在该步输入的是二维[7] 王 预．数据仓库与数据挖掘的关系及其安全性问题 j【]． 数据 ，为提高协议的安全性，可以采用基于同态加密的计算机技术与发展，2008，18(5)：144—146． 点积协议["】，假设 优是该点积协议的安全参数 (使得[8] 吕 品，陈年生．面向隐私保护的数据挖掘技术研究[J]． 2 足够大)，根据文献[17]，Alice(或Bob)能猜测出对计算机技术与发展 ，2006．16(7)：147—149．1[9] 罗永龙，黄刘生，荆巍巍，等．一个保护私有信息的布尔关 方数据的概率为 。

Step3中，Bob发送给Alice的 “3是联规则挖掘算法[J]．电子学报．2005，33(5)：900—903． 加了随机数 的，Alice并不能简单就猜出z +Y 的[10]罗永龙，黄刘生，荆巍巍，等．空间几何对象相对位置判 值。因此，协议PIRA是安全的该判定方法是安全的。定中的私有信息保护[J]．计算机研究与发展，2006，43(3)：(3)复杂性。410—416．通信复杂性 ：协议PRISPP执行了一次点积协议， [11]罗永龙 ，黄刘生 ，荆巍巍 ，等．保护私有信息的叉积协议 基于同态加密的点积协议的通信次数为4m[]，Step3及其应用[J]．计算机学报 ，2007，30(2)：248—254．[12]罗永龙，黄刘生 ，徐维江，等 ．一个保护私有信息的多边 进行了一次通信，因此协议 PIRA的通信复杂性为形相交判定协议[J]．电子学报，2004，32(4)：685—691． O(4m)。[13]Lu0YongLong，HuangLiusheng，ZhongHong，eta1．A8e-计算复杂性：协议PRISPP的主要计算代价在于cureprotocolfordeterminingwhetherapointisinsideacon· Step2中执行了O(优 )次加解密运算，其计算复杂性vexpolygon[J．CahineseJournalofElectronics，2006，15(4)： 依赖于所采用的同态加密方案。

578—582．[14]L∞YongLong，HuangLiusheng，ChenGuoliang，eta1．Pri- 3 结束语racy— preserving distancemeasurementanditsapplications点和矩形区域包含关系的安全判定是一个安全两[J]．ChineseJournalofElectronics，2006，15(2)：237—241．[15]LuoYong-Long，HLlangLiu—Sheng，ZhongHong．Secure 方计算问题 ，文中采用点积协议来解决，但是不同的点Two—PartyPoint—CircleIndusionProblem[J]．Journalof 积协议都不能兼顾安全性和复杂性，因此可以对算法ComputerScience& Technology，2007，22(1)：88—91． 进行优化，降低复杂性的同时，也提高安全性。点和矩[16]仲 红，黄刘生，罗永龙．基于安全多方求和的多候选人电 形区域的安全判定可扩展到多个点，以及多维空间上。子选举方案[J]．计算机研究与发展，2006，43(8)：1405—1410． 参考文献：[17]AtallahMJ，DuWenliang．Securemu／ti—partycomputational [1] YaoAC．Protocolsforsecurecomputations[C]∥In：Proc．goemetry[M]∥In：LectureNotesinComputerScience2125．23rdAnnualIIEE Symposium onFoundationsofComputerBerlin：Springer。2001：165—179．