Privacy Preserving Similarity Estimation with Locality Sensitive Hashing

18 concepts13 papers1 proposal

In modern distributed computing, we frequently encounter a fundamental tension: two or more parties need to know how similar their data is, but privacy regulations, competitive boundaries, or security risks prevent them from sharing the data itself.

For instance, banks might want to discover if they share identical suspicious transaction patterns without exposing their clients' raw financial histories. Medical institutions might want to cluster patient profiles across hospitals to improve diagnostic models without leaking protected health information.

The naive solution relies on heavy cryptographic primitives like Fully Homomorphic Encryption (FHE) or Secure Multi-Party Computation (SMPC). While mathematically secure, these methods introduce massive computational and communication overheads, often rendering them impractical for large-scale datasets.

Instead, a powerful alternative direction relies on a geometric trick: Locality-Sensitive Hashing (LSH) and randomized binary embeddings. By mapping high-dimensional features or discrete sets into compact, irreversible bitstrings, systems can compute distances and alignments using simple bitwise operations while mathematically destroying the ability to reconstruct the original data.


The Geometry of Distance-Preserving Hashes

To understand why this approach works, imagine two high-dimensional vectors representing sensitive features—such as voiceprints or deep neural network embeddings. If we want to measure their similarity without revealing their exact coordinates, we can exploit the properties of random geometric projections.

If we draw a random hyperplane through the origin of a high-dimensional space, two vectors that are close to each other (i.e., have a small angular distance) are highly likely to reside on the same side of the hyperplane. Conversely, vectors that are far apart are much more likely to be separated by the plane.

By projecting a sensitive vector onto a series of random directions and recording only the sign of the result (whether it falls on the positive or negative side of the hyperplane), we transform a continuous, high-dimensional vector into a sequence of bits.

High-Dimensional Space                  Binary Hypercube
   [ Sensitive Vector A ]  ---\             [ 10110011 ]
                               \--+---> 
   [ Sensitive Vector B ]  ---/             [ 10110111 ]
                                      (Hamming Distance = 1)

This process yields two critical properties:

  1. Distance Preservation: The Hamming distance (the number of differing bits) between the resulting bitstrings directly approximates the geometric distance between the original vectors.
  2. Irreversibility: Because an infinite number of vectors can map to the exact same binary signature, the transformation is a many-to-one mapping. It is mathematically impossible to reconstruct the exact raw coordinates from the hash alone.

This mechanism forms the backbone of several privacy-preserving architectures. For example, José Portelo et al. apply this concept to speaker verification in Secure binary embeddings of front-end factor analysis for privacy preserving speaker verification, converting sensitive voice characteristics into obfuscated bit strings so that authentication can happen safely on an untrusted server.

Leveraging the Concentration of Measure

Recent advances have refined this geometric intuition by introducing structured random rotations. As highlighted by Jianyang Gao et al. in High-Dimensional Vector Quantization: General Framework, Recent Advances, and Future Directions, applying a random orthogonal rotation to high-dimensional vectors before quantization maps them evenly onto the vertices of a structured hypercube.

This technique leverages the "concentration of measure" phenomenon in high dimensions, ensuring that the relative distances between vectors are preserved with minimal variance. Wenhao Li et al. utilize this exact mechanism in RaBitQCache: Rotated Binary Quantization for KVCache in Long Context LLM Inference to compress high-dimensional key-value vectors into 1-bit representations, enabling highly accurate, fast similarity estimation via hardware-friendly bitwise operations.


Set Similarity and MinHash Signatures

When dealing with discrete data—such as logs, transaction sets, or text documents—similarity is typically measured using the Jaccard index:

$$\text{Jaccard}(A, B) = \frac{|A \cap B|}{|A \cup B|}$$

Computing this directly across distributed databases normally requires both parties to reveal their entire sets. To circumvent this, researchers turn to MinHash, a variant of LSH designed for sets.

MinHashing works by applying a family of random permutations to the universe of possible items. The minimum hash value under each permutation forms a compact "signature" of the dataset. The probability that two sets share the same minimum hash value under a random permutation is exactly equal to their Jaccard similarity.

Party A Set ----> [ Random Permutations ] ----> MinHash Signature A (e.g., [4, 12, 89])
                                                       |
                                            (Compare Signatures Only)
                                                       |
