Indexing dynamic encrypted database in cloud for efficient secure k-nearest neighbor query |
| |
Authors: | Xingxin LI Youwen ZHU Rui XU Jian WANG Yushu ZHANG |
| |
Affiliation: | 1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China2. Department of Mathematical Informatics, University of Tokyo, Tokyo 113-8654, Japan3. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China4. School of Computer Science, China University of Geosciences, Wuhan 430074, China |
| |
Abstract: | Secure -Nearest Neighbor (-NN) query aims to find nearest data of a given query from an encrypted database in a cloud server without revealing privacy to the untrusted cloud and has wide applications in many areas, such as privacy-preserving machine learning and secure biometric identification. Several solutions have been put forward to solve this challenging problem. However, the existing schemes still suffer from various limitations in terms of efficiency and flexibility. In this paper, we propose a new encrypt-then-index strategy for the secure -NN query, which can simultaneously achieve sub-linear search complexity (efficiency) and support dynamical update over the encrypted database (flexibility). Specifically, we propose a novel algorithm to transform the encrypted database and encrypted query points in the cloud. By indexing the transformed database using spatial data structures such as the R-tree index, our strategy enables sub-linear complexity for secure -NN queries and allows users to dynamically update the encrypted database. To the best of our knowledge, the proposed strategy is the first to simultaneously provide these two properties. Through theoretical analysis and extensive experiments, we formally prove the security and demonstrate the efficiency of our scheme. |
| |
Keywords: | cloud computing secure k-NN query sub-linear complexity dynamic update |
|
| 点击此处可从《Frontiers of Computer Science》浏览原始摘要信息 |
|
点击此处可从《Frontiers of Computer Science》下载全文 |
|