保护私有信息的点包含协议研究

doi:10.11959/j.issn.1000-436x.2016075

Abstract

Abstract:

A privacy-preserving point-in-polygon protocol was proposed under semi-honest model, to deal with the prob-lem of high complexity and limitation of the existing protocols. First, an blivious point-line protocol was designed by extending the traditional point-line protocol, making the use of 1-out-n oblivious transfer and the geometric properties of the vector. Then, based on this protocol and combined with the secure binary search protocol, the final solution was put forward. The security of the protocol was proved with ich method. Meanwihle, the validity and the complexity of the protocol were also be analyzed. It is shown that this new protocol gets the advantage over the existing one in terms of efficiency and enjoys excellent expandability.

Key words: point-in-polygon, oblivious point-line protocol, privacy-preserving, secure multi-party geometry

Jing ZHANG,Shou-shan LUO,Yi-xian YANG,Yang XIN. Research on the privacy-preserving point-in-polygon protocol[J]. Journal on Communications, 2016, 37(4): 87-95.

Figures/Tables 4

References 21

[1]	ATALLAH M J , DU W . Secure multi-party computational geome-try[M]. Algorithms and Data Structures. Springer Berlin HeidelBerg, 2001:165-179.
[2]	DU W L , ATALLAH M J . Secure multi-party computation problems and their applications: a review and open problems[C]// The 2001 Workshop on New Security Paradigms, c2001:13-22.
[3]	YANG B , SHAO Z Y , ZHANG W Z . Secure two-party protocols on planar convex hulls[J]. Journal of Information, 2012,9(4):915-929.
[4]	孙茂华，罗守山，辛阳，等．安全两方线段求交协议及其在保护隐私凸包交集中的应用[J]．通信学报， 2013,34(1):30-42. SUN M H , LUO S S , XIN Y , et al. Secure two-party line segments in-tersection scheme and its application in privacy-preserving convex hull intersection[J]. Journal of Communications, 2013,34(1):30-42.
[5]	YANG B , SUN A D , ZHANG W Z . Secure two-party protocols on planar circles[J]. Journal of Information, 2011,8(1):29-40.
[6]	耿涛，李海成，罗守山，等．保护私有信息的动点距离判定协议及其推广[J]．北京邮电大学学报， 2012,35(3):47-51. GENG T , LI H C , LUO S S , et al. A privacy-preserving dynamic point distance determination protocol and its extension[J]. Journal of Beijing University of Posts and Telecommunications, 2012,35(3):47-51.
[7]	仲红，孙彦飞，燕飞飞，等．保护私有信息的空间最近点对协议[J]．计算机工程与应用， 2011,48(4):87-89. ZHONG H , SUN Y F , YAN F F , et al. Protocol for privacy-preserving space closet-pair of points[J]. Computer Engineering and Applicatio 2011, 2011,48(4):87-89.
[8]	周敏，杨波，万军洲，等．保留隐私的计算最近点对协议[J]．西南师范大学学报：自然科学版， 2013,38(2):111-115. ZHOU M , YANG B , WAN J Z , et al. A protocol for privacy-preserving closest-pair of points[J]. Journal of Southwest China Normal U iver-sityJ], 2013,38(2):111-115.
[9]	李顺东，司天歌，戴一奇．集合包含与几何包含的多方保密计算[J]．计算机研究与发展， 2005,42(10):1647-1653. LI S D , SI T G , DAI Y Q . Secure multi-party computation of set-inclusion and graph-inclusion[J]. Journal of Computer Research and Development, 2005,42(10):1647-1653.
[10]	LUO Y L , HUANG L S , ZHONG H , et al. A secure protocol for de-termining whether a point is inside a convex polygon[J]. Chinese Journal of Electronic, 2006,15(4):578-582.
[11]	THOMAS T . Secure two-party protocols for point inclusion problem[J]. International Journal of Network Security, 2009,9(1):1-7.
[12]	YUN Y , LIU S H , WEI Y , et al. Efficient secure protocols to determine whether a point is inside a convex hull[C]// International Symposium on Information Engineering and Electronic Commerce, IEEC'09. c2009:100-105.
[13]	LI S D , DAO S W , DAI Y Q . Efficient secure multiparty computation-al geometry[J]. Chinese Journal of Electronics, 2010,19(2):324-328.
[14]	CHEN L , LIN B . Privacy-preserving point-inclusion two-party computation protocol[C]// 2013 Fifth International Conference on Computational and Information Sciences(ICCIS). c2013:257-260.
[15]	LI S D , WU C Y , WANG D S , et al. Secure multiparty computation of solid geometric problems and their applications[J]. Information Sciences, 2014,282:401-413.
[16]	TRONCOSO-PASTORIZA J R , KATZENBEISSER S , CELIK M , et al. A secure multidimensional point inclusion protocol[C]// The 9th Workshop on Multimedia ＆Security. c2007:109-120.
[17]	TZENG W G . Efficient 1-out-of-n oblivious transfer schemes with universally usable parameters[J]. IEEE Transactions on Computers, 2004,53(2):232-240.
[18]	YAO-PASTORIZA A C . Protocols for secure computations[C]// The 23th Annual IEEE Symposium on Foundations of Computer Science. Chicago, USA, c1982:160-164.
[19]	IOANNIDIS I , GRAMA A . An efficient protocol for Yao's millio-naires' problem[C]// The 36th Annual Hawaii International Conference on System Sciences. c2003:6.
[20]	PAILLIER P . Public-key cryptosystems based on composite degree residuosity classes[C]// Advances in Cryptology—EUROCRYPT'99. Springer Berlin HeidelBerg, c1999:223-238.
[21]	LUO YL , HUANG L S , CHEN G L , et al. Privacy-preserving distance measurement and its applications[J]. Chinese Journal of Electronics, 2006,15(2):237-241.

