Abstract
The k-nearest neighbors (k-NN) algorithm is a popular and effective classification algorithm. Due to its large storage and computational requirements, it is suitable for cloud outsourcing. However, k-NN is often run on sensitive data such as medical records, user images, or personal information. It is important to protect the privacy of data in an outsourced k-NN system. Prior works have all assumed the data owners (who submit data to the outsourced k-NN system) are a single trusted party. However, we observe that in many practical scenarios, there may be multiple mutually distrusting data owners. In this work, we present the first framing and exploration of privacy preservation in an outsourced k-NN system with multiple data owners. We consider the various threat models introduced by this modification. We discover that under a particularly practical threat model that covers numerous scenarios, there exists a set of adaptive attacks that breach the data privacy of any exact k-NN system. The vulnerability is a result of the mathematical properties of k-NN and its output. Thus, we propose a privacy-preserving alternative system supporting kernel density estimation using a Gaussian kernel, a classification algorithm from the same family as k-NN. In many applications, this similar algorithm serves as a good substitute for k-NN. We additionally investigate solutions for other threat models, often through extensions on prior single data owner systems.
Introduction
As organizations increasingly rely on cloud infrastructure for machine learning tasks, the security of outsourced computation has become a primary concern. The k-nearest neighbors (k-NN) algorithm is a cornerstone of classification, yet its application to sensitive datasets—such as medical records or biometric data—requires rigorous privacy protections. While extensive research has focused on "private k-NN," most existing solutions operate under the assumption of a single, trusted data owner who provides the entire dataset to the cloud.
This paper identifies a critical gap in this paradigm: in many real-world applications, data is contributed by multiple, mutually distrusting entities. For instance, several hospitals might wish to collaborate on a diagnostic model without sharing raw patient data with each other or the cloud provider. The authors demonstrate that in this multi-owner setting, exact k-NN is vulnerable to a "triangulation" attack. An adversarial data owner can inject carefully crafted "probe" points into the system. By observing how these probes affect the classification of specific queries, the attacker can mathematically derive the exact values of other owners' private data points.
Methodology: From k-NN to Gaussian KDE
The fundamental privacy leak in k-NN stems from its discrete nature. Because only the $k$ closest points influence the result, there is a clear "boundary" where a point enters or leaves the neighborhood. This binary signal provides the side-channel information necessary for distance-learning attacks.
To address this, the authors propose a shift to Kernel Density Estimation (KDE) using a Gaussian kernel. Unlike k-NN, which has a finite "influence zone," the Gaussian kernel has "infinite width." Mathematically, every data point in the system exerts some degree of influence on every query, weighted by its distance. This "blurring" of the neighborhood eliminates the discrete signals that enable triangulation.
The proposed system utilizes a multi-party computation (MPC) framework involving two non-colluding cloud entities: a Data Host and a Cryptographic Service Provider (CSP). The workflow is as follows:
- Encrypted Storage: Data owners upload their records encrypted using the Paillier Cryptosystem, a partially homomorphic scheme.
- Distance Computation: The Data Host computes the squared Euclidean distances between encrypted queries and encrypted data points. Due to the properties of Paillier encryption, these distances can be calculated without the host ever seeing the raw data.
- Secure Classification: The final classification, which involves summing the Gaussian influences and identifying the class with the highest total, is performed using Yao’s Garbled Circuits. This ensures that intermediate sums remain hidden from all parties.
Experimental Evaluation
The authors benchmarked their Gaussian KDE system against traditional k-NN using several datasets from the UCI Machine Learning Repository, including:
- Cancer 1 & 2: Datasets containing 9 and 30 features respectively for breast cancer diagnosis.
- Diabetes: Pima Indian diabetes patient data (8 features).
- MNIST: The standard benchmark for handwritten digit recognition (784 features per image).
The experiments focused on two primary metrics: accuracy and algorithmic agreement. The Gaussian KDE approach demonstrated remarkable fidelity to k-NN, achieving accuracy within 1% of the original algorithm on the Cancer and MNIST datasets. Furthermore, the two algorithms agreed on the final classification for over 98-99% of the test cases. Crucially, the authors provided formal security proofs showing that their KDE implementation is immune to the adaptive distance-learning attacks that compromise exact k-NN.
Conclusion and Future Directions
This work highlights a significant privacy challenge in collaborative machine learning and provides a robust solution through Gaussian KDE. While the system effectively neutralizes triangulation attacks, it introduces a computational cost that scales linearly ($O(N)$) with the number of data points. This overhead is a common bottleneck in private k-NN schemes. Future research will explore optimization strategies, such as parallel processing or secure approximation, to enhance scalability for large-scale "Big Data" applications without re-introducing the privacy risks associated with discrete neighborhood boundaries.
Summary updated