Privacy-preserving determination of spatial relationship belongs to spatial geometry problem in secure multiparty computation, which is significant to confidential business, engineering, military, etc. However, most existing schemes transform the original problem into the distance problem or the correspondingly proportional data problem, which makes the computation complexity high and the application range being limited. To deal with these problems, first, the original problem is transformed into whether a point is the solution of equation. Based on the technique, a simple and efficient scalar product protocol is adopted to determine five spatial relationships all at once: point and line, point and plane, line and line, line and plane, and plane and plane. In addition, the security of the proposed protocol is proved with simulation paradigm. The proposed scheme does not employ any public key encryption algorithm so as to achieve the information security. The analysis indicates the trick transformation makes the proposed scheme higher efficient and more applicable than the known schemes.
YAO A C. Protocols for secure computations[C]. Proceedings of 23rd IEEE Symposiumon Foundations of Computer Science, Chicago, IL, USA, 1982: 160-164. doi: 10.1109/ SFCS.1982.38.
[2]
KAMM L. Privacy-preserving statistical analysis using secure multi-party computation[D]. [Ph.D. dissertation], University of TARTU, 2015: 50-54.
LIU Feng, XUE Anrong, and WANG Wei. Hybrid algorithm for privacy preserving association rules mining[J]. Application Research of Computers, 2012, 29(3): 1108-1109. doi: 10.3969/ j.issn.1001-3695.2012.03.084.
[4]
ROY B. Performance analysis of clustering in privacy preserving data mining[J]. International Journal of Computer Applications & Information Technology, 2014, 5(4): 35-39.
CHONG Zhihong, NI Weiwei, LIU Tengteng, et al. A privacy-preserving data publishing algorithm for clustering application[J]. Journal of Computer Research and Development, 2010, 47(12): 2083-2089.
[6]
LI C and LIN B G. Privacy-preserving point-inclusion two-party computation protocol [C]. 2013 IEEE Fifth International Conferenceon on Computational and Information Sciences (ICCIS), Hubei, China, 2013: 257-260. doi: 10.1109/ICCIS.2013.75.
WANG Ting and LUO Wenjun. Applications of secure multi-party computation in spacegeometry problems[J]. Computer Systems & Applications, 2015, 24(1): 156-160. doi: 10.3969/j.issn.1003-3254.2015.01.029.
[8]
QIN Jing, DUAN Hongwei, ZHAO Huawei, et al. A new lagrange solution to the privacy-preserving general geometric intersection problem[J]. Journal of Network and Computer Applications, 2014, 46(1): 94-99. doi:10.1016/j.jnca.2014. 08.004.
[9]
GOLDWASSER S. Multi-party computations: Past and present[C]. Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, New York, USA, 1997: 1-6. doi: 10.1145/259380.259405.
[10]
GOLDRE O, MICALI S, and WIGDERSON A. How to play any mental game[C]. Proceedings of the 19th Annual ACM Conference on Theory of Computing, New York, USA, 1987: 218-229.
[11]
GOLDREICH O. Secure multi-party computation(draft)[OL]. http://www.wisdow.weizmann.ac.il/~oded/pp.html,1998.
[12]
DU W L and ATALLAH M J. Secure multi-party computation problems and their applications: A review and open problems[C]. Proceedings of the 2001 Workshop on New Security Paradigms, New York, USA, 2001: 11-22.
JING Weiwei. Research on several basic protocols and application of secure multi-party, computation[D]. [Ph.D. dissertation], University of Science and Technology of China, 2008. doi: 10.7666/d.y1270516.
WANG Ting and LUO Wenjun. Privacy-preserving determination protocol for point-line distance and position relation based on threshold[J]. Computer Engineering and Applications, 2010, 46(13): 87-89. doi: 10.3778/j.issn. 1002-8331/.2010.13.026.
[15]
LI Shundong, WU Chunying, WANG Daoshun, et al. Secure multiparty computation of solid geometric problems and their applications[J]. Information Sciences, 2014, 282(10): 401-413. doi: 10.1016/j.ins.2014.04.004.
LUO Yonglong, HUANG Liusheng, JING Weiwei, et al. Privacy protection in the relative position determination for two spatial geometric objects[J]. Journal of Computer Research and Development, 2006, 43(3): 410-416.
[17]
GOLDREICH O. Foundations of Cryptography: Basic Applications[M]. London: Cambridge University Press, 2004: 599-729.
[18]
CLIFTON C, KANTARCIOGLU M, VAIDYA J, et al. Tools for privacy preserving distributed data mining[J]. ACM SIGKDD Explorations Newsletter, 2002, 4(2): 28-34.
[1]
张少波, Md Zakirul Alam Bhuiyan,刘琴,孟大程,王国军. 移动社交网络中基于代理转发机制的轨迹隐私保护方法[J]. 电子与信息学报, 2016, 38(9): 2158-2164.