A new encrypt-then-index strategy is in development in an effort to improve the efficiency and security of k-nearest neighbor (k-NN) queries on encrypted databases, which can improve privacy-preserving machine learning and secure biometric identification.

The 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 enhances both efficiency and security in cloud computing,” said Prof. Youwen Zhu, the lead researcher and professor at Nanjing University of Aeronautics and Astronautics in China. “We believe it will lead to more secure and dynamic data management solutions.”

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

Schneider Bold

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.

Secure 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.

System model of secure k-NN query.
Source: Youwen Zhou


A new encrypt-then-index strategy is now in development for the secure k-NN query, which can simultaneously achieve sub-linear search complexity (efficiency) and support dynamical update over the encrypted database (flexibility).

A novel algorithm can 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, the strategy enables sub-linear complexity for secure k-NN queries and allows users to dynamically update the encrypted database.

This strategy can simultaneously provide these two properties. Through theoretical analysis and extensive experiments, it is possible to prove the security and demonstrate the efficiency of the scheme.

Pin It on Pinterest

Share This