LFRkNN: Towards Leakage-Free Reverse K-Nearest Neighbor Queries on Encrypted Data
摘要
The reverse k-nearest neighbor (RkNN) query is a practical and classic problem. Cloud computing enables data service providers to offer this service efficiently. However, existing solutions risk leaking sensitive information, such as access patterns and volume patterns. This paper presents LFRkNN, the first leakage-free RkNN scheme that protects data, queries, results, access patterns, and volume patterns. Our approach is threefold. First, we design an oblivious non-overlapping spatial index. This index is optimized for both query efficiency and volume pattern hiding. Second, we propose several secret-sharing-based secure protocols for oblivious index traversal, thus protecting access patterns. Furthermore, we extend our scheme to LFRkNN-E, which additionally conceals the query parameter k. We formally prove the security of our schemes under the semi-honest model and demonstrate their efficiency through extensive experiments.