Privacy-Preserving Linear Region Search Service

  • SCI-E
  • EI
作者: Hua Zhang;Ziqing Guo;Shaohua Zhao;Qiaoyan Wen
作者机构: Beijing University of Posts and Telecommunications, 12472 Beijing, Beijing China (e-mail: zhaoshaohua@bupt.edu.cn)
State Key Laboratory of Networking and Switch Technology, Beijing University of Posts and Telecommunications, Beijing, Beijing China (e-mail: wqy@bupt.edu.cn)
Beijing University of Posts and Telecommunications, 12472 Beijing, Beijing China (e-mail: guoziqing@bupt.edu.cn)
State Key Laboratory of Networking and Switch Technology, Beijing University of Posts and Telecommunications, Beijing, Beijing China (e-mail: zhanghua_288@bupt.edu.cn)
语种: 英文
关键词: Cryptography;Indexes;Cloud computing;Algorithm design and analysis;Search problems;Outsourcing;Linear region search;privacy-preserving;location-based services;data outsourcing;cloud computing
期刊: IEEE Transactions on Services Computing
ISSN: 1939-1374
年: 2021
摘要: Due to a variety of advantages of data outsourcing, some Location Based Services (LBS) providers are motivated to outsource the geographic data and query service to commercial cloud. However, for protecting data confidentiality, the valuable data should be encrypted before outsourcing, which obstructs the utilization like geographic information query. To address this problem, some previous works regarding to secure search on encrypted database could be applied in outsourced LBS scenario directly, but none of them is tailor-made for linear region search (LRS). The LRS is a kind of LBS that widely used in navigation system, it finds the nearby points of interest (POI) for a query segment. In this paper, for the first time, we explore and solve the challenging problem of privacy-preserving linear region search. Specifically, we choose the quadtree structure to build index for POI database, then the results of LRS can be efficiently obtained by finding out the rectangular regions that query segment passes through. In order to preserve the privacy of both LBS providers and users, according to computational geometry and Asymmetric Scalar-product Preserving Encryption (ASPE) approach, we design a novel algorithm for accurately determining whether a segment intersects with a rectangle on ciphertext. Moreover, this algorithm also provides a new idea to solve other computational problems in encrypted 2-dimensional geometry space. Based on different privacy requirements of two threat models, we propose two privacy-preserving LRS schemes and corresponding dynamic update operations. Security analysis and experiments on real-world dataset show that our schemes are secure and efficient.

文件格式:
导出字段:
导出
关闭
Privacy-Preserving Linear Region Search Service
有问题请联系我们,邮箱:常见的失败原因