Private Information Retrieval (PIR)

Query privacy is the foundational guarantee of any PIR protocol. It ensures that a database server, even if it deviates from the protocol (behaves maliciously), cannot learn which specific item a client is retrieving from the database. The server sees only an obfuscated query that is statistically indistinguishable from a query for any other item. This is a stronger guarantee than simply encrypting the query, as it must hold against computationally unbounded servers in information-theoretic PIR or against efficient servers in computational PIR.

Database privacy (or data privacy) is the complementary property that ensures the client learns nothing more than the single item it requested. The client should not gain any information about the contents of other database records beyond what can be inferred from the retrieved item itself. In standard PIR, this is typically assumed, but it becomes a critical explicit requirement in Symmetric PIR (SPIR) protocols, which enforce both query and database privacy simultaneously.

Communication complexity measures the total amount of data exchanged between the client and server during a PIR protocol. A naive solution—downloading the entire database—has linear complexity O(n) for an n-item database, which is prohibitively expensive. Efficient PIR protocols aim for sublinear communication (e.g., O(√n) or even polylogarithmic). This is the primary practical challenge, as cryptographic techniques for privacy often increase bandwidth overhead. Single-server PIR schemes typically have higher communication cost than multi-server PIR schemes.

Computational complexity refers to the processing overhead required by the client and server. For the client, this should be lightweight (sublinear in n). The server's computation is often the major bottleneck, especially in homomorphic encryption-based PIR, where the server must perform computations on encrypted data. Recent advances using fully homomorphic encryption (FHE) or partially homomorphic encryption seek to optimize this. Vectorized batch processing on the server side is a common technique to amortize costs across multiple queries.

This property defines the system's trust model. Multi-server PIR (originated by Chor, Goldreich, Kushilevitz, and Sudan) assumes multiple non-colluding database replicas. By sending correlated queries to each, the client can combine responses to retrieve the desired item privately. This setting allows for information-theoretic security with low communication overhead. Single-server PIR relies on computational hardness assumptions (e.g., the learning with errors problem). It is more practical for real-world deployment but incurs higher cryptographic overhead. The choice fundamentally impacts protocol design and guarantees.

Retrieval correctness is the requirement that the client always receives the accurate, unaltered data item it requested, provided both parties follow the protocol. This must hold even if the database is publicly known. The protocol must guarantee that the server's response, when processed by the client's decoding algorithm, yields the exact bit-string stored at the target index. This property distinguishes PIR from weaker notions like oblivious transfer, where the server may be unaware of the database contents. Correctness is typically required with high probability or certainty.

PIR's foundational use case is enabling confidential lookups in sensitive databases. A client can retrieve a record—such as a medical diagnosis, financial transaction, or legal document—while keeping the query index secret from the server operator. This is critical for:

• Healthcare: Patients querying genomic databases or electronic health records.
• Finance: Auditors verifying transactions without revealing the specific accounts under scrutiny.
• Legal Research: Lawyers searching case law without exposing their client's strategic interests.

The server learns only that a query occurred, not what was queried, providing strong query privacy.

PIR protocols are used to build private DNS resolvers that prevent network observers (including the resolver itself) from learning which websites a user is visiting. Standard DNS queries leak the requested domain name in plaintext. A PIR-based system, such as the conceptual PIR-DNS, allows a client to fetch the IP address for a domain from a massive database of all domains without revealing the target. This application directly combats surveillance and censorship by hiding browsing patterns at the fundamental level of domain name resolution.

PIR enables private streaming from content libraries. A user can watch a movie or read an article from a service's catalog without the provider learning which specific title was accessed. This is achieved by treating the entire media library as a database where each item is an encrypted chunk of content. The client uses PIR to fetch only the chunks corresponding to their chosen title. This protects consumer privacy from detailed behavioral profiling and is particularly relevant for sensitive content (e.g., political news, health information). It shifts the trust model from the service provider to the cryptographic protocol.

In blockchain systems, PIR allows nodes or light clients to privately read state (e.g., account balances, smart contract storage) without revealing what data they are inspecting. This is vital for:

• Confidential DeFi Positions: Traders can check liquidity pool reserves or their own positions without publicly linking their wallet address to their trading strategy.
• Private Audits: Regulators can verify compliance without disclosing which contracts or accounts are under review.
• General User Privacy: Masking the on-chain data a user is interested in, which is otherwise fully transparent in systems like Ethereum. This application decouples data availability from access pattern privacy.

