Privacy-preserving kNN query processing algorithms via secure two-party computation over encrypted database in cloud computing

Since studies on privacy-preserving database outsourcing have been spotlighted in a cloud computing, databases need to be encrypted before being outsourced to the cloud. Therefore, a couple of privacy-preserving k NN query processing algorithms have been proposed over the encrypted database. However, the existing algorithms are either insecure or inefficient. Therefore, in this paper we propose a privacy-preserving k NN query processing algorithm via secure two-party computation on the encrypted database. Our algorithm preserves both data privacy and query privacy while hiding data access patterns. For this, we propose efficient and secure protocols based on Yao’s garbled circuit. To achieve a high degree of efficiency in query processing, we also propose a parallel k NN query processing algorithm using encrypted random value pool. Through our performance analysis, we verify that our proposed algorithms outperform the existing ones in terms of a query processing cost.