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

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

摘要/Abstract

摘要：

摘要：对现有保护私有信息的点包含协议进行研究，针对算法复杂度高、协议本身的的局限性等问题，在半诚实模型下，提出一种保护隐私的判断点与凸包位置关系协议。首先，利用OT ⁿ₁与矢量的几何性质，将传统的点线位置判断问题扩展，设计一种茫然安全点线位置关系判断协议；然后，将此协议作为基础协议，结合安全二分检索法提出最终解决方案。利用 Goldreich 证明法对协议进行安全性证明，同时分析协议的正确性与算法复杂度。分析结果表明，协议在效率上优于现有方案，并具有可扩展性。

关键词: 点包含, 茫然点线关系, 隐私保护, 安全多方几何计算

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

张静,罗守山,杨义先,辛阳. 保护私有信息的点包含协议研究[J]. 通信学报, 2016, 37(4): 87-95.

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.

图/表 4

表1

图1

表2

表3

参考文献 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.

文献	主要研究成果
文献[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]	角度旋转协议	是	是