LBS中面向协同位置隐私保护的群组最近邻查询

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

摘要/Abstract

摘要：

在分析现有群组最近邻查询中位置隐私保护的基础上，提出LBS中一种面向位置隐私保护的群组最近邻查询方法。该方法采用分布式系统结构，克服了集中式匿名系统结构所存在通信瓶颈和攻击重点的缺陷。在此基础上根据用户群组的运动状态信息，提出使用位置随机扰动和门限秘密共享的Paillier密码系统来安全地计算用户群组的质心位置。于是将用户群组的最近邻查询转换为此质心的最近邻查询。与现有的相关工作相比，理论分析表明所提有关方案能够在有效抵御现有的距离交叉攻击和共谋攻击下，实现灵活的群组最近邻查询，同时耗费较低的网络资源。

关键词: 分布式系统结构, 群组最近邻查询, 位置隐私, 质心位置

Abstract:

On the basis of analyzing the existing location privacy protections in GNN queries, a GNN queries method for location privacy protection in LBS was proposed. In this method, a distributed system structure for GNN was adopted to overcome the disadvantages of centralized anonymous system structure such as making a communication bottleneck and being a vulnerable point of attack. According to the motion status of a user group, two methods on the basis of this struc-ture, named location random perturbation and threshold secret sharing version of Paillier cryptosystem, were used to se-curely compute the center location of the user group. Then these users' GNN queries had been turned into NN queries of the group center. Compared with existing related work, theoretical analysis proves that the proposal can effectively resist against the existing distance interaction attack and collusion attack and achieve flexible GNN queries, while it costs lower network resources.

Key words: distributed system architecture, group nearest neighbor query, location privacy, center location

高胜,马建峰,姚青松,孙聪. LBS中面向协同位置隐私保护的群组最近邻查询[J]. 通信学报, 2015, 36(3): 12-20.

Sheng GAO,Jian-feng MA,Qing-song YAO,Cong SUN. Towards cooperation location privacy-preserving group nearest neighbor queries in LBS[J]. Journal on Communications, 2015, 36(3): 12-20.

图/表 4

参考文献 29

