Secure Distance and Similarity Computation

101 concepts84 papers

In modern data systems, we frequently need to know how "close" two pieces of information are. We compute spatial proximity to assign ridesharing tasks, evaluate biometric similarity to authenticate users, calculate document relevance to return search results, and measure clinical alignment to discover similar patient profiles.

Traditionally, computing distance metrics—such as Euclidean distance, Hamming distance, or cosine similarity—requires access to raw feature vectors. However, when these vectors represent precise physical locations, biometric templates, or medical histories, exposing them creates severe privacy risks.

Secure similarity computation solves this dilemma. It allows mutually distrusting parties, or a third-party cloud server, to determine the geometric relationship between data points without ever decrypting or exposing the underlying data itself. The field achieves this through three core paradigms: algebraic homomorphism, geometric invariance, and secure distributed secret sharing.

The Algebra of Encrypted Distances

How can a server compute the distance between two vectors if it cannot see the coordinates of either? The answer lies in additively homomorphic encryption (HE).

An additively homomorphic cryptosystem (such as the Paillier cryptosystem) allows a party holding only the ciphertexts of $x$ and $y$ to compute the ciphertext of their sum, $[x + y] = [x] \cdot [y]$, or the product of a ciphertext and a plaintext scalar, $[c \cdot x] = [x]^c$.

To see how this enables distance computation, consider the standard squared Euclidean distance formula for two-dimensional coordinates:

$$D^2 = (x_1 - y_1)^2 + (x_2 - y_2)^2 = (x_1^2 + x_2^2) + (y_1^2 + y_2^2) - 2(x_1y_1 + x_2y_2)$$

If a user encrypts their coordinates, the server can exploit this algebraic expansion. By combining the user's encrypted coordinates with its own plaintext data, the server can homomorphically compute the cross-terms (like $-2x_1y_1$) and sum them with the squared terms.

Bozhong Liu et al. demonstrate the practicality of this approach in Protecting Location Privacy in Spatial Crowdsourcing using Encrypted Data, where a dual-server framework assigns crowdsourced tasks based entirely on encrypted spatial coordinates. Similarly, Jingwei Li et al. apply homomorphic distance calculations to mobile social networks in MobiShare+: Security Improved System for Location Sharing in Mobile Online Social Networks, allowing proximity detection without exposing raw user trajectories to the service provider.

This algebraic mapping extends naturally to binary spaces. When comparing strings or categorical profiles, systems often rely on the Hamming distance—the number of positions at which two bit-vectors differ. Because the Hamming distance can be decomposed into linear bitwise operations, additively homomorphic encryption can compute it directly on encrypted bit-vectors.

Martin Beck and Martín Beck leverage this property in Approximate Two-Party Privacy-Preserving String Matching with Linear Complexity to securely match genetic sequences. In a federated medical context, Jimeng Sun et al. apply homomorphic encryption to binary patient hashes in Privacy-Preserving Patient Similarity Learning in a Federated Environment: Development and Analysis, allowing independent hospitals to identify clinically similar patients across institutions without leaking identifiable health records.

The primary advantage of homomorphic encryption is mathematical exactness. As Süleyman Özdel et al. show in Privacy-preserving Scanpath Comparison for Pervasive Eye Tracking, executing complex sequence alignments within an encrypted domain yields identical results to plaintext execution, avoiding the accuracy trade-offs inherent in noise-based privacy techniques like differential privacy.

Geometric Invariance via Matrix Transformations

While homomorphic encryption provides strong security guarantees, its computational overhead can be prohibitive for high-dimensional data or real-time applications. An alternative approach leverages linear algebra to mask data through geometric transformations that preserve distances.

Consider an orthogonal matrix $Q$, which satisfies the property $Q^T Q = I$. If we multiply two vectors $x$ and $y$ by $Q$, their inner product remains completely unchanged:

$$(Qx) \cdot (Qy) = x^T Q^T Q y = x^T I y = x \cdot y$$

Because Euclidean distance and cosine similarity are derived directly from inner products, transforming an entire dataset by an orthogonal matrix hides the absolute coordinates of the data points while perfectly preserving their relative geometric relationships.

Xuexian Hu et al. utilize this property in An Efficient Biometric Identification in Cloud Computing With Enhanced Privacy Security, mapping high-dimensional biometric templates into an encrypted domain where a cloud server can perform rapid identification using standard geometric calculations on the ciphertexts.

Plaintext Space                     Encrypted Domain
  Vector x, y                         Vector Qx, Qy
       │                                    │
       ▼                                    ▼
  Distance D(x,y)  ═════[Identical]═════► Distance D(Qx,Qy)

For secure cloud search, researchers frequently combine random vector splitting with secret matrix multiplication. In this setup, document index vectors and incoming query vectors are augmented with random noise, split into distinct components, and multiplied by secret invertible matrices. The cloud server can then compute the dot product of the transformed vectors to determine relevance scores, yet it cannot invert the transformation to recover the original keywords or weights.

