SetRkNN: Efficient and Privacy-Preserving Set Reverse kNN Query in Cloud

The advance of cloud computing has driven a new paradigm of outsourcing large-scale data and data-driven services to public clouds. Due to the increased awareness of privacy protection, many studies have focused on addressing security and privacy issues in outsourced query services. Although many pr...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information forensics and security 2023-01, Vol.18, p.1-1
Main Authors: Zheng, Yandong, Lu, Rongxing, Zhu, Hui, Zhang, Songnian, Guan, Yunguo, Shao, Jun, Wang, Fengwei, Li, Hui
Format: Article
Language:English
Subjects:
Access pattern privacy
Algorithms
Cloud computing
Computational modeling
Cryptography
Cybersecurity
Data privacy
Efficiency
Encrypted data
Encryption
Homomorphic encryption
Indexes
Inverted prefix filter index
Privacy
Protocols
Queries
Servers
Set RkNN
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The advance of cloud computing has driven a new paradigm of outsourcing large-scale data and data-driven services to public clouds. Due to the increased awareness of privacy protection, many studies have focused on addressing security and privacy issues in outsourced query services. Although many privacy-preserving schemes have been proposed for various query types, the set reverse k nearest neighbors (RkNN) query is still an unexplored area. Even if some existing schemes can be adapted to achieve privacy-preserving set RkNN queries, they will suffer from linear search efficiency. As a steppingstone, in this paper, we propose an efficient and privacy-preserving set RkNN query scheme over encrypted data with sublinear query efficiency. Specifically, we first design an inverted prefix index to organize the set dataset and propose an algorithm to traverse the index with sublinear search efficiency. Then, we propose two oblivious data comparison protocols based on a symmetric homomorphic encryption (SHE) scheme and design the private filter/refinement protocols to preserve the privacy of index searching. After that, we propose an access pattern privacy-preserving set RkNN query scheme by using private filter/refinement protocols. Rigorous security analysis demonstrates that our scheme can protect data privacy and access pattern privacy. Experimental results indicate that our scheme is more efficient than the available naive solution in terms of computational costs and communication overheads.
ISSN:1556-6013
1556-6021
DOI:10.1109/TIFS.2022.3231785