Encrypted Vector Search

Homomorphic encryption is a cryptographic scheme that allows computations to be performed directly on encrypted data. The encrypted result, when decrypted, matches the result of the same operations performed on the plaintext. This is the core mathematical foundation enabling encrypted vector search, as it allows distance calculations (like cosine similarity) to be computed in ciphertext space without decrypting the vectors.

• Fully Homomorphic Encryption (FHE): Supports arbitrary computations on ciphertext but is computationally intensive.
• Partially Homomorphic Encryption: Supports only specific operations (e.g., addition or multiplication) but is more efficient. Encrypted search often uses schemes optimized for the specific distance metric required.

Secure multi-party computation (MPC) is a cryptographic protocol that enables multiple parties to jointly compute a function over their private inputs while keeping those inputs concealed. In the context of search, MPC can be used to perform a similarity search where the query vector is held by one party and the database by another, without either revealing their private data.

• Contrast with Homomorphic Encryption: MPC involves interactive protocols between parties, whereas homomorphic encryption allows computation on data encrypted for a single key holder.
• Use Case: A hospital could search a pharmaceutical company's private molecular compound database without revealing its target protein or the company revealing its proprietary compound structures.

A trusted execution environment (TEE) is a secure, isolated area within a main processor, protected by hardware. Code and data inside a TEE are encrypted in memory and inaccessible to the host operating system, hypervisor, or other tenants. This provides an alternative architectural foundation for private search.

• How it Enables Search: Sensitive vectors and queries can be loaded into the TEE's encrypted memory enclave. The similarity search computation occurs inside this protected enclave, with results released only to the authorized client.
• Examples: Intel SGX, AMD SEV, and AWS Nitro Enclaves. This approach often offers lower computational overhead than pure cryptographic methods like FHE but requires trust in the hardware vendor and correct implementation.

Differential privacy is a rigorous mathematical framework for quantifying and bounding the privacy loss incurred when an individual's data is used in an analysis. It works by injecting carefully calibrated noise into query results or model outputs.

• Relation to Encrypted Search: While encrypted search protects data at rest and during computation, differential privacy protects the outputs of a system. They are complementary: you could use encrypted search to retrieve relevant records and then apply differential privacy to any aggregate statistics generated from those results before releasing them.
• Privacy Budget (ε): A key parameter that controls the trade-off between accuracy and privacy; a smaller epsilon provides stronger privacy guarantees.

Federated learning is a decentralized machine learning paradigm where a global model is trained across multiple edge devices or isolated data silos. Each client trains on its local data and shares only model updates (e.g., gradients), not the raw data itself.

• Retrieval Analogy: Conceptually similar to keeping data at its source. A federated retrieval system might involve sending an encrypted query to multiple private databases. Each database performs a local, private search and returns only an encrypted set of relevant document IDs or aggregated embeddings, which are then combined centrally.
• Key Challenge: Designing federated algorithms for retrieval that are communication-efficient and preserve privacy during the aggregation phase, often using secure aggregation protocols.

Searchable symmetric encryption (SSE) is a cryptographic primitive designed specifically for keyword search over encrypted data stored on an untrusted server. The client encrypts documents and builds an encrypted index. Later, it can generate a search token for a specific keyword, which the server uses to retrieve matching documents without learning the keyword or document contents.

• Contrast with Encrypted Vector Search: SSE is typically designed for exact or boolean keyword matching. Encrypted vector search is designed for approximate similarity search over dense, high-dimensional embeddings.
• Evolution: Modern encrypted search systems are beginning to hybridize techniques, using SSE for efficient filtering and encrypted vector search for semantic ranking.