A Secure and Efficient kNN Classification Algorithm using Encrypted Index Search and Yao’s Garbled Circuit over Encrypted Databases

EasyChair Preprint no. 286

Abstract

Database outsourcing has been popular according to the development of cloud computing. Databases need to be encrypted before being outsourced to the cloud so that they can be protected from adversaries. However, the existing kNN classification scheme over encrypted databases in the cloud suffers from high computation overhead. So we proposed a secure and efficient kNN classification algorithm using encrypted index search and Yao’s garbled circuit over encrypted databases. Our algorithm can preserve data privacy, query privacy, and data access pattern. We show that our algorithm achieves about 17 times better performance on classification time than the existing scheme, while preserving high security level.

Keyphrases: Cloud Computing, data privacy, Database outsourcing, Hiding data access pattern, KNN classification algorithm, Query protection

@Booklet{EasyChair:286,
  author = {Hyeong-Jin Kim and Jae-Hwan Shin and Jae-Woo Chang},
  title = {A Secure and Efficient kNN Classification Algorithm using Encrypted Index Search and Yao’s Garbled Circuit over Encrypted Databases},
  howpublished = {EasyChair Preprint no. 286},
  doi = {10.29007/cm65},
  year = {EasyChair, 2018}}