Private Information Retrieval (PIR)

In its strongest form, PIR guarantees that the server learns absolutely nothing about the index being queried. This is not computational obscurity; even an adversary with unbounded computing power cannot distinguish which record was accessed. This is achieved by having the client encode the query such that it is statistically independent of the desired index. The server's view of the query is uniformly random, providing a mathematical guarantee rather than a complexity-theoretic assumption.

Computational PIR relaxes the security model to rely on hard mathematical problems, such as the Quadratic Residuosity Problem or the Phi-Hiding Assumption. While an unbounded adversary could theoretically break the scheme, cPIR is dramatically more efficient than its information-theoretic counterpart. Modern lattice-based cPIR protocols, such as SealPIR and FastPIR, reduce communication complexity to sublinear levels, making single-server deployments practical for encrypted vector database queries.

Information-theoretic PIR typically requires k non-colluding servers, each holding an identical copy of the database. The client sends distinct, randomized queries to each server. Individually, each query reveals nothing. The client reconstructs the record by combining the responses. The critical security assumption is that the servers do not collude to share their query logs. This architecture trades operational complexity for unconditional privacy guarantees.

A fundamental limitation of single-server PIR is the linear server-side computation requirement. The server must process every record in the database to prevent access pattern leakage; otherwise, skipping a record would reveal it was not the target. Optimizations like batch PIR and stateful PIR amortize this cost across multiple queries. Recent breakthroughs using homomorphic encryption allow the server to perform this linear scan on compressed ciphertexts, reducing the computational overhead by a constant factor.

Standard PIR protects only the client's query privacy. Symmetric PIR adds data privacy, ensuring the client learns nothing beyond the single record they requested. This prevents a malicious client from extracting the entire database through repeated queries. SPIR is essential for commercial encrypted vector databases where the database owner must protect their intellectual property while serving private queries to authorized clients.

Traditional PIR retrieves records by numeric index, which is impractical for semantic search. Keyword PIR extends the protocol to retrieve records based on a keyword or predicate without revealing the search term. The server holds a key-value store; the client privately retrieves the value associated with a specific key. This is the foundational primitive for building encrypted vector search where the query vector itself remains hidden from the database server.