Exploring Privacy Preservation in Outsourced K-Nearest Neighbors with Multiple Data Owners

Frank Li, Richard Shin, Vern Paxson

TL;DR

This paper reveals a fundamental privacy vulnerability in outsourced k-Nearest Neighbors (k-NN) systems when multiple, mutually distrusting parties contribute data. To solve this, the authors propose a secure alternative using Gaussian Kernel Density Estimation (KDE) implemented via homomorphic encryption and garbled circuits, maintaining high accuracy while neutralizing "triangulation" attacks.

What Problem Does This Paper Address?

Machine learning often requires massive datasets, leading organizations to outsource computation to the cloud. However, when the data is sensitive (like medical records), privacy is paramount.

Previous research into "private k-NN" assumed a single trusted data owner. This paper tackles a more complex, realistic scenario: multiple data owners (e.g., different hospitals) who want to pool their data for better accuracy but don't trust each other or the cloud provider. The authors discover that in this multi-owner setting, the mathematical nature of k-NN itself creates a "side channel." An adversarial owner can perform distance-learning attacks by inserting "guess" data points and observing how the classification output changes, eventually triangulating the exact values of other owners' private data.

Methods

The authors argue that exact k-NN is fundamentally insecure in this setting because its "influence zone" (the distance to the $k$-th neighbor) changes based on the data. They propose replacing k-NN with Kernel Density Estimation (KDE) using a Gaussian kernel.

Because a Gaussian kernel has "infinite width," every data point in the system has some influence on every query. This removes the discrete "boundary" signals that attackers use to learn distances. To implement this securely, they use a multi-party system:

  1. Paillier Cryptosystem: A partially homomorphic encryption scheme used to compute squared distances between encrypted queries and encrypted data points without the cloud seeing the raw values.
  2. Yao’s Garbled Circuits: A cryptographic protocol used at the final step to determine which class has the highest "influence sum" without revealing the intermediate sums to any party.
  3. Two-Cloud Model: The system splits duties between a Data Host (stores encrypted data) and a Cryptographic Service Provider (manages keys), assuming they do not collude.

Datasets

The authors evaluated their approach on several real-world datasets from the UCI Machine Learning Repository and standard benchmarks:

  • Cancer 1 & 2: Breast cancer patient data with 9 and 30 features, respectively.
  • Diabetes: Data from Pima Indian diabetes patients (8 features).
  • MNIST: The classic handwritten digit recognition dataset (28x28 pixel images).

Key Insights and Ideas

  • The "Infinite Width" Defense: The most clever insight is that "blurring" the neighborhood is a security feature. By using a Gaussian kernel where every point always matters, you eliminate the "on/off" signal an attacker gets when a point enters or leaves the top-$k$ neighbors.
  • Mathematical Vulnerability: The paper proves that the privacy leak isn't a bug in the code, but a result of k-NN's mathematical properties. Any system providing exact k-NN results to a party that can also insert data is inherently vulnerable to triangulation.
  • KDE as a k-NN Proxy: While KDE and k-NN are different algorithms, they belong to the same family. The authors show that for most practical classification tasks, KDE is an excellent substitute that offers a path to provable privacy.

Key Results

  • Accuracy Parity: On most datasets (Cancer 1, Cancer 2, and MNIST), the Gaussian KDE approach achieved accuracy within 1% of traditional k-NN.
  • High Agreement: The two algorithms agreed on the classification result over 98-99% of the time for the cancer and MNIST datasets.
  • Security: The authors provide a formal proof that under their Gaussian KDE scheme, an adversary learns nothing from the adaptive distance-learning attacks that break k-NN.

Limitations and Future Work

The primary drawback is computational overhead. The current construction has a complexity of $O(N)$, meaning the time to process a query grows linearly with the number of data points. While this is standard for many private k-NN schemes, it makes the system slow for truly massive "Big Data" applications.

The authors suggest that future work should focus on optimizing performance, perhaps through parallelism or secure approximation techniques. However, they caution that any approximation must be carefully designed to avoid re-introducing the very privacy leaks they solved.

Summary updated

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.
BibTeX
@inproceedings{li2015exploring,
  author = {Frank Li and Richard Shin and Vern Paxson},
  title = {{Exploring Privacy Preservation in Outsourced K-Nearest Neighbors with Multiple Data Owners}},
  booktitle = {CCSW},
  year = {2015},
  url = {https://openreview.net/forum?id=kj_9yFzkOiy},
}

Loading related content...

Figure