Parallelly Running k-Nearest Neighbor Classification Over Semantically Secure Encrypted Data in Outsourced Environments

Abstract

Cloud services with powerful resources are popularly used to manage exponentially increasing data and to carry out data mining to analyze the data. However, a data mining involving query can cause privacy problems by disclosing both the data and the query. One task in data mining, classification, is used in a wide range of applications, and we focus on <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-nearest neighbor (<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>NN) in this study to realize classification. Although several studies have already attempted to address the privacy problems associated with <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>NN computation in a cloud environment, the results of these studies are still inefficient. In this paper, we propose a very efficient and privacy-preserving <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>NN classification (<inline-formula> <tex-math notation="LaTeX">$\text{P}k$ </tex-math></inline-formula>NC) over encrypted data. While the amount of computation (encryptions/decryptions and exponentiations) and communication of the most efficient <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>NN classification proposed in prior studies is bounded by <inline-formula> <tex-math notation="LaTeX">$O(kln)$ </tex-math></inline-formula>, that of the proposed <inline-formula> <tex-math notation="LaTeX">$\text{P}k$ </tex-math></inline-formula>NC is bounded by <inline-formula> <tex-math notation="LaTeX">$O(ln)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$l$ </tex-math></inline-formula> is the domain size of data and <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is the number of data. When conducting experiments with the same dataset, the prior <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>NN classification took 12.02 to 55.5 minutes but <inline-formula> <tex-math notation="LaTeX">$\text{P}k$ </tex-math></inline-formula>NC took 4.16 minutes. Furthermore, since <inline-formula> <tex-math notation="LaTeX">$\text{P}k$ </tex-math></inline-formula>NC allows to be carried out in parallel for each data, its performance can be improved extremely if it is carried out on machine to allow more numerous threads. <inline-formula> <tex-math notation="LaTeX">$\text{P}k$ </tex-math></inline-formula>NC protects the privacy of dataset, input query including the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>NN result, and does not disclose any data access patterns. We propose several protocols to serve as building blocks to construct <inline-formula> <tex-math notation="LaTeX">$\text{P}k$ </tex-math></inline-formula>NC and formally prove their security. In particular, we propose efficient protocols that privately find <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> largest or smallest elements in array.