密码学报（中英文）2025，Vol.12Issue(4)：836-853,18.DOI:10.13868/j.cnki.jcr.000797
任意多边形点包含问题的保密计算协议
Privacy-Preserving Point-Inclusion Protocol for Arbitrary Polygons
摘要
Abstract
The point-inclusion problem is an important aspect of secure multi-party computation and has a wide range of applications in location-based services like navigation,social networks,and recommendation systems.This problem aims at determining whether a point in two-dimensional space is inside a geometric range.Traditional methods can only address the point-inclusion problem for specific geometric shapes such as circles and rectangles,making them impractical for many real-world scenarios.Researchers have proposed many solutions to solve the point-inclusion problem of convex polygons.As for concave polygons,people either divide them into multiple convex polygons,and then simply invoke the solution of convex polygons several times,or design new privacy-preserving solutions,such as angel-based and ray-based solutions.These methods suffer from complicated protocols,poor accuracy,private information leakage,and low efficiency.This study creatively transforms the point-inclusion problem of arbitrary polygons into the decision problem of the quadrants of the polygon vertices with coordinate transformation,and proposes a new solution that is secure and efficient under the semi-honest model using additively homomorphic encryption schemes.The proposed solution can be used to address the point-inclusion problem for both concave and convex polygons,and the execution of the protocol does not leak any information about the shape of the polygon.The security of the protocol is proved by the simulation paradigm.Experiments are conducted to test the performance of the protocol and results show that the advantage of the proposed protocol in execution efficiency becomes more and more significant with the increase of the number of polygon vertices.When the number of vertices of the polygon is 100,the efficiency of the proposed protocol is about 12.70 times that of the privacy-preserving ray-based solution.关键词
安全多方计算/任意多边形/点包含问题/同态加密/隐私保护Key words
secure multi-party computation/arbitrary polygons/point-inclusion problem/homo-morphic encryption/privacy-preserving分类
信息技术与安全科学引用本文复制引用
王明慧,李顺东..任意多边形点包含问题的保密计算协议[J].密码学报（中英文）,2025,12(4):836-853,18.基金项目
国家重点研发计划(2022YFB2703001)National Key Research and Development Program of China(2022YFB2703001) （2022YFB2703001）
