首页|Indexing dynamic encrypted database in cloud for efficient secure k-nearest neighbor query

Indexing dynamic encrypted database in cloud for efficient secure k-nearest neighbor query

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
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-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 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.

cloud computingsecure k-NN querysub-linear complexitydynamic update

Xingxin LI、Youwen ZHU、Rui XU、Jian WANG、Yushu ZHANG

展开 >

College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

Department of Mathematical Informatics,University of Tokyo,Tokyo 113-8654,Japan

Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China

School of Computer Science,China University of Geosciences,Wuhan 430074,China

展开 >

National Key R&D Program of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaKey R&D Program of Guangdong ProvinceNatural Science Foundation of Jiangsu ProvinceNatural Science Foundation of Jiangsu ProvinceResearch Fund of Guangxi Key Laboratory of Trusted SoftwareJSPS Postdoctoral Fellowships for Research in Japan

2020YFB1005900621722166203202562071222U20A2010922020B0101090002BK20211180BK20200418KX202034P21073

2024

10.1007/s11704-022-2401-1

计算机科学前沿
高等教育出版社

计算机科学前沿

CSTPCDEI
影响因子：0.303
ISSN：2095-2228
年,卷(期)：2024.18(1)
  • 47