A new encrypt-then-index strategy has been developed to improve the efficiency and security of k-nearest neighbor (k-NN) queries on encrypted databases. This method provides significant improvements for privacy-preserving machine learning and secure biometric identification.

The innovative approach achieves sub-linear search complexity, facilitating swift and secure retrieval of data points. It supports dynamic updates without compromising security by leveraging spatial data structures such as the R-tree index, making it ideal for large-scale encrypted databases.

Cloud computing has revolutionized data management for businesses and governments, yet security concerns persist. Traditional secure k-NN query methods often face inefficiencies that hinder their practicality for large datasets. This new encrypt-then-index strategy addresses these challenges by combining encryption with efficient indexing techniques, enabling secure and efficient queries directly in the cloud.

"Our strategy is designed to enhance both efficiency and security in cloud computing," said Prof. Youwen Zhu, the lead researcher. "We believe it will lead to more secure and dynamic data management solutions."

Extensive analysis and experimentation have shown that this method meets and exceeds current security standards, offering greater efficiency and flexibility than existing solutions.

This research, published in Frontiers of Computer Science, is a collaborative effort between Nanjing University of Aeronautics and Astronautics, the University of Tokyo, Guilin University of Electronic Technology, and China University of Geosciences. The complete study is accessible via DOI: 10.1007/s11704-022-2401-1.