Encrypted k-Nearest Neighbours

Definition

k-nearest-neighbours search finds, for a query, the K entries of a dataset that lie closest to it under a fixed distance — without revealing the query or the data.

Given an encrypted query and an encrypted dataset of N entries, and a distance $d(\cdot, \cdot)$, the result is the set of K entries whose distance to the query is smallest:

i.e. the K entries with the smallest values of $d(q, \text{data}_i)$.

Mathematical Domain

kNN is defined over a domain equipped with a distance or similarity measure (for example Euclidean distance, squared distance, or cosine similarity). The result depends only on the ranking of the N distances, so the operation composes a distance computation with a selection of the K smallest.

Because the query and dataset are encrypted, both the distances and the selection must be computed homomorphically, and the selection must not branch on the secret values: the sequence of operations is fixed and independent of the data (data-oblivious), so the control flow reveals nothing.

The kernel does not fix the cryptographic scheme, the sizes N and K, the distance measure, the representation of points, or the correctness tolerance. These are defined by individual specifications.

Parameters Defined by Specifications

A specification narrows the general kNN operation into a concrete computational problem by defining, for example:

• the cryptographic scheme and element domain;
• the dataset size N and the number of neighbours K;
• the distance or similarity measure;
• the representation of the query, the dataset, and the returned neighbours;
• exact or approximate correctness and the accuracy tolerance;
• whether the computation must be data-oblivious.

Applications

kNN is a workhorse of retrieval and classification: recommendation, similarity search, nearest-centroid and instance-based classification, deduplication, and anomaly detection. Evaluating it over encrypted data enables private information retrieval and confidential inference, where a client's query and the server's dataset must both stay secret.