Privacy-Preserving Linear Region Search Service

被引:7
作者
Zhang, Hua [1 ]
Guo, Ziqing [1 ]
Zhao, Shaohua [1 ]
Wen, Qiaoyan [1 ]
机构
[1] Beijing Univ Posts & Telecommun, State Key Lab Networking & Switching Technol, Beijing 100876, Peoples R China
关键词
Cryptography; Indexes; Cloud computing; Algorithm design and analysis; Search problems; Outsourcing; Linear region search; privacy-preserving; location-based services; data outsourcing; cloud computing; RANGE QUERIES; CLOUD; SECURE;
D O I
10.1109/TSC.2017.2777970
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:207 / 221
页数:15
相关论文
共 50 条
  • [41] A Privacy-Preserving System for Targeted Coupon Service
    Yao, Jing
    Zheng, Yifeng
    Guo, Yu
    Cai, Chengjun
    Zhou, Anxin
    Wang, Cong
    Gui, Xiaolin
    [J]. IEEE ACCESS, 2019, 7 : 120817 - 120830
  • [42] Secure and Evaluable Clustering Based on a Multifunctional and Privacy-Preserving Outsourcing Computation Toolkit
    Li, Jialin
    Lu, Penghao
    Lin, Xuemin
    [J]. IEEE ACCESS, 2022, 10 : 39407 - 39423
  • [43] Attack on the Privacy-Preserving Carpooling Service TAROT
    Vargheese, Meghana
    Vivek, Srinivas
    [J]. INFORMATION SYSTEMS SECURITY, ICISS 2023, 2023, 14424 : 249 - 258
  • [44] Privacy-Preserving Group Closeness Maximization
    Zhao, Zihao
    Cao, Sijia
    Zhang, Hanlin
    Lin, Jie
    Kong, Fanyu
    Yu, Leyun
    [J]. 2024 33RD INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS, ICCCN 2024, 2024,
  • [45] Towards Efficient and Privacy-Preserving High-Dimensional Range Query in Cloud
    Sun, Lili
    Zhang, Yonggang
    Zheng, Yandong
    Song, Weiyu
    Lu, Rongxing
    [J]. IEEE TRANSACTIONS ON SERVICES COMPUTING, 2023, 16 (05) : 3766 - 3781
  • [46] Privacy-Preserving and Distributed Algorithms for Modular Exponentiation in IoT With Edge Computing Assistance
    Li, Hongjun
    Yu, Jia
    Zhang, Hanlin
    Yang, Ming
    Wang, Huaqun
    [J]. IEEE INTERNET OF THINGS JOURNAL, 2020, 7 (09) : 8769 - 8779
  • [47] Enabling Privacy-Preserving Parallel Computation of Linear Regression in Edge Computing Networks
    Gao, Wenjing
    Yu, Jia
    Wang, Huaqun
    [J]. IEEE TRANSACTIONS ON CLOUD COMPUTING, 2024, 12 (04) : 1103 - 1115
  • [48] BopSkyline: Boosting privacy-preserving skyline query service in the cloud
    Wang, Weibo
    Zheng, Yifeng
    Wang, Songlei
    Hua, Zhongyun
    Xu, Lei
    Gao, Yansong
    [J]. COMPUTERS & SECURITY, 2024, 140
  • [49] Privacy-preserving Image Processing in the Cloud
    Qin, Zhan
    Weng, Jian
    Cui, Yong
    Ren, Kui
    [J]. IEEE CLOUD COMPUTING, 2018, 5 (02): : 48 - 57
  • [50] Privacy-preserving horizontally partitioned linear programs
    Olvi L. Mangasarian
    [J]. Optimization Letters, 2012, 6 : 431 - 436