Secure k-Nearest Neighbor(k-NN)query aims to find k 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,s...Secure k-Nearest Neighbor(k-NN)query aims to find k 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-preservingmachine elearning gand 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 k-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 k-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.展开更多
基金support by the National Key R&D Program of China(No.2020YFB1005900)the National Natural Science Foundation of China(Grant Nos.62172216,62032025,62071222,U20A201092)+3 种基金the Key R&D Program of Guangdong Province(No.2020B0101090002)the Natural Science Foundation of Jiangsu Province(No.BK20211180,BK20200418)the Research Fund of Guangxi Key Laboratory of Trusted Software(No.KX202034)JSPS Postdoctoral Fellowships for Research in Japan(No.P21073).
文摘Secure k-Nearest Neighbor(k-NN)query aims to find k 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-preservingmachine elearning gand 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 k-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 k-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.
