Paper 52 (Research track)

Secure k-NN as a Service Over Encrypted Data in Multi-User Setting

Author(s): Gagandeep Singh, Akshar Kaul, Sameep Mehta

Abstract: Many enterprises are exploring utilizing cloud services for their IT needs. However, security of the outsourced data, both from external attacks and from cloud service provider, remain a big concern which hinders many enterprises from migrating to cloud. To handle this concern a new paradigm of ”Always Encrypted Data” has emerged. It utilizes advancements in the homomorphic encryption techniques to allow a set of computations to be directly performed on the encrypted data. This allows the Cloud Server (CS) to provide storage and analytics as a service over encrypted data. As a concrete use case, many encryption schemes have been proposed for securely processing k Nearest Neighbors (skNN) queries over encrypted data in the outsourced setting. Any secure kNN (skNN) should achieve the following properties : (1) Data Privacy (2) Key Confidentiality (3) Query Privacy (4) Query Controllability (5) Query Verification. However, most of the existing skNN solutions trust Query Users with the secret key of Data Owner and hence they are not able to provide Key Confidentiality, Query Controllability, and Query Verification. Recent work by [1] proposes a new skNN solution which claims to satisfy first four properties. However, on the detailed analysis, we found that Query Controllability of the proposed scheme can be broken. Specifically, we show an attack by which a Query User can generate a valid encryption of a new query point without any involvement of Data Owner. In this paper, we propose a new skNN solution which satisfies all the five property requirements. We provide security proofs to show that our proposed solution is provably secure. We also present detailed experimental results to showcase that our proposed scheme is efficient and can be deployed in real-world scenarios.

Keywords: Data Security; Encryption; Cloud Computing; k-nearest neighbors

Share on

Leave a Reply

Your email address will not be published. Required fields are marked *