PIR enhances federated learning and analytics by enabling private model update retrieval. In a federated learning round, a central server needs to fetch model updates from a subset of client devices. Using PIR, the server can retrieve a specific client's update without knowing which client's update it received. This adds a layer of client anonymity to the process, protecting participants from being identified based on their unique model contributions. It mitigates risks of membership inference attacks against the training process itself, strengthening the overall privacy guarantee beyond what standard secure aggregation alone provides.

PIR can facilitate privacy-preserving location queries. For example, a user could fetch map tiles, points of interest, or local business information from a geographic database without revealing their precise coordinates or destination. The client encodes a region of interest, and the PIR protocol retrieves the corresponding data without disclosing which tile or POI was accessed. This contrasts with standard services that require sending exact GPS coordinates. It enables useful services while implementing the principle of minimum disclosure, protecting against location tracking and profiling.

A form of encryption that allows computations to be performed directly on ciphertext. Unlike PIR, which protects query privacy, homomorphic encryption enables processing of encrypted data without decryption, preserving data confidentiality during computation. It is foundational for privacy-preserving machine learning and secure cloud computing.

• Fully Homomorphic Encryption (FHE): Supports arbitrary computations on encrypted data.
• Partially Homomorphic Encryption: Supports only specific operations, like addition or multiplication (e.g., Paillier, ElGamal).
• Use Case: A hospital could send encrypted patient records to a cloud server, which trains a model on the encrypted data and returns an encrypted result, never accessing plaintext.

A cryptographic protocol that enables multiple distributed parties to jointly compute a function over their private inputs while revealing nothing but the output. MPC and PIR share the goal of privacy-preserving computation but differ in architecture: MPC is multi-party and collaborative, while PIR is typically a two-party client-server protocol.

• Core Principle: Based on secret sharing and garbled circuits.
• Comparison to PIR: In MPC, all parties contribute private data; in PIR, the server holds all data, and the client's query is private.
• Example: Two banks can compute their total number of shared customers without revealing either bank's full customer list.

A specialized cryptographic protocol within the MPC family. It allows two parties, each holding a private set of items, to compute the intersection of their sets without revealing any elements not in the intersection. PSI is concerned with input privacy for both parties, whereas PIR focuses on query privacy for a single client against a server.

• Applications: Contact discovery in encrypted messaging, fraud detection across institutions, and collaborative threat intelligence.
• Efficiency: Modern PSI protocols using oblivious transfer and hashing can process millions of items in seconds.
• Variant: Private Set Union (PSU) computes the union of sets without revealing which set contributed which element.

A fundamental cryptographic primitive where a sender transmits one of several messages to a receiver, but remains oblivious to which message was received. 1-out-of-N OT is a core building block for many PIR protocols. The server (sender) holds N database items; the client (receiver) retrieves one item without the server learning the index.

• Role in PIR: Efficient PIR protocols are often constructed from a series of oblivious transfers.
• Extensions: Oblivious RAM (ORAM) allows a client to privately read and write to remote memory, generalizing PIR to private access patterns over multiple queries.

A rigorous mathematical framework that provides a quantifiable privacy guarantee by ensuring the output of a computation is statistically indistinguishable whether any single individual's data is included or excluded. While PIR protects which data is accessed, differential privacy protects the content of the data from revealing individual information.

• Mechanisms: Achieved by injecting calibrated noise (e.g., via the Laplace or Gaussian mechanism).
• Privacy Budget (ε): Tracks cumulative privacy loss across queries.
• Synergy with PIR: A system could use PIR to fetch records and then apply a differentially private algorithm to analyze them, protecting both access patterns and individual contributions.

A decentralized machine learning paradigm where a global model is trained across multiple client devices or servers holding local data, without exchanging the raw data itself. It addresses data locality and privacy. PIR could be integrated into federated learning for secure model aggregation or for privately retrieving global model updates from a central server.

• Core Process: Local training on device → secure aggregation of model updates → global model refinement.
• Privacy Threat: Even model updates can leak information; techniques like secure aggregation (often using MPC) and differential privacy are combined for protection.
• Contrast with PIR: Federated learning avoids centralizing data; PIR allows private queries to a centralized database.