Secure k-nearest neighbor query over encrypted data in outsourced environments

Yousef Elmehdwi, Bharath K. Samanthula, Wei Jiang

TL;DR

This paper introduces two protocols for securely performing k-nearest neighbor (kNN) queries on encrypted data stored in the cloud. The first protocol offers a basic solution, while the second, more robust protocol, ensures data confidentiality, query privacy, and hides data access patterns, addressing critical security concerns in cloud outsourcing.

What Problem Does This Paper Address?

Cloud computing offers significant advantages in terms of cost and flexibility, leading many organizations to outsource their data and database management to cloud providers. However, this raises serious privacy concerns, especially for sensitive data like medical records. To protect this data, owners encrypt it before outsourcing. The challenge then becomes how to perform complex queries, such as kNN, on this encrypted data without decrypting it, all while ensuring that the cloud provider cannot learn anything about the data, the query itself, or even which data points are being accessed. Existing solutions often fall short, either by being insecure against attacks or by not fully preserving privacy.

Methods

The paper proposes two protocols: a basic, less secure one (SkNN♭) and a fully secure one (SkNNm). Both protocols leverage the Paillier cryptosystem for its additive homomorphic properties.

  • SkNN♭ (Basic Protocol): This protocol first encrypts the query and then uses a Secure Squared Euclidean Distance (SSED) protocol to compute the squared Euclidean distance between the encrypted query and each encrypted data record. The cloud provider (C2) then decrypts these distances to identify the top k nearest neighbors. Finally, the data is randomized and sent back to the user. This protocol is efficient but reveals data access patterns and intermediate distance values to the cloud.
  • SkNNm (Fully Secure Protocol): This protocol builds upon SkNN♭ but adds more robust security. It uses a Secure Bit-Decomposition (SBD) protocol to break down the encrypted distances into bits. Then, it employs a Secure Minimum out of n Numbers (SMINn) protocol to find the minimum distance in an encrypted form, ensuring that neither cloud provider knows which data points are the nearest neighbors. This iterative process, combined with randomization and secure protocols like Secure Bit-OR (SBOR), ensures that data confidentiality, query privacy, and data access patterns are all protected.

Datasets

The paper uses a sample heart disease dataset from the UCI Machine Learning Repository for illustrative purposes. For experimental evaluation, synthetic datasets were generated based on varying parameters like the number of data records (n), number of attributes (m), number of nearest neighbors (k), and encryption key size (K).

Key Insights and Ideas

  • The Trade-off Between Security and Efficiency: The paper clearly demonstrates that achieving strong privacy guarantees in secure kNN queries comes at a computational cost. SkNNm is significantly more secure than SkNN♭ but also more computationally intensive.
  • The Importance of Hiding Access Patterns: Simply encrypting data and queries isn't enough. The paper highlights that observing which data records are accessed during a query can reveal sensitive information, necessitating protocols that obscure these access patterns.
  • Leveraging Homomorphic Encryption for Complex Operations: The use of Paillier's homomorphic properties is crucial for performing computations (like distance calculation and finding minimums) directly on encrypted data without decryption.
  • The Power of Secure Multi-Party Computation (SMC) Primitives: The paper effectively utilizes various SMC primitives (like SSED, SBD, SMINn, SBOR) as building blocks to construct the secure protocols, showcasing their utility in privacy-preserving data processing.

Key Results

  • SkNN♭ Performance: The computation cost of SkNN♭ grows linearly with the number of data records (n) and attributes (m). It is largely independent of k (number of neighbors) but significantly affected by the encryption key size (K), increasing roughly by a factor of 7 when K doubles.
  • SkNNm Performance: SkNNm's running time grows almost linearly with k and l (domain size of attributes). Similar to SkNN♭, its cost increases significantly with larger key sizes. The SMINn protocol accounts for a substantial portion of SkNNm's cost.
  • Security: SkNNm is shown to protect data confidentiality, query privacy, and data access patterns. SkNN♭, while less secure, still offers some privacy guarantees.
  • End-User Efficiency: The paper emphasizes that the end-user's (Bob's) computational overhead is minimal, making it suitable for mobile devices.

Limitations and Future Work

  • Computational Cost of SkNNm: The fully secure SkNNm protocol is computationally more expensive than the basic SkNN♭ protocol.
  • Scalability: While the paper discusses parallelizing operations to improve performance, a full analysis of scalability on large datasets and distributed environments (e.g., using map-reduce) is left for future work.
  • Extension to Other Query Types: The authors suggest extending their research to other complex conjunctive queries over encrypted data.
  • Dataset Size: The experiments were conducted on synthetic datasets, and the authors note the difficulty of controlling parameters on real-world datasets.

The paper concludes that while SkNNm is more expensive, its enhanced security makes it a valuable solution for privacy-sensitive applications. The authors also suggest exploring parallel processing techniques to mitigate the performance overhead.

Summary updated

Abstract

For the past decade, query processing on relational data has been studied extensively, and many theoretical and practical solutions to query processing have been proposed under various scenarios. With the recent popularity of cloud computing, users now have the opportunity to outsource their data as well as the data management tasks to the cloud. However, due to the rise of various privacy issues, sensitive data (e.g., medical records) need to be encrypted before outsourcing to the cloud. In addition, query processing tasks should be handled by the cloud; otherwise, there would be no point to outsource the data at the first place. To process queries over encrypted data without the cloud ever decrypting the data is a very challenging task. In this paper, we focus on solving the k-nearest neighbor (kNN) query problem over encrypted database outsourced to a cloud: a user issues an encrypted query record to the cloud, and the cloud returns the k closest records to the user. We first present a basic scheme and demonstrate that such a naive solution is not secure. To provide better security, we propose a secure kNN protocol that protects the confidentiality of the data, user's input query, and data access patterns. Also, we empirically analyze the efficiency of our protocols through various experiments. These results indicate that our secure protocol is very efficient on the user end, and this lightweight scheme allows a user to use any mobile device to perform the kNN query.
BibTeX
@misc{elmehdwi2013secure,
  author = {Yousef Elmehdwi and Bharath K. Samanthula and Wei Jiang},
  title = {{Secure k-nearest neighbor query over encrypted data in outsourced environments}},
  year = {2013},
  eprint = {1307.4824},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1307.4824},
}
Figure