A Secure and Efficient Query Processing Algorithm 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 kNN query processing techniques have been proposed over the encrypted database. However, the existing schemes are either insecure or inefficient. Therefore, in this paper we propose a secure and efficient kNN query processing algorithm. Our algorithm preserves both data privacy and query privacy while hiding data access patterns. To achieve a high efficiency in query processing, we also propose efficient and secure protocols using Yao’s garbled circuit and a data packing technique. Through our performance analysis, we verify that our proposed scheme outperforms the existing schemes in terms of a query processing cost.

I. Introduction

Research on preserving data privacy in outsourced databases has been spotlighted with the development of a cloud computing. Since a data owner (DO) outsources his/her databases and allows a cloud to manage them, the DO can reduce the database management cost by using the cloud’s resources with flexibility [1]. The cloud not only maintains the databases, but also provides an authorized user (AU) with querying services on the outsourced databases.