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  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