A kNN query processing algorithm using a tree index structure on the encrypted database

With the adoption of cloud computing, database outsourcing has emerged as a new platform. Due to the serious privacy concerns in the cloud, database need to be encrypted before being outsourced to the cloud. Therefore, various kNN query processing techniques have been proposed over the encrypted database. However, the existing schemes are either insecure or inefficient. So, we, in this paper, propose a new secure kNN query processing algorithm. Our algorithm guarantees the confidentiality of both the encrypted data and a user's query record. To achieve the high query processing efficiency, we also devise an encrypted index search scheme which can perform data filtering without revealing data access patterns. We show from our performance analysis that the proposed scheme outperforms the existing scheme in terms of a query processing cost while preserving data privacy.