Visible to the public Fast and Secure kNN Query Processing in Cloud Computing

TitleFast and Secure kNN Query Processing in Cloud Computing
Publication TypeConference Paper
Year of Publication2020
AuthorsLei, X., Tu, G.-H., Liu, A. X., Xie, T.
Conference Name2020 IEEE Conference on Communications and Network Security (CNS)
Keywordscloud computing, commercial public clouds, cryptography, data privacy, data structure, data structures, encrypted data, fast and secure kNN query processing, fast location-based query, FSkNN, Geospatial analysis, geospatial data storage, Indexes, location based services, location-based services, LSPs, Measurement, nearest neighbor search, nearest neighbour methods, Predictive Metrics, process location-based queries, Protocols, pubcrawl, query processing, random Bloom filter, RBF, secure index, secure location-based query, secure range query protocol, tracking technology, untrusted cloud
AbstractAdvances in sensing and tracking technology lead to the proliferation of location-based services. Location service providers (LSPs) often resort to commercial public clouds to store the tremendous geospatial data and process location-based queries from data users. To protect the privacy of LSP's geospatial data and data user's query location against the untrusted cloud, they are required to be encrypted before sending to the cloud. Nevertheless, it is not easy to design a fast and secure location-based query processing scheme over the encrypted data. In this paper, we propose a Fast and Secure kNN (FSkNN) scheme to support secure k nearest neighbor (k NN) search in cloud computing. We reveal the inherent connection between an Sk NN protocol and a secure range query protocol and further describe how to construct FSkNN based on a secure range query protocol. FSkNN leverages a customized accuracy-assured strategy to ensure the result accuracy and adopts a data structure named random Bloom filter (RBF) to build a secure index for efficiently searching. We formally prove the security of FSkNN under the random oracle model. Our evaluation results show that FSkNN is highly practical.
Citation Keylei_fast_2020