Secure and Efficient k-Nearest Neighbor Query with Privacy-Preserving Authentication

AbstractDealing with k-nearest neighbor (kNN) on untrusted cloud servers without revealing private information is an existing challenge. Although a large number of encryption and authentication techniques have been studied to guarantee data privacy and the integrity of results, there are defective in efficiency and security. This paper focuses on finding k-nearest neighbor (kNN) on encrypted data and verifying the query results. Firstly, this paper designs a novel index structure to support sub-linear computation. Based on it, we further propose a batch reading protocol for a faster read operator, by way of batch reading it is more suitable for large-scale kNN search. Secondly, all calculations are performed under ciphertext without clouds learning anything about the dataset, query and result, other indirect information such as access pattern privacy and intermediate result privacy also are guaranteed to resist the latest data recovery attacks. Moreover, this paper designs a verifiable strategy for secure kNN. Our verification process considers the privacy of authentication, which hides the confidential or unnecessary data in Verification Object using Paillier. This work integrates the index structure, verifiable structure and Paillier encryption to build secure and verifiable kNN scheme that gains strong privacy and low latency. Detailed experiments and analysis also are performed in this paper, and our schemes S-kQ and SV-kQ are an order of magnitude faster than the state-of-the-art work on real-world datasets.KeywordsSecure k-nearest neighbor queryPaillier encryptionLocation-based servicesAuthenticated data structure