[1]	周傲英，杨彬，金澈清等．基于位置的服务：架构与进展[J]．计算机学报， 2011,34(7):1155-1171. ZHOU A Y , YANG B , JIN C Q , et al. Location-based services:archi-tecture and progress[J]. Chinese Journal of Computers, 2011,34(7):1155-1171.
[2]	VIRRANTAUS K , MARKKULA J , GARMASH A , et al. Developing GIS-supported location-based services[A]. WISE[C]. Kyoto, 2001.66-75.
[3]	GRUTESTER M , GRUNWALD D . Anonymous usage of loca-tion-based services through spatial and temporal cloaking[A]. Mobi-Sys[C]. USA, 2003.31-42.
[4]	SWEENEY L . k-Anonymity: a model for protecting privacy[J]. International Journal on Uncertainty, Fuzziness and Konwledge Based Systems, 2002,10(5):557-570.
[5]	CHOW C Y , MOKBEL M F . Privacy in location-based services: a system architecture perspective[J]. SIGSPATIAL Special, 2009,1(2):23-27.
[6]	MOKBEL M F , CHOW C Y , AREF W G . The new Casper: query processing for location services without compromising privacy[A]. VLDB[C]. Seoul Korea, 2006.763-774.
[7]	XIAO Z , MENG X , XU J . Quality aware privacy protection for loca-tion-based services[A]. DASFAA[C]. Thailand, 2007.434-446.
[8]	GEDIK B , LIU L . Protecting location privacy with personalized k-anonymity: architecture and algorithms[J]. IEEE Transactions on Mobile Computing, 2008,7(1):1-18.
[9]	BAMBA B , LIU L , PESTI P , et al. Supporting anonymous location queries in mobile environments with privacygrid[A]. WWW[C]. Bei-jing, China, 2008.237-246.
[10]	WANG Y , XU D , HE X , et al. L2P2:location-aware location privacy protection for location-based services[A]. INFOCOM[C]. Orlando, FL, USA, 2012.1996-2004.
[11]	SHOKRI R , THEODORAKOPOULOS G , TRONCOSO C , et al. Protecting location privacy: optimal strategy against localization at-tacks[A]. CCS[C]. North Carolina, USA, 2012.617-627.
[12]	GAO S , MA J F , SHI W S , et al. LTPPM: a location and trajectory privacy protection mechanism in participatory sensing[J]. Wireless Communications and Mobile Computing, 2015,15(1):155-169.
[13]	GHINITA G , KALNIS P , KHOSHGOZARAN A , et al. Private queries in location based services: anonymizers are not necessary[A]. ACM SIGMOD[C]. Vancouver, BC, Canada, 2008.121-132.
[14]	YIU M L , JENSEN C S , HUANG X , et al. SpaceTwist:managing the trade-offs among location privacy, query performance, and query ac-curacy in mobile services[A]. ICDE[C]. Mexico, 2008.366-375.
[15]	HASHEM T , KULIK L . Don't trust anyone: privacy protection for location-based services[J]. Pervasive and Mobile Computing, 2011,7(1):44-59.
[16]	PAPADIAS D , SHEN Q , TAO Y , et al. Group nearest neighbor queries[A]. ICDE[C]. MA, USA, 2004.301-312.
[17]	PAPADIAS D , TAO Y , MOURATIDIS K , et al. Aggregate nearest neighbor queries in spatial databases[J]. ACM Transactions on Data-base Systems, 2005,30(2):529-576.
[18]	LIAN X , L CHEN , LIAN X , et al. Probabilistic group nearest neighbor queries in uncertain databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2008,20(6):809-824.
[19]	HASHEM T , KULIK L , ZHANG R . Privacy preserving group nearest neighbor queries[A]. EDBT[C]. Lausanne, 2010.489-500.
[20]	HUANG Y , VISHWANATHAN R . Privacy preserving group nearest neighbour queries in location-based services using cryptographic techniques[A]. GLOBECOM[C]. Miami, FL, 2010.1-5.
[21]	ASHOURI-TALOUKI M , BARAANI-DASTJERDI A , SELCUK A A . GLP: a cryptographic approach for group location privacy[J]. Computer Communications, 2012,35(12):1527-1533.
[22]	SOLANAS A , MARTINEZ-BALLESTE A . A TTP-free protocol for location privacy in location-based services[J]. Computer Communications, 2008,31(6):1181-1191.
[23]	CHOW C Y , MOKBEL M F , LIU X . A peer-to-peer spatial cloaking algorithm for anonymous location-based service[A]. SIGSPATIAL GIS[C]. New York, NY, USA, 2006.171-178.
[24]	CHE Y , YANG Q , HONG X . A dual-active spatial cloaking algorithm for location privacy preserving in mobile peer-to-peer networks[A]. WCNC[C]. Paris, France, 2012.2098-2102.
[25]	FOUQUE P A , POUPARD G , STERN J . Sharing decryption in the context of voting or lotteries[A]. FC[C]. London, 2001.90-104.
[26]	雷浩等．面向有差异群体的联合决策方案[J]．电子学报， 2005,33(8):1523-1528. LEI H , et al. A joint decision-making scheme for groups with members having different superiorities[J]. Chinese Journal of Electronics, 2005,33(8):1523-1528.
[27]	SHAMIR A . How to share a secret[J]. Communications of the ACM, 1979,22(11):612-613.
[28]	PAILLIER P . Public-key cryptosystems based on composite degree residuosity classes[A]. EUROCRYPT[C]. Prague, 1999.223-238.
[29]	DAMGARD I , FAZIO N , NICOLOSI A . Non-interactive zero-knowledge from homomorphic encryption[A]. TCC[C]. New York, NY, USA, 2006.41-59.

方案	计算方法	通信方式	网络资源	用户状态	查询点个数	结果集大小	共谋用户个数k'
文献[19]	距离和	环形单播	低	没有考虑	k	O(n)	k'=0
文献[21]	质心	群组广播	高	没有考虑	1	O(1)	1≤k'＜k-1
文献[22]	质心	环形单播	低	静态/动态	1	O(1)	k'=1
本文	质心	星型单播	低	静态/动态	1	O(1)	1≤k'＜k-1