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

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