Secure Similarity Computation for Encrypted Vector Search

This direction is split into other directions: privacy-preserving similarity computation. Its last version stays readable and citable here.

Version 1 of 1144 papers187 conceptsfrozen 2026-10-04

In modern data systems, we often need to find things that are "similar" to a query—finding the most relevant document for an LLM, identifying a face in a crowd, or detecting malicious updates in federated learning. Traditionally, this requires a server to see both the query and the database in plaintext to calculate distances.

However, a growing body of research enables Secure Similarity Computation: the ability to calculate distance metrics (like Euclidean distance or Cosine similarity) between vectors while they remain encrypted or secret-shared. This allows a server to rank results or identify matches without ever "seeing" the underlying sensitive data.

The Core Intuition: Computing Differences in the Dark

The fundamental challenge is calculating a distance metric, such as the squared Euclidean distance $\|x - y\|^2$, without knowing $x$ or $y$. Most privacy-preserving protocols solve this by leveraging the algebraic properties of specific encryption schemes.

As Rong-Hua Li and Chuankun Wu demonstrate in their work on Co-operative Private Equality Test (CPET), additive homomorphic encryption (HE) allows a third party to subtract two encrypted values. If the result is zero, the inputs were identical. To prevent the third party from learning the actual difference when they don't match, the result is multiplied by a secret random factor.

For more complex similarity metrics like Cosine similarity, which powers most modern vector databases, researchers like Hyunmin Choi and Simon S. Woo in Blind-Match use Fully Homomorphic Encryption (FHE) to perform dot products directly on encrypted real-valued vectors. By partitioning these calculations, they achieve accuracy identical to plaintext models while maintaining sub-second speeds.

Scaling to Large Databases

Comparing a query against every single record in a database (1:N matching) is computationally expensive when every operation involves heavy cryptography. To make this practical, researchers use two main strategies:

  1. Encrypted Indexing: Instead of a flat search, systems like EMRS by Dongxiao Liu and Xuemin Shen use secure k-nearest neighbor (kNN) techniques combined with "blind storage" or tree-based indices. This allows the server to navigate a search tree (like a KD-tree) by performing only a few encrypted comparisons at each node.
  2. Sketching and Bloom Filters: For high-speed approximate matching, data can be transformed into compact "sketches." Martin Beck and Dagmar Schönfeld show in Inference Control for Privacy-Preserving Genome Matching how genomic data can be represented as Bloom filters. Homomorphic encryption is then used to calculate the Hamming distance (the number of differing bits) between these encrypted filters.

Hybrid Protocols for Binary Outcomes

In many applications, such as biometric deduplication or financial fraud detection, the goal isn't to get a list of scores, but a simple "Yes/No" (is this person already registered?).

Revealing the raw similarity score can actually be a security risk, as an attacker could use multiple queries to "hill-climb" and reconstruct the original data. To prevent this, Kasra EdalatNejad and Wouter Lueks in Janus propose a hybrid approach:

  • Phase 1: Use Homomorphic Encryption to compute the distance between a query and the database.
  • Phase 2: Feed that encrypted distance into a Garbled Circuit—a form of secure multi-party computation (MPC)—that performs a threshold check.

The circuit only outputs a single bit (Match/No-Match), ensuring that the server learns nothing about how close the "near-misses" were.

Applications in Modern AI and Distributed Learning

This research direction is becoming critical for the deployment of Large Language Models (LLMs). In Retrieval-Augmented Generation (RAG), a user's query is converted into a vector and compared against a document database. Guy Zyskind and Alex Pentland argue in Don't forget private retrieval that MPC is essential to prevent cloud providers from seeing the user's search intent. Similarly, Lan Zhang and Yihang Cheng demonstrate in RemoteRAG that combining differential privacy with HE can achieve 100% retrieval accuracy without exposing semantic content.

Beyond search, these metrics are used to secure the training process itself. In Federated Learning, malicious participants might try to "poison" a model. Basak Guler and Amir Salman Avestimehr developed BREA, which calculates pairwise distances between encrypted model updates. By identifying updates that are "too far" from the consensus, the system can reject malicious contributions without ever seeing the private data used to train them.

Papers in this version

Showing 60 of 144 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_secure_similarity_computation_for_encryp_5b7a1d32,
  title = {Secure Similarity Computation for Encrypted Vector Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/secure-similarity-computation-for-encrypted-vector-search/rdr_5b7a1d32ef2246188b343e464edd9e30},
  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_secure_similarity_computation_for_encryp_5b7a1d32_v1,
  title = {Secure Similarity Computation for Encrypted Vector Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/secure-similarity-computation-for-encrypted-vector-search/rdr_5b7a1d32ef2246188b343e464edd9e30/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}