Private Information Retrieval

The fundamental guarantee of any PIR protocol. The database server learns nothing about which specific item (e.g., which database index or record) the client is retrieving. This is stronger than simply encrypting the query, as the server should gain zero information about the query's target, even from the access pattern. This is formally defined as computational or information-theoretic security against a curious server.

A PIR protocol must protect the access pattern to the data. The server should not be able to distinguish between a request for item i and a request for item j based on the data accessed during the protocol execution. This often requires the client's request to touch multiple or all database entries in a way that is independent of the desired item, a technique central to many PIR constructions.

PIR protocols are categorized by their trust model:

• Information-Theoretic PIR (IT-PIR): Requires multiple non-colluding database replicas. Privacy is guaranteed unconditionally, without computational assumptions, but relies on the strong assumption that servers do not collude.
• Computational PIR (CPIR): Requires only a single server. Privacy relies on cryptographic hardness assumptions (e.g., the learning with errors problem). This is more practical for real-world deployment but is computationally more expensive for the server.

A key efficiency goal. In a trivial solution, the client downloads the entire database, achieving perfect privacy but with communication cost O(n) (where n is the database size). Non-trivial PIR protocols aim for sublinear communication—where the total bits exchanged are less than n. Modern single-server CPIR schemes achieve polylogarithmic or even constant communication overhead, though with significant server-side computation.

The primary trade-off for achieving query privacy on a single server. In CPIR, the server must perform a homomorphic computation over the entire (or large portions of the) encrypted database to generate a response. This results in O(n) server computation time, which is the major bottleneck for scaling PIR to very large databases. Optimizations focus on reducing the constant factors and leveraging hardware acceleration.

A PIR protocol that provides privacy but not integrity is vulnerable to a malicious server returning incorrect data. Verifiable PIR (VPIR) extensions allow the client to cryptographically verify that the retrieved item is correct and consistent with the public database commitment, without breaking the privacy guarantee. This is crucial for applications where data correctness is as important as query secrecy.

A form of encryption that allows computations to be performed directly on ciphertext. The encrypted result, when decrypted, matches the result of operations performed on the plaintext. This enables secure data processing on untrusted servers without ever decrypting the data.

• Key Use Case: Performing encrypted vector search for semantic similarity over sensitive embeddings.
• Trade-off: Computationally intensive, often making it impractical for real-time, high-throughput RAG applications without significant optimization.

A cryptographic protocol that enables multiple parties to jointly compute a function over their private inputs while keeping those inputs concealed. Only the final output of the computation is revealed.

• Key Use Case: Private Set Intersection (PSI), where two entities can find common records (e.g., customers) without exposing their full datasets.
• Mechanism: Often implemented using garbled circuits or secret sharing schemes to distribute the computation.

A secure, isolated area of a main processor (an enclave) that provides hardware-level protection for code and data. It ensures confidentiality and integrity even from privileged system software like the OS.

• Examples: Intel SGX and AWS Nitro Enclaves.
• Key Use Case: Running a retriever model or performing similarity search on plaintext data within a protected enclave, isolating it from the cloud provider and other tenants (Confidential Computing).

A cryptographic primitive that allows a client to store encrypted data on an untrusted server and later perform keyword searches over it. The client generates encrypted search tokens that reveal nothing about the query or data beyond the results.

• Contrast with PIR: SSE is optimized for keyword-based Boolean search ("documents containing 'X'"), while PIR is for index-based retrieval ("give me item #123").
• Efficiency: More practical for large-scale document databases than general PIR, but less flexible for complex queries.

A decentralized machine learning paradigm where a global model is trained collaboratively across multiple client devices or data silos. Only model updates (e.g., gradients) are shared, not the raw training data.

• Key Use Case: Training a domain-adaptive retriever model across multiple hospitals or banks without centralizing sensitive patient or financial records.
• Enhancement: Often combined with secure aggregation to prevent the server from inspecting any individual client's update.

A rigorous mathematical framework for quantifying and limiting the privacy loss when an individual's data is used in an analysis. It guarantees that the output of an algorithm does not reveal whether any specific individual's data was in the input dataset.

• Core Mechanism: Adds carefully calibrated noise (e.g., via the Laplace Mechanism) to query results or model outputs.
• Key Concept: Privacy Budget (ε): A finite resource that is consumed with each query; once exhausted, no further privacy-preserving queries can be made.
• Application: Releasing aggregate statistics from a private knowledge base or adding noise to retrieved context before passing it to an LLM in a RAG pipeline.