Source-linked AI summary
Secure k-Nearest Neighbor Query over Encrypted Data in Outsourced Environments
Yousef Elmehdwi, Bharath K. Samanthula, Wei Jiang
TL;DR
Cloud outsourcing creates a need to process sensitive encrypted databases without exposing data, queries, or access patterns. The paper develops secure kNN protocols using encrypted-distance and secure-minimum primitives, including a fully secure variant. Experiments report higher costs for the fully secure protocol but low end-user computation, while scalability improvement through parallelization remains future work.
Problem
Cloud users need kNN queries over outsourced encrypted data without the cloud learning database contents, query inputs, or data access patterns.
Method
The paper constructs basic and fully secure SkNN protocols from secure distance and secure minimum primitives.
Results
The fully secure SkNN protocol protects data confidentiality, query privacy, and access patterns, while experiments show significantly higher computation costs than the basic protocol but low user-end costs.
Takeaways & Limitations
The protocols trade efficiency for security, and the reported user-side workload supports lightweight encrypted kNN querying.
Takeaways & Limitations
Scalability improvement through parallelization and map-reduce is proposed but left for future work.
Abstract
from arXiv · showhide
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.
1 Introduction
Cloud outsourcing reduces data-management burden but creates confidentiality, query-privacy, and access-pattern challenges for encrypted kNN processing. The paper defines SkNN requirements and proposes protocols designed to preserve these protections while keeping user computation low.
- Cloud outsourcing offers cost and administrative benefits, but processing data outside the owner's control raises confidentiality and query-privacy challenges.
- Encrypted databases and queries protect stored data and user inputs, yet cloud query processing remains difficult without decrypting data.
- Secure kNN identifies the k-nearest tuples to encrypted query Q without revealing database contents or Q to the cloud.
- An effective SkNN protocol must preserve confidentiality, hide data access patterns, compute accurate neighbors, and impose low end-user overhead.
- The paper proposes a novel SkNN protocol intended to satisfy these security properties together.
- The proposed protocol keeps database contents, query inputs, intermediate results, and neighbor-related access patterns hidden while limiting Bob's computation.
2 Related Work and Background
This section frames secure kNN over encrypted cloud databases, reviews centralized and distributed approaches, and introduces the Paillier-based security setting. Existing methods leave gaps in exactness or security, motivating the paper’s protocol.
- Motivation: Cloud outsourcing reduces data-management costs but creates privacy risks involving database contents, query confidentiality, and access patterns.The paper focuses on querying encrypted data while the cloud provides database-management services.
- Existing Approaches: Centralized methods outsource encrypted databases and query processing to an untrusted service provider, whereas distributed methods partition plaintext data among non-colluding parties.The paper distinguishes these categories by deployment and data representation.
- Problem Setting: Secure kNN identifies the k records closest to an encrypted query without revealing database contents, query contents, or access patterns to the cloud.The paper restricts its discussion to secure evaluation of kNN queries over encrypted data.
- Existing Approaches: Prior SkNN methods include scalar-product-preserving encryption, Privacy Homomorphism encryption, and partition-based secure Voronoi diagrams.The partition-based method retrieves an encrypted partition guaranteed to contain the nearest neighbors rather than the exact kNN result.
- Contribution: The paper positions its protocol as accurate encrypted kNN and notes potential use in secure clustering, classification, and outlier detection.The broader applications are stated as possible uses of the proposed encrypted kNN capability.
- Security Background: The security model assumes semi-honest parties and defines security through computational indistinguishability of simulated protocol views from views generated using inputs and outputs.The background uses Paillier, an additive homomorphic and probabilistic asymmetric encryption scheme with semantic security.
3 Basic Security Primitives
The section develops encrypted-data primitives for secure kNN, including multiplication, distance computation, bit decomposition, minimum selection, and iterative minimum computation. These protocols keep intermediate outputs encrypted and use Paillier homomorphism with semi-honest two-party execution.
- Protocol Setting: The primitives operate in a two-party semi-honest setting where P2 holds Paillier’s secret key and P1 receives encrypted outputs.The protocols are intended as subroutines for the proposed SkNN protocol.
- Secure Multiplication: Secure Multiplication computes Epk(a ∗b) from encrypted inputs without revealing a or b to either party.P1 masks both inputs, P2 multiplies the decrypted masked values, and P1 removes the random factors homomorphically.
- Distance Computation: Secure Squared Euclidean Distance computes Epk(|X−Y|2) for encrypted m-dimensional vectors without revealing X or Y.P1 forms encrypted coordinate differences, invokes secure multiplication on each difference, and sums the encrypted squares locally.
- Bit Decomposition: Secure Bit-Decomposition converts encrypted z, with 0 ≤z < 2^l, into encryptions of its individual binary bits known only to P1.The paper adopts an existing efficient SBD protocol rather than investigating new SBD constructions.
- Secure Minimum: Secure Minimum compares encrypted bit representations of u and v and returns encrypted bits of min(u, v) without revealing either value.P1 randomly chooses one comparison direction, executes it obliviously, and derives the minimum bits using homomorphic operations.
- Secure Minimum out of n Numbers: Secure Minimum out of n Numbers iteratively applies SMIN in a hierarchical binary fashion to compute encrypted [min(d1, . . . , dn)].The resulting encrypted minimum is known only to P1, while the inputs remain undisclosed.
4 The Proposed Protocols
The paper presents a basic encrypted kNN protocol and a fully secure protocol built from secure computation primitives. The fully secure design protects query privacy, data confidentiality, and data access patterns while computing nearest neighbors iteratively.
- Fully secure protocol: The fully secure SkNNm protocol uses SSED, SBD, and SMINn to compute encrypted distances, compare minima, and iteratively identify the top k records.At each iteration, only C1 retains the encrypted minimum and selected encrypted record, while the remaining operations use randomized or permuted values.
- System model: The protocols use two non-colluding semi-honest cloud providers: C1 stores the encrypted database, while C2 holds the secret key.Users send encrypted queries to C1, and the providers jointly perform the query-processing subprotocols.
- Basic protocol: The basic SkNNb protocol encrypts the query, computes encrypted squared Euclidean distances, and lets C2 decrypt distances to select the nearest records.C1 randomizes the selected records before C2 decrypts them, allowing Bob to recover attributes using the randomization values.
- Basic protocol: SkNNb reveals distance values to C2 and exposes the k-nearest records’ access patterns to both cloud providers.It is therefore secure only under the assumption that these distance values and access patterns may be revealed.
- Security analysis: The security analysis states that SkNNm protects the database, the user query, and data access patterns from the cloud providers.The protocol uses semantic security for the encrypted query, randomized intermediate values, and permutation so decrypted components cannot be traced to records.
- Efficiency: SkNNb has computation complexity O(n ∗m + k), while SkNNm uses O(n) SBD and SSED, O(k) SMINn, and O(n ∗l) SBOR instantiations.For SkNNb, k ≪n ∗m in practice, giving a bound of O(n ∗m) encryptions and exponentiations.
5 Empirical Results
The experiments evaluate SkNNb and SkNNm under varied dataset, query, attribute-domain, and encryption-key parameters. SkNNb is substantially more efficient, while SkNNm provides stronger security and both protocols can exploit parallelism.
- Experimental setup: The experiments use synthetic encrypted datasets and evaluate SkNNb and SkNNm under varied parameter settings.The study varies record count, attributes, neighbors, attribute-domain size, and Paillier key size.
- Performance of SkNNb: SkNNb computation grows linearly with n and m, while changing k has little effect because most cost comes from SSED, which is independent of k.With m = 6 and K = 512, runtime rises from 44.08 to 87.91 seconds as n increases from 2000 to 4000; changing k from 5 to 25 changes runtime from 44.08 to 44.14 seconds.
- Encryption key size: Doubling K increases computation time by almost a factor of 7 for both protocols under fixed parameters.This trend is reported for SkNNb and SkNNm across the evaluated settings.
- Performance of SkNNm: SkNNm runtime grows almost linearly with k and l and is significantly higher than SkNNb's runtime.For K = 512 and l = 6, SkNNm increases from 11.93 to 55.65 minutes as k rises from 5 to 25; for l = 12, it increases from 20.68 to 97.8 minutes.
- Security-efficiency tradeoff: The protocols trade efficiency for security, with SkNNm more secure and SkNNb less costly; Bob's query-encryption cost is 4 milliseconds at K = 512 and 17 milliseconds at K = 1024.The reported end-user computation is therefore small compared with the protocol runtimes.
- Towards Performance Improvement: Per-record computations are independent, enabling parallelization; for n = 10000, parallel and serial SkNNb runtimes are 40 and 215.59 seconds, respectively.The authors also suggest map-reduce execution across multiple nodes as a possible further improvement.
6 Conclusion
The paper proposes two encrypted-cloud SkNN protocols: a basic scheme that leaks information and a fully secure scheme that protects data, query, and access-pattern confidentiality. The fully secure protocol is more expensive, and the authors identify broader encrypted conjunctive queries as future work.
- The paper addresses secure kNN query processing over encrypted data outsourced to the cloud.
- The proposed basic protocol leaks some information, whereas the second protocol protects data, query, and access-pattern confidentiality.
- The fully secure protocol is more expensive than the basic protocol, and extending the work to other complex conjunctive queries remains future work.