JCP 2012 Vol.7(9): 2224-2231 ISSN: 1796-203X
doi: 10.4304/jcp.7.9.2224-2231
doi: 10.4304/jcp.7.9.2224-2231
Privacy-preserving Judgment of the Intersection for Convex Polygons
Yifei Yao1, Shurong Ning1, Miaomiao Tian2, Wei Yang2
1School of Computer & Communication Engineering, University of Science & Technology Beijing, Beijing, China
2National High Performance Computing Center, Hefei, China
Abstract—As the basic issues of computational geometry, intersection and union of convex polygons can solve lots of problems, such as economy and military affairs. And privacy-preserving judgment of the intersection and union for convex polygons are most popular issues for information security. Traditional method of making the polygons public does not satisfy the requirements of personal privacy. In this paper, a method to compute intersection and union of convex polygons in secure two-party computation (STC) model has been considered, both proportionate partition and unproportionate partition cases are studied. Scan line algorithm is used to figure out the geometry matter, while secret comparison protocol is used for saving the privacy, a series of protocols for this matter is proposed, which combines computational geometry and secure multi-party computation (SMC) technique to achieve the functionality of cooperation calculation without leaking so much privacy. At last, the security, complexity and applicability analysis of the protocols are also discussed.
Index Terms—STC, secret comparison protocol, privacypreserving geometric computation, polygonal intersection, polygonal union.
2National High Performance Computing Center, Hefei, China
Abstract—As the basic issues of computational geometry, intersection and union of convex polygons can solve lots of problems, such as economy and military affairs. And privacy-preserving judgment of the intersection and union for convex polygons are most popular issues for information security. Traditional method of making the polygons public does not satisfy the requirements of personal privacy. In this paper, a method to compute intersection and union of convex polygons in secure two-party computation (STC) model has been considered, both proportionate partition and unproportionate partition cases are studied. Scan line algorithm is used to figure out the geometry matter, while secret comparison protocol is used for saving the privacy, a series of protocols for this matter is proposed, which combines computational geometry and secure multi-party computation (SMC) technique to achieve the functionality of cooperation calculation without leaking so much privacy. At last, the security, complexity and applicability analysis of the protocols are also discussed.
Index Terms—STC, secret comparison protocol, privacypreserving geometric computation, polygonal intersection, polygonal union.
Cite: Yifei Yao, Shurong Ning, Miaomiao Tian, Wei Yang, "Privacy-preserving Judgment of the Intersection for Convex Polygons," Journal of Computers vol. 7, no. 9, pp. 2224-2231, 2012.
General Information
ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
-
Nov 14, 2019 News!
Vol 14, No 11 has been published with online version [Click]
-
Mar 20, 2020 News!
Vol 15, No 2 has been published with online version [Click]
-
Dec 16, 2019 News!
Vol 14, No 12 has been published with online version [Click]
-
Sep 16, 2019 News!
Vol 14, No 9 has been published with online version [Click]
-
Aug 16, 2019 News!
Vol 14, No 8 has been published with online version [Click]
- Read more>>