Xingming Sun et al. demonstrate this mechanism in Dynamic Multi-keyword Top-k Ranked Search over Encrypted Cloud Data and expand upon it in Privacy-preserving Multi-keyword Ranked Search over Encrypted Cloud Data Supporting Dynamic Update. Similarly, Guowen Xu et al. employ encrypted vector dot products in Achieving Fine-grained Multi-keyword Ranked Search over Encrypted Cloud Data to support complex logical queries while ranking results by user preferences.

By mapping non-linear distance metrics into linear inner products, these transformations allow servers to evaluate complex relationships efficiently. As Kai Zhou et al. show in PassBio: Privacy-Preserving User-Centric Biometric Authentication, leveraging matrix trace invariance allows high-dimensional randomized data to be reduced to a single meaningful scalar for threshold comparison, keeping the raw biometric templates secure.

Secret Sharing and Distributed Proximity

When data cannot be trusted to a single cloud provider, systems turn to Secure Multi-Party Computation (MPC) and secret sharing. Instead of encrypting a vector under a cryptographic key, the vector is broken into random numerical "shares" and distributed across multiple independent, non-colluding servers.

For instance, a value $x$ can be split into $x_a$ and $x_b$ such that $x = x_a + x_b$. Separately, $x_a$ and $x_b$ look like uniform random noise, revealing zero information about $x$. However, if Server A holds $x_a$ and Server B holds $x_b$, they can collaboratively compute linear operations by operating directly on their individual shares.

This technique is highly effective for distributed retrieval and federated learning. Guy Zyskind et al. apply this to Large Language Models in Don't forget private retrieval: distributed private similarity search for large language models, secret-sharing both query vectors and document databases across servers to execute secure dot-product similarity searches.

In federated clustering, Songze Li et al. demonstrate in Secure Federated Clustering that exact Euclidean distances between private data points and cluster centers can be computed entirely within a coded domain, providing information-theoretic privacy guarantees that prevent the central server or colluding clients from reconstructing the data.

Secret sharing also enables privacy-preserving anomaly and threat detection. Mohammad Ali Maddah-Ali introduces a secure aggregation framework in ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitment that leverages ramp secret sharing. By embedding data points into a sharing polynomial, the system computes pairwise distances between local model updates, allowing it to identify and filter out malicious Byzantine updates without exposing the honest participants' underlying gradients.

The Threshold Problem: Hiding the Distance Itself

Computing a distance securely is only half the battle. If a server calculates the exact distance between a query and a target, it can still infer sensitive information. For example, by submitting multiple queries and observing the exact output distances, an attacker can use triangulation to map out the exact coordinates of the target data.

To prevent this, modern protocols incorporate a final "threshold check" that converts a continuous distance metric into a binary match/mismatch decision, ensuring the exact distance value is never revealed.

[Encrypted Vectors] ──► [Secure Distance Math] ──► [Garbled Circuit / Masking] ──► Binary Output (0 or 1)

This is typically achieved by combining homomorphic distance calculations with garbled circuits or random masking. Kasra EdalatNejad et al. implement this hybrid approach in Janus: Safe Biometric Deduplication for Humanitarian Aid Distribution. The system uses somewhat homomorphic encryption to compute the distance between a new biometric sample and an encrypted database, then passes the result into a garbled circuit that evaluates whether the distance falls below a specific threshold. The requester receives only a single bit indicating whether the individual has already registered, preventing the leakage of similarity scores.

Similarly, Chang Xu et al. employ a two-server architecture in PPLS: a privacy-preserving location-sharing scheme in mobile online social networks. One server computes an encrypted matrix of the differences between the actual distance and a user's customized proximity threshold, while the second server evaluates the matrix to output a binary proximity result without either server learning the exact distance or location.

When performing more complex operations like $k$-means clustering or $k$-nearest neighbor classification, the system must identify the minimum distance among a set of candidates without revealing the distances themselves. Yifeng Zheng addresses this in SecSkyline: Fast Privacy-Preserving Skyline Queries over Encrypted Cloud Databases by combining bit-decomposition with a parallel prefix adder to identify the most significant bit of the differences between secret-shared values.

Ultimately, as originally framed by Jaideep Vaidya and Chris Clifton in Privacy-preserving k-means clustering over vertically partitioned data, using secure circuit evaluation to isolate the index of the minimum value ensures that iterative algorithms can successfully group data while keeping the underlying distance metrics completely masked.

Key Foundational Work

Client-side web mining for community formation in peer-to-peer environments (2006) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_privacy_preserving_similarity_computatio_ee36db29,
  title = {privacy-preserving similarity computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/privacy-preserving-similarity-computation/rdr_ee36db2961b54cc6acead8c7ae43e51f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_privacy_preserving_similarity_computatio_ee36db29_v1,
  title = {privacy-preserving similarity computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/privacy-preserving-similarity-computation/rdr_ee36db2961b54cc6acead8c7ae43e51f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake