A Privacy-Preserving kNN Classification Algorithm Using Yao's Garbled Circuit on Cloud Computing

With the prevalence of cloud computing, privacy-preserving database outsourcing has been spotlighted. To preserve both data privacy and query privacy from adversaries, databases need to be encrypted before being outsourced to the cloud. However, there exists the only kNN classification scheme over the encrypted databases in the cloud. Because the existing scheme suffers from high computation overhead, we proposed a secure and efficient kNN classification algorithm that conceals the resulting class label and data access patterns. In addition, our algorithm can support efficient kNN classification by using our encrypted index scheme and the Yao's garbled circuit. We show from our performance analysis that the proposed algorithm achieves about 17 times better performance than the existing scheme, in terms of classification time.