Pseudorandom number encryption based location privacy preserving nearest neighbor querying

ZHANG Feng; NI Wei-wei

doi:10.3969/j.issn.1000-5641.2015.05.011

Issue 5

Oct. 2015

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2015 > (5): 128-142

ZHANG Feng, NI Wei-wei. Pseudorandom number encryption based location privacy preserving nearest neighbor querying[J]. Journal of East China Normal University (Natural Sciences), 2015, (5): 128-142. doi: 10.3969/j.issn.1000-5641.2015.05.011

Citation:

ZHANG Feng, NI Wei-wei. Pseudorandom number encryption based location privacy preserving nearest neighbor querying[J]. Journal of East China Normal University (Natural Sciences), 2015, (5): 128-142. doi: 10.3969/j.issn.1000-5641.2015.05.011

Citation:

PDF( 1637 KB)

Pseudorandom number encryption based location privacy preserving nearest neighbor querying

doi: 10.3969/j.issn.1000-5641.2015.05.011

ZHANG Feng,
NI Wei-wei^,

Received Date: 2015-07-09
Publish Date: 2015-09-25

Abstract

Abstract

The rapid development of positioning and mobile communication promotes the popularity of locationbased services. Nearest neighbor querying witness its thriving in locationbased services. With the increasing attention people pay to individual privacy, location privacy preserving k nearest neighbor querying becomes a hot topic. In recent years, private information retrieval techniques attract increasing concerning from researchers for its merits in providing high location protection strength, as well as its independence on any trusted thirdparty. A series of methods are proposed based on PIR to surmount the problem of location privacy protection in nearest neighbors querying. Most of them suffer from heavy time cost in preprocessing as well as query process. Concerning these problems, a novel PIR based method PRN_kNN is proposed to surmount above mentioned problems.The client can pinpoint the candidate k nearest neighbor set quickly by spatial encryption. Meanwhile, a pseudorandom number encryption schema is elaborated to avoid pattern attack and reduce the workload of preprocessing.Further, continuous storage policy for POI entity is adopted to avoid storing large amounts of fake entities in some blocks, which can enhance the efficiency of preprocessing and the querying process. Theoretical and empirical analysis demonstrate the effectiveness and efficiency of our method.
- locationbased serviceslocation privacy protectionprivate information retrievalpseudorandom number rule,

FullText(HTML)

References(1)

References

[1]

［1］ROUSSOPOULOS N, KELLEY S, VINCENT F. Nearest neighbor queries［C］Proceedings of the ACM Special Interest Group on Management of Data (SIGMOD’95). California, USA,1995: 7179.

［2］GRUTESER M, GRUNWAL D.Anonymous usage of location based services through spatial and temporal cloaking［C］Proceedings of the International Conference on Mobile Systems,Applications, and Services (MobiSys’03). California, USA, 2003:3142.

［3］MOKBEL M F, CHOW C Y, AREF W G. The new casper: Query processing for location services without compromising privacy［C］Proceedings of the International Conference on Very Large Data Bases (VLDB’06). Seoul, Korea, 2006: 763774.

［4］GEDIK B, LIU L. Location privacy in mobile systems: A personalized anonymization model［C］Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS’05). Ohio, USA, 2005:620629.

［5］朱怀杰, 王佳英, 王斌, 等. 障碍空间中保持位置隐私的最近邻查询方法［J］. 计算机研究与发展. 2014, 51(1): 115125.

［6］FIROOZJAEI M D, YU J, KIM H. Privacy preserving nearest neighbor search based on topologies in cellular networks［C］Proceedings of the IEEE International Conference on Advanced Information Networking and Applications Workshops. Suwon, Korea,2015: 146149.

［7］INDYK P, WOODRUFF D, Polylogarithmic private approximations and efficient matching［C］Proceedings of the Third Theory of Cryptography Conference(TCC’06), New York, USA, 2006: 245264.

［8］KHOSHGOZARAN A, SHAHABI C. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy［C］Proceedings of the International Symposium on Spatial and Temporal Databases (SSTD’07), Massachusetts, USA,2007: 239257.

［9］YIU M L, JENSEN C S, HUANG X, et al. Spacetwist:Managing the tradeoffs among location privacy, query performance, and query accuracy in mobile services［C］Proceedings of the IEEE International Conference on Data Engineering (ICDE’08). Cancun, Mexico, 2008: 366375.

［10］NI W W, ZHENG J W, CHONG Z H. HilAnchor:Location privacy protection in the presence of users’preferences［J］. Journal of Computer Science and Technology, 2012, 27(2): 413 427.

［11］GONG Z, SUN G, XIE X. Protecting privacy in locationbased servicesusing 〖WTBX〗k〖WTBZ〗anonymity without cloaked region［C］Proceedings of the International Conference on Mobile Data Management (MDM’10). Missouri, USA , 2010: 366371.

［12］CHOR B, GOLDREICH O, KUSHILEVITZ E, et al. Private information retrieval［C］Proceedings of the Thirtysixth Annual Symposium on Foundations of Computer Science (FOCS’95).Wisconsin, USA, 1995: 4150 .

［13］KHOSHGOZARAN A, SHAHABI C, SHIRANIMEHR H. Location privacy: Moving beyond 〖WTBX〗k〖WTBZ〗anonymity, cloaking and anonymizers［J］. Knowledge and Information Systems, 2011, 26(3): 435465 .

［14］GHINITA G, KAINIS P, KHOSHGOZARAN A, et al. Private queries in location based services: Anonymizersare not necessary［C］Proceedings of the ACM Special Interest Group on Management of Data (SIGMOD’08). British Columbia, Canada, 2008: 121132.

［15］PAPADOPOULOS S, BAKIRAS S, PAPADIAS D. Nearest neighbor search with strong location Privacy［C］Proceedings of the International Conference on Very Large Data Bases Endowment (VLDB’10). Singapore, 2010,3(1): 619629.

［16］王璐, 孟小峰. 位置大数据隐私保护研究综述［J］. 软件学报, 2014, 25(4): 693712.

［17］WILLIAMS P, SION R. Usable PIR［C］Proceedings of the Network and Distributed System Security Symposium (NDSS’08). California, USA, 2008:111.

［18］MOURATIDIS K, HADJIELEFTHERIOU M, PAPADIAS D. Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring［C］Proceedings of the ACM Special Interest Group on Management of Data (SIGMOD’05). Maryland, USA, 2005: 634645.

Relative Articles

Supplements(0)

Cited By

Proportional views