Metrics

Recommended 0

No Suggested Reading articles found!

文献	主要研究成果
文献[3]	提出安全仰角计算协议，安全线段交计算协议和安全二分检索协议，并将其作为基础协议，提出了一种新的点与凸包包含协议
文献[9]	利用 Monte Carlo 方法，结合 Cantor 编码，提出一种解决任意几何图形的点包含的方法
文献[10]	提出安全两方向量叉积协议，并利用安全两方三点叉积协议实现安全两方点包含协议
文献[11]	利用矢量夹角比较法，提出了星形域上的点包含协议，并将其扩展为解决一般多边形域的包含问题
文献[12]	分别利用Du的两方点积协议和极角比较的方法，提出了2个有效的点与凸包包含关系协议
文献[13]	基于对称密钥的三角形面积协议，提出了一种有效的点与凸多边形包含协议
文献[14]	利用角度旋转方法，解决点与任意多边形的包含问题
文献[15]	将四面体体积作为黑盒工具，提出了一种新包括点面关系判断协议。
文献[16]	提出了安全两方超平面上的点与多维凸包之间的包含关系协议

方法	计算复杂度	通信复杂度
本文	O(nlogn)	O(nlogn)
文献[3]	O(nlog N)	O(nd)
文献[10]	O(n²)	O(n²)
文献[11]	O(nlo gnlo g N)	O(nd lo g n)
文献[14]	O(n²)	O(n²)

方法	基础协议	判断点与凸包关系	判断点与简单多边形关系
本文	茫然点线关系协议	是	是
文献[3]	仰角比较协议	是	否
文献[10]	安全叉积协议	是	否
文献[11]	极角比较协议	是	是
文献[14]	角度旋转协议	是	是

Research on the privacy-preserving point-in-polygon protocol

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 4

References 21

Related Articles 15

Metrics

Recommended 0

[1]	Yingjie XIA, Siyu ZHU, Xuejiao LIU. Research on efficient cross trust-domain group authentication with conditional privacy of vehicle platoon under blockchian architecture [J]. Journal on Communications, 2023, 44(4): 111-123.
[2]	Shengxing YU, Zhong CHEN. Efficient secure federated learning aggregation framework based on homomorphic encryption [J]. Journal on Communications, 2023, 44(1): 14-28.
[3]	Haining YU, Hongli ZHANG, Xiangzhan YU, Jiaxing QU, Mengmeng GE. Privacy-preserving trajectory similarity computation method [J]. Journal on Communications, 2022, 43(11): 1-13.
[4]	Tao PENG, Wentao ZHONG, Guojun WANG, Entao LUO, Jinbo XIONG, Yining LIU, Wang Hao. Privacy-preserving precise profile matching in mobile social network [J]. Journal on Communications, 2022, 43(11): 90-103.
[5]	Rui SHI, Huamin FENG, Huiqin XIE, Guozhen SHI, Biao LIU, Yang YANG. Privacy-preserving attribute ticket scheme based on mobile terminal with smart card [J]. Journal on Communications, 2022, 43(10): 26-41.
[6]	Jinbo XIONG, Yongjie ZHOU, Renwan BI, Liang WAN, Youliang TIAN. Towards edge-collaborative, lightweight and privacy-preserving classification framework [J]. Journal on Communications, 2022, 43(1): 127-137.
[7]	Jiaqi WANG,Ning LU,Qingfeng CHENG,Zhaoxia WU,Wenbo SHI. Privacy-preserving multi-attribute reverse spectrum auction scheme [J]. Journal on Communications, 2020, 41(9): 77-91.
[8]	Yousheng ZHOU,Chang TAN,Fei TANG. Multi-dimensional secure query scheme for fog-enhanced IIoT [J]. Journal on Communications, 2020, 41(8): 175-186.
[9]	Jiayin LI,Wenzhong GUO,Xiaoyan LI,Ximeng LIU. Privacy-preserving real-time road conditions monitoring scheme based on intelligent traffic [J]. Journal on Communications, 2020, 41(7): 73-83.
[10]	Ming LI,Xiaopeng YANG,Hui ZHU,Fengwei WANG,Qi LI. Efficient and privacy-preserving online face authentication scheme [J]. Journal on Communications, 2020, 41(5): 205-214.
[11]	Xinyu WANG,Ben NIU,Fenghua LI,Kun HE. Risk assessing and privacy-preserving scheme for privacy leakage in APP [J]. Journal on Communications, 2019, 40(5): 13-23.
[12]	Xiangyu WANG,Jianfeng MA,Yinbin MIAO. Efficient privacy-preserving image retrieval scheme over outsourced data with multi-user [J]. Journal on Communications, 2019, 40(2): 31-39.
[13]	Weihao LI,Sheng DING,Jiajie MENG,Hui LI. Spatio-temporal aware privacy-preserving scheme in LBS [J]. Journal on Communications, 2018, 39(5): 134-142.
[14]	Jiale ZHANG,Yanchao ZHAO,Bing CHEN,Feng HU,Kun ZHU. Survey on data security and privacy-preserving for the research of edge computing [J]. Journal on Communications, 2018, 39(3): 1-21.
[15]	Xia FENG,Yawei LIU. Dynamic Mix-zone scheme with joint-entropy based metric for privacy-perserving in IoV [J]. Journal on Communications, 2018, 39(3): 76-85.