Private Information Retrieval (PIR)

PIR protocols are categorized by their underlying security assumptions. Information-theoretic PIR guarantees the server learns absolutely nothing about the query, even with infinite computing power, but requires multiple non-colluding server replicas. Computational PIR relies on hard mathematical problems (e.g., quadratic residuosity, lattice-based cryptography) to secure a query against a single server. If the underlying cryptographic assumption holds, the server cannot distinguish which record was accessed.

• Multi-server IT-PIR: Requires 2+ servers; zero failure probability.
• Single-server CPIR: More practical infrastructure; security reduces to a hardness assumption.

A defining requirement of PIR is that the total communication between client and server must be strictly less than the size of the database (n). A trivial protocol where the server sends the entire database achieves perfect privacy but has O(n) communication. PIR protocols achieve sublinear communication, typically O(n^c) for some c < 1, or polylogarithmic in n.

• Naive download: O(n) communication, trivial privacy.
• PIR: O(log n) or O(n^c) communication, cryptographic privacy.
• This is the core efficiency metric that distinguishes PIR from a simple bulk transfer.

The fundamental security property of PIR is that the server's view of the protocol is computationally or statistically independent of the query index i. For any two indices i and j, the distribution of query messages sent by the client must be indistinguishable. This ensures the server cannot infer which record was retrieved, even by observing network traffic, query structure, or access timing.

• Indistinguishability: Query(i) ≈ Query(j) for all i, j.
• No trusted hardware required: Privacy is purely cryptographic.
• Protects access patterns: The server learns that some query occurred, but not which record.

Single-query PIR is computationally expensive. Modern deployments achieve practical throughput by amortizing the server's cost across batches of queries. Techniques like the XPIR protocol and SealPIR use homomorphic encryption to pack multiple queries into a single ciphertext, reducing the per-query cost by orders of magnitude.

• Single query: High latency, low throughput.
• Batch PIR: Amortized server work; throughput can reach gigabytes per second.
• Key technique: Query compression using fully homomorphic encryption (FHE) SIMD packing.

PIR protocols operate on different logical views of the database, which impacts efficiency. Bit PIR treats the database as an array of individual bits, retrieving one bit per query. Block PIR retrieves a contiguous block of bits (e.g., a 256-byte record) in a single query. Block retrieval is significantly more efficient for real-world records.

• Bit PIR: Simple model; high overhead for multi-bit records.
• Block PIR: Retrieves a full record; amortizes cryptographic cost.
• Keyword PIR: An extension where the query is a keyword, not an index.

Standard PIR assumes honest-but-curious servers that follow the protocol correctly. Byzantine-robust PIR extends the security model to servers that may actively deviate from the protocol—returning malformed or incorrect responses. This is critical for decentralized storage networks where servers cannot be trusted.

• Honest-but-curious: Server follows protocol, tries to learn query.
• Byzantine: Server may lie, send corrupt data, or collude.
• Defense: Verifiable computation or redundant queries across independent servers.

A method for splitting a function into compact secret shares that can be evaluated independently by two or more non-colluding servers. In the context of PIR, Distributed Point Functions (DPFs)—a subclass of FSS—enable highly efficient two-server PIR schemes. Each server evaluates its function share on the database and returns a share of the result, which the client combines to recover the desired record.

• Enables sublinear communication complexity in two-server PIR
• DPF-based PIR avoids expensive public-key cryptography
• Each server learns nothing about the query index

A cryptographic scheme that allows computation directly on encrypted data, producing an encrypted result that decrypts to the correct output. Fully Homomorphic Encryption (FHE) enables single-server PIR by allowing the client to encrypt the query index and the server to homomorphically evaluate a selection circuit over the entire database. The server never sees the plaintext index.

• Enables PIR with a single, non-replicated server
• Computational cost remains the primary practical bottleneck
• Lattice-based HE schemes provide post-quantum security

A cryptographic technique that hides the access pattern—which memory locations are read or written—from an observer. While PIR protects the privacy of a single read operation, ORAM provides ongoing privacy across a sequence of reads and writes. ORAM is often used to compile a program to run obliviously on a remote server, preventing data leakage through memory access side-channels.

• Hides both read and write access patterns
• Typically requires logarithmic or polylogarithmic overhead
• Complements PIR for interactive database operations

A broad class of protocols that enable multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other. PIR is a specific instance of MPC where the function is a database lookup, the server's input is the database, and the client's input is the query index. General MPC frameworks like SPDZ and garbled circuits can implement PIR as a special case.

• PIR is a restricted, highly optimized form of MPC
• MPC provides stronger security against malicious adversaries
• General MPC incurs higher overhead than purpose-built PIR

A protocol that allows two parties to compute the intersection of their private datasets without revealing any elements outside the intersection. PSI and PIR share underlying cryptographic techniques, including oblivious transfer and homomorphic encryption. In fact, PIR can be used as a subroutine in PSI protocols to efficiently check membership without revealing the queried element.

• Both rely on OT and HE primitives
• PSI reveals the intersection size and contents to authorized parties
• Used in contact discovery, password monitoring, and ad conversion tracking