基于维诺图的位置隐私最近邻查询方法
|
摘要
针对K-匿名、空间匿名、位置模糊等隐私保护方法易受推理攻击及连续多查询攻击的不足,提出了一种抗连续多查询攻击的基于维诺图的位置隐私最近邻查询算法.该算法基于K-匿名思想以及维诺图算法,在可信第三方生成K-匿名集,用基于位置的服务(location based service,LBS)运营方服务器上存储的兴趣点(point of interest,POI)划分维诺图,基于用户与POI之间的邻近关系生成关系矩阵;用K-匿名集生成的离散维诺图构成匿名空间,以抵抗多查询攻击,保护用户位置隐私安全;用私有信息检索(privacy information retrieval,PIR)技术保护用户兴趣点查询隐私的安全.在保证关系矩阵匿名度的同时,也确保了K-匿名集的用户查询位置语义的单一性,以不同的维诺图划分集合,确保了l-多样性.
With the rapid development of location services,the problem of privacy disclosure in location queries is becoming more and more severe.A variety of privacy protection algorithms came into being.To overcome the shortcomings of K-anonymous,spatial anonymity,location blur and other privacy protection methods,a location nearest neighbor query method based on Voronoi Mapagainst continuous multi-query attacks was proposed.Based on the K-anonymous idea and the Voronoi Map algorithm,the K-user anonymous set was generated by the trusted third party,and the Vino diagram was divided by the point of interest(POI) stored in the LBS server.The relationship matrix was generated by the distance between the user and the POI.The discrete Vino chart generated by the K-anonymous user set constituted an anonymous space to resist multi-query attacks and protected the user's location from privacy.User interest point query privacy was protected by private information retrieval technology.While ensuring the anonymity of the relation matrix,the singularity of the semantics of user and l-diversity was by dividing the set with different Vino diagrams.By the method,not only the privacy of location information and query information was ensured,but also the process of security,server-side security and the efficiency of the query were guaranteed.
With the rapid development of location services,the problem of privacy disclosure in location queries is becoming more and more severe.A variety of privacy protection algorithms came into being.To overcome the shortcomings of K-anonymous,spatial anonymity,location blur and other privacy protection methods,a location nearest neighbor query method based on Voronoi Mapagainst continuous multi-query attacks was proposed.Based on the K-anonymous idea and the Voronoi Map algorithm,the K-user anonymous set was generated by the trusted third party,and the Vino diagram was divided by the point of interest(POI) stored in the LBS server.The relationship matrix was generated by the distance between the user and the POI.The discrete Vino chart generated by the K-anonymous user set constituted an anonymous space to resist multi-query attacks and protected the user's location from privacy.User interest point query privacy was protected by private information retrieval technology.While ensuring the anonymity of the relation matrix,the singularity of the semantics of user and l-diversity was by dividing the set with different Vino diagrams.By the method,not only the privacy of location information and query information was ensured,but also the process of security,server-side security and the efficiency of the query were guaranteed.
引文
[1]杨松涛,马春光.随机匿名的位置隐私保护方法[J].哈尔滨工程大学学报,2015,36(3):374-378.YANG S T,MA C G.Location privacy protection method based on random anonymity[J].Journal of Harbin Engineering University,2015,36(3):374-378.(in Chinese)
[2]SHIN K G,JU X,CHEN Z,et al.Privacy protection for users of location-based services[J].Wireless Communications IEEE,2012,19(1):30-39.
[3]SHOKRI R,THEODORAKOPOULOS G,TRONCOSO C,et al.Protecting location privacy:optimal strategy against localization attacks[C]∥Proceedings of ACM Conference on Computer and Communications Security.New York:ACM Press,2012:617-627.
[4]CHOW C Y.A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]∥Proceedings of ACM International Symposium on Advances in Geographic Information Systems.New York:ACM Press,2006:171-178.
[5]KALNIS P,GHINITA G,MOURATIDIS K,et al.Preventing location-based identity inference in anonymous spatial queries[J].IEEE Transactions on Knowledge&Data Engineering,2007,19(12):1719-1733.
[6]GHINITA G,KALNIS P,SKIADOPOULOS S,et al.Mobi Hide:a mobilea peer-to-peer system for anonymous location-based queries[M].Berlin:Springer-Verlag,2008:221-238.
[7]XU T,CAI Y.Feeling-based location privacy protection for location-based services[C]∥Proceedings of ACM Conference on Computer and Communications Security.New York:ACM Press,2009:348-357.
[8]BAMBA B,LIU L,PESTI P,et al.Supporting anonymous location queries in mobile environments with privacygrid[C]∥Proceedings of the 17th International Conference on World Wide Web.New York:ACM Press,2008:237-246.
[9]XIAO X,LI F,YAO B,et al.Secure nearest neighbor revisited[C]∥Proceedings of IEEE International Conference on Data Engineering.Piscataway:IEEE Press,2013:733-744.
[10]BENISCH M,KELLEY P G,SADEH N,et al.Capturinglocation-privacy preferences:quantifying accuracy and user-burden tradeoffs[J].Personal and Ubiquitous Computing,2011,15(7):679-694.
[11]霍峥,孟小峰.轨迹隐私保护技术研究[J].计算机学报,2011(10):1820-1830.HUO Z,MENG X F.A survey of trajectory privacypreserving techniques[J].Journal of Computers,2011(10):1820-1830.(in Chinese)
[12]GHINITA G,KALNIS P,KHOSHGOZARAN A,et al.Private queries in location based services:anonymizers are not necessary[C]∥Proceedings of ACM SIGMOD International Conference on Management of Data.New York:ACM Press,2008:121-132.
[13]KHOSHGOZARAN A,SHAHABI C,SHIRANI-MEHR H,et al.Location privacy:going beyond K-anonymity,cloaking and anonymizers[M].New York:SpringerVerlag,2011:435-465.
[14]WANG S,CHEN C,TING I,et al.Multi-layer partition for query location anonymization[C]∥Proceedings of the2012 IEEE International Conference on Systems.Piscataway:IEEE Press,2012:378-383.
[15]CHOW C Y,MOKBEL M F,LIU X,et al.Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].Goo Informatica,2011,15(2):351-380.
[16]REEM D.An algorithm for computing voronoi diagrams of general generators in general normed spaces[C]∥Sixth International Symposium on Voronoi Diagrams.Piscataway:IEEE Press,2009:144-152.
[17]REEMD.The geometric stability of voronoi diagrams with respect to small changes of the sites[C]∥Twenty-Seventh Symposium on Computational Geometry.New York:ACM Press,2011:254-263.
[18]PALANISAMY B,LIU L.MOBIMIX:protecting location privacy with mix-zones over road networks[C]∥Proceedings of International Conference on Data Engineering.Piscataway:IEEE Press,2011:494-505.
[19]薛姣,刘向宇,杨晓春,等.一种面向公路网络的位置隐私保护方法[J].计算机学报,2011,34(5):865-878.XUE J,LIU X Y,YANG X C,et al.Location privacy protection method for road network[J].Chinese Journal of Computers,2011,34(5):865-878.(in Chinese)
[2]SHIN K G,JU X,CHEN Z,et al.Privacy protection for users of location-based services[J].Wireless Communications IEEE,2012,19(1):30-39.
[3]SHOKRI R,THEODORAKOPOULOS G,TRONCOSO C,et al.Protecting location privacy:optimal strategy against localization attacks[C]∥Proceedings of ACM Conference on Computer and Communications Security.New York:ACM Press,2012:617-627.
[4]CHOW C Y.A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]∥Proceedings of ACM International Symposium on Advances in Geographic Information Systems.New York:ACM Press,2006:171-178.
[5]KALNIS P,GHINITA G,MOURATIDIS K,et al.Preventing location-based identity inference in anonymous spatial queries[J].IEEE Transactions on Knowledge&Data Engineering,2007,19(12):1719-1733.
[6]GHINITA G,KALNIS P,SKIADOPOULOS S,et al.Mobi Hide:a mobilea peer-to-peer system for anonymous location-based queries[M].Berlin:Springer-Verlag,2008:221-238.
[7]XU T,CAI Y.Feeling-based location privacy protection for location-based services[C]∥Proceedings of ACM Conference on Computer and Communications Security.New York:ACM Press,2009:348-357.
[8]BAMBA B,LIU L,PESTI P,et al.Supporting anonymous location queries in mobile environments with privacygrid[C]∥Proceedings of the 17th International Conference on World Wide Web.New York:ACM Press,2008:237-246.
[9]XIAO X,LI F,YAO B,et al.Secure nearest neighbor revisited[C]∥Proceedings of IEEE International Conference on Data Engineering.Piscataway:IEEE Press,2013:733-744.
[10]BENISCH M,KELLEY P G,SADEH N,et al.Capturinglocation-privacy preferences:quantifying accuracy and user-burden tradeoffs[J].Personal and Ubiquitous Computing,2011,15(7):679-694.
[11]霍峥,孟小峰.轨迹隐私保护技术研究[J].计算机学报,2011(10):1820-1830.HUO Z,MENG X F.A survey of trajectory privacypreserving techniques[J].Journal of Computers,2011(10):1820-1830.(in Chinese)
[12]GHINITA G,KALNIS P,KHOSHGOZARAN A,et al.Private queries in location based services:anonymizers are not necessary[C]∥Proceedings of ACM SIGMOD International Conference on Management of Data.New York:ACM Press,2008:121-132.
[13]KHOSHGOZARAN A,SHAHABI C,SHIRANI-MEHR H,et al.Location privacy:going beyond K-anonymity,cloaking and anonymizers[M].New York:SpringerVerlag,2011:435-465.
[14]WANG S,CHEN C,TING I,et al.Multi-layer partition for query location anonymization[C]∥Proceedings of the2012 IEEE International Conference on Systems.Piscataway:IEEE Press,2012:378-383.
[15]CHOW C Y,MOKBEL M F,LIU X,et al.Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].Goo Informatica,2011,15(2):351-380.
[16]REEM D.An algorithm for computing voronoi diagrams of general generators in general normed spaces[C]∥Sixth International Symposium on Voronoi Diagrams.Piscataway:IEEE Press,2009:144-152.
[17]REEMD.The geometric stability of voronoi diagrams with respect to small changes of the sites[C]∥Twenty-Seventh Symposium on Computational Geometry.New York:ACM Press,2011:254-263.
[18]PALANISAMY B,LIU L.MOBIMIX:protecting location privacy with mix-zones over road networks[C]∥Proceedings of International Conference on Data Engineering.Piscataway:IEEE Press,2011:494-505.
[19]薛姣,刘向宇,杨晓春,等.一种面向公路网络的位置隐私保护方法[J].计算机学报,2011,34(5):865-878.XUE J,LIU X Y,YANG X C,et al.Location privacy protection method for road network[J].Chinese Journal of Computers,2011,34(5):865-878.(in Chinese)