Party B Set ----> [ Random Permutations ] ----> MinHash Signature B (e.g., [4, 55, 89])

By exchanging only these compact signatures, parties can estimate their shared overlap without revealing the unshared items. To make this process cryptographically secure, Carlo Blundo et al. introduced the EsPRESSo framework in EsPRESSo: Efficient Privacy-Preserving Evaluation of Sample Set Similarity. Their approach combines MinHash signatures with Private Set Intersection Cardinality (PSI-CA) protocols. Because the cryptographic operations are restricted to the small, fixed-size MinHash signatures rather than the massive raw datasets, the framework achieves orders-of-magnitude speedups over traditional secure computation.

A similar intuition is deployed by Wenjie Qu in Towards Collaborative Anti-Money Laundering Among Financial Institutions, where banks generate compact LSH signatures of local transaction graphs to collaboratively detect multi-bank laundering patterns without exposing individual account details.


Unlocking Decentralized and Federated Learning

The ability to compute similarity safely and cheaply serves as a foundational building block for decentralized machine learning, particularly when data distributions are non-IID (not independent and identically distributed) or poorly labeled.

Cross-Client Label Propagation

In federated semi-supervised learning, clients often hold unlabeled data, while only a few clients possess labeled instances. To propagate labels across different clients without exposing the underlying features, Jonathan Scott et al. proposed frameworks in FedProp: Cross-client Label Propagation for Federated Semi-supervised Learning and Cross-client Label Propagation for Transductive and Semi-Supervised Federated Learning.

By using shared random projections, clients transform high-dimensional feature vectors into compact binary strings. These strings are safe to share because they protect raw data from exposure, yet they retain enough geometric structure to build a global similarity graph, allowing labels to flow accurately across decentralized nodes.

Device Grouping and Correlation Mapping

In a similar vein, Tian Liu et al. developed a device-grouping framework in Towards Fast and Accurate Federated Learning with non-IID Data for Cloud-Based IoT Applications. Here, a central server clusters IoT devices based on the similarity of their local data distributions. By hashing local feature maps into compact LSH indices, the server can group similar devices to accelerate model convergence while defending against model inversion attacks.

This strategy of using hashes as a secure proxy for data relationships shows up across several other distributed architectures:


Scaling Privacy Guarantees

Beyond federated learning, distance-preserving hashes provide massive algorithmic speedups for classical data privacy problems. For example, achieving $k$-anonymity—ensuring every record in a public dataset is indistinguishable from at least $k-1$ other records—traditionally requires quadratic-time nearest-neighbor searches, which fail on modern, large-scale datasets.

By applying LSH to quickly bin similar records together, Kevin Aydin et al. demonstrate in Nearly-Linear Time and Massively Parallel Algorithms for $k$-anonymity that the computational complexity of data suppression can be reduced to nearly-linear time, allowing $k$-anonymity to scale to millions of rows.

When absolute cryptographic security is required alongside scalability, LSH can be paired directly with lightweight cryptographic protocols. As Ruidi Wei demonstrates in Cryptographically Secure Private Record Linkage Using Locality-Sensitive Hashing, embedding LSH within a secure private record linkage workflow allows organizations to find matching entities across databases with both cryptographic rigor and the high-speed throughput of hash-based filtering.

Conclusion

The core power of locality-sensitive hashing in privacy contexts lies in its elegant simplification of the problem space. Instead of hiding data behind complex mathematical puzzles that require heavy computation to solve, LSH projects data into a lower-dimensional, lossy binary space. Because this projection preserves the underlying geometry while discarding the exact coordinate details, it allows distributed systems to collaborate, align, and learn based on proximity alone—proving that we don't always need to see data to understand how it connects.

Key Foundational Work

EsPRESSo: Efficient Privacy-Preserving Evaluation of Sample Set Similarity (2011) — contributed 1 concept elements to this direction.
Secure binary embeddings of front-end factor analysis for privacy preserving speaker verification (2013) — contributed 1 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_set_similarity_estima_17d4d0c9,
  title = {privacy-preserving set similarity estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/privacy-preserving-set-similarity-estimation/rdr_17d4d0c902374aa5929e69434df40593},
  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_set_similarity_estima_17d4d0c9_v1,
  title = {privacy-preserving set similarity estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/privacy-preserving-set-similarity-estimation/rdr_17d4d0c902374aa5929e69434df40593/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake