Homomorphic Querying

Performs nearest neighbor calculations directly on ciphertext. The vector database computes cosine similarity or Euclidean distance over encrypted embeddings, returning encrypted results that only the data owner can decrypt. This ensures the database operator never sees the query vector, the stored embeddings, or the final results in plaintext.

Leverages cryptographic primitives that preserve algebraic structure across encrypted operands:

• Partially Homomorphic Encryption (PHE): Supports only addition or multiplication, sufficient for dot-product similarity
• Somewhat Homomorphic Encryption (SHE): Supports limited depth of both operations
• Fully Homomorphic Encryption (FHE): Supports arbitrary computations on ciphertext, enabling complex ranking and filtering without decryption

The standard protocol proceeds in three stages:

1. Client-Side Encryption: The querying application encrypts the search vector using the data owner's public key
2. Blind Computation: The vector database executes the similarity algorithm homomorphically over the encrypted query and encrypted stored embeddings
3. Encrypted Result Return: The database returns encrypted identifiers or scores; only the holder of the private key can decrypt the final ranked list

Homomorphic operations impose significant computational overhead compared to plaintext vector search:

• Latency Increase: FHE-based similarity search can be 1000x to 1,000,000x slower than unencrypted equivalents
• Ciphertext Expansion: Encrypted vectors are orders of magnitude larger than their plaintext counterparts, increasing storage and bandwidth costs
• Hardware Acceleration: Emerging FPGA and ASIC designs target polynomial multiplication bottlenecks to reduce the performance gap

Homomorphic querying protects against specific adversarial scenarios:

• Honest-but-Curious Server: The database operator executes queries correctly but attempts to learn from observed data; encryption renders all observations meaningless
• Insider Threats: Database administrators with root access cannot inspect query content or stored embeddings
• Subpoena Resistance: A legal demand for server data yields only encrypted blobs with no intelligible information

Homomorphic querying complements rather than replaces traditional access controls:

• Pre-Encryption Authorization: Role-based or attribute-based checks determine whether a user may submit an encrypted query at all
• Encrypted Metadata Filtering: Boolean constraints on encrypted tags can be evaluated homomorphically alongside vector similarity
• Decryption-Key Gating: The private key required to decrypt results can be bound to a separate identity and access management system, adding a second authorization layer

A cryptographic scheme that allows arbitrary computations to be performed directly on ciphertexts, generating an encrypted result that, when decrypted, matches the output of operations performed on the plaintext. In the context of vector databases, FHE enables a client to send an encrypted query vector to an untrusted server, which computes the similarity scores (e.g., dot product) on encrypted data and returns an encrypted result without ever seeing the raw query or the matched data.

• Key Limitation: High computational overhead (often 1000x slower than plaintext operations).
• Use Case: Highly regulated industries where even the query vector cannot be exposed to the database operator.

A subfield of cryptography that distributes a computation across multiple parties where each party holds a private piece of the input data. No single party can learn anything about the other parties' inputs. For homomorphic querying, SMPC can be used to split a user's query and the database owner's index across non-colluding servers, which jointly compute the similarity search without any single server reconstructing the full query or results.

• Trust Model: Security holds as long as a threshold of parties remains honest.
• Advantage: Often more computationally efficient than pure FHE for specific functions like private set intersection.

A specialized encryption scheme where a secret key is associated with a specific function. A decryptor holding a key for function f can learn f(x) from an encryption of x, but learns nothing else about x. In vector search, a server can be given a key that allows it to compute the inner product of an encrypted query vector with stored database vectors, revealing only the similarity score and no other attributes of the vectors.

• Efficiency: Significantly faster than FHE for the specific task of linear operations on vectors.
• Constraint: The key is function-specific; a key for inner product cannot compute Euclidean distance.

A mathematical framework that injects calibrated statistical noise into embeddings or query results to provide a provable guarantee against the reconstruction of any single individual's data. When applied to homomorphic querying, differential privacy ensures that even if an attacker can observe the encrypted query outputs, they cannot infer with high confidence whether a specific record was included in the database.

• Privacy Budget (ε): A parameter that quantifies the privacy loss; lower epsilon means stronger privacy.
• Trade-off: Adding noise reduces the accuracy of similarity search results.

The process of applying a reversible or irreversible transformation to a vector to mask its true semantic meaning from unauthorized observers. Unlike encryption, obfuscation may rely on random rotations, dimensionality expansion, or adversarial perturbations to prevent an untrusted server from reconstructing the original text or image from the embedding while still allowing approximate similarity computations.

• Reversible Obfuscation: Uses a secret key to apply a random orthogonal transformation; authorized parties can invert it.
• Irreversible Obfuscation: Applies a one-way function or noise that permanently degrades fidelity but preserves relative distances.

An access control paradigm that defines permissions based on the conceptual meaning or category of data within a vector space, rather than static file paths. A Semantic ACL policy might state 'User A can query vectors semantically similar to public financial reports but not vectors similar to unreleased earnings data.' This is enforced by evaluating the query's intent or the result's content category before returning matches.

• Implementation: Often uses a classifier model to label query intent and result categories in real-time.
• Integration: Works as a post-filter on homomorphic query results to ensure decrypted data is only released for authorized semantic categories.