Private Information Retrieval
Private information retrieval, universally abbreviated PIR, is a cryptographic protocol that lets a client fetch one record from a database without revealing to the server which record it wanted. The database itself is ordinary. In the standard formulation the server holds the data in the clear, may publish it freely, and learns nothing beyond the fact that some query occurred. What the protocol hides is the index, and with it the intent behind the lookup.
That distinction is what separates PIR from the encryption technologies that surround it. Transport encryption hides a query from anyone watching the wire but not from the server that answers it. Encrypted storage hides data from an operator who never legitimately reads it. PIR addresses a different leak entirely: the access pattern. Which telephone number a handset checked against a caller-identification service, which certificate a browser tested for revocation, which medical code a clinical application looked up, and which advertisement identifier a device requested are each sensitive precisely because of what the choice reveals about the person making it. A server that answers such queries in the obvious way accumulates a behavioral record that no amount of link encryption removes.
PIR matters to hardware and systems engineers because its cost is a hardware cost. Absent the preprocessing schemes described below, every construction forces the server to touch essentially the whole database for every query, so the performance question is not one of algorithmic cleverness but of memory bandwidth, arithmetic throughput, and cache behavior. A PIR server is best understood as a streaming numerical kernel that happens to have a cryptographic purpose, and its design decisions are the familiar ones: how wide the datapath is, how many bytes move per operation, and where the roofline lies.
The Problem and the Trivial Solution
Formally, a server holds a database of n records. A client wants record i and must learn its contents while the server gains no information about i. The requirement holds for every index: the server's view of the interaction must look the same whichever record was requested, either identically or, in the weaker computational setting, to any adversary bounded by feasible computation.
One solution always works. The client downloads the entire database and reads record i locally. This is perfectly private, requires no cryptography, and establishes the baseline that every real scheme must beat. Its communication cost is the full database size, which is prohibitive for a database of any consequence and impossible for one that changes frequently. The entire field exists to reduce that communication while preserving the privacy guarantee, and every scheme is judged against the trivial download.
Two costs must be tracked separately, and confusing them is the most common source of misplaced optimism about PIR. Communication is the number of bytes exchanged, comprising the query the client uploads and the response the server returns. Computation is the work the server performs. Schemes whose communication grows only polylogarithmically in the database size have existed since the late 1990s. Reducing server computation proved far harder, and for good reason, as explained below.
Two Families: Information-Theoretic and Computational
PIR schemes divide along the nature of their privacy guarantee. Information-theoretic schemes hide the index even from a server with unlimited computing power, because the query genuinely carries no information about the index in the Shannon sense. Computational schemes hide the index only from a server bounded by feasible computation, resting on a hardness assumption such as the difficulty of the learning-with-errors problem. The distinction is not academic: it determines how many servers are required and what the failure of an assumption would cost.
Multi-Server, Information-Theoretic PIR
The field began with the multi-server case. Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan introduced private information retrieval at the 1995 IEEE Symposium on Foundations of Computer Science, with the journal version following in the Journal of the ACM in 1998, and proved a discouraging fact along with it: with a single server, information-theoretic privacy requires communication at least as large as the database. Perfect privacy against one unbounded server offers no improvement on downloading everything.
The escape is replication. If the database is copied to two or more servers that do not collude, sublinear communication becomes possible. The simplest construction is worth stating because it makes the mechanism concrete. The client chooses a uniformly random subset of record indices, sends that subset to the first server, and sends the same subset with index i toggled to the second server. Each server returns the bitwise exclusive-or of the records it was asked for. The client combines the two responses with a further exclusive-or, and every record except i cancels, leaving record i alone. Neither server sees anything but a uniformly random subset, so neither learns anything at all about i. Arranging the database as a two-dimensional array and recursing reduces communication further; the original paper achieved communication on the order of the cube root of the database size for two servers.
Modern multi-server practice replaces the explicit subset with a distributed point function, a form of function secret sharing introduced by Niv Gilboa and Yuval Ishai in 2014 and developed with Elette Boyle in subsequent work. A distributed point function compresses the shares of a query vector that is zero everywhere except at position i into keys of size proportional to the logarithm of the database size, so the upload shrinks from the size of the database to a few hundred bytes. Two-server PIR built this way is fast, simple, and free of heavy public-key arithmetic. Theoretical work has pushed the asymptotics much further: Zeev Dvir and Sivakanth Gopi showed in work published in the Journal of the ACM in 2016 that two-server PIR is possible with sub-polynomial communication.
The cost of the multi-server approach is entirely organizational. Privacy evaporates the moment the operators collude, share infrastructure, or are compelled by the same legal authority. Deploying two servers under genuinely independent control, in different jurisdictions and under different administrative teams, is a governance problem that many services cannot solve, which is why single-server constructions attract so much attention despite their higher cost.
Single-Server, Computational PIR
Eyal Kushilevitz and Rafail Ostrovsky showed in 1997 that relaxing the guarantee from information-theoretic to computational removes the single-server barrier. Their construction, based on the quadratic residuosity assumption, achieved communication that grows only as a small power of the database size. Christian Cachin, Silvio Micali, and Markus Stadler followed in 1999 with a scheme achieving polylogarithmic communication under the Φ-hiding assumption. These results settled the theory: one server suffices if the adversary is computationally bounded.
Every practical single-server scheme in use today follows the same shape. The client encrypts a selection vector under a homomorphic encryption scheme, the server evaluates a homomorphic inner product of that vector with the database, and the client decrypts the single record that survives. Because the server operates on ciphertexts throughout, it cannot tell which coefficient of the selection vector was set. The construction is described in more detail in the next section, and the arithmetic that underlies it is treated under homomorphic encryption hardware.
Homomorphic Encryption as the Modern Foundation
Single-server PIR is among the first applications of homomorphic encryption to reach production, and the reason is a matter of circuit depth. Selecting a record is a linear operation: it is a sum of database entries weighted by a selection vector that is one at the desired index and zero elsewhere. Linear operations consume very little of a lattice ciphertext's noise budget, so PIR fits comfortably inside a leveled or somewhat homomorphic scheme and never requires bootstrapping. Deep computations such as encrypted neural network inference are what drive the demand for large accelerators; PIR runs acceptably on commodity servers today precisely because it stays shallow.
Query Compression and Expansion
The naive version of the protocol is unusable because the client must upload one ciphertext per database record. The standard fix is to arrange the database as a multidimensional hypercube and to have the client send one selection vector per dimension, reducing the upload from n ciphertexts to a number proportional to the dimension-wise side lengths. SealPIR, presented by Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty at the 2018 IEEE Symposium on Security and Privacy, went further with a technique called oblivious expansion: the client sends a single ciphertext, and the server homomorphically expands it into the full vector of selection ciphertexts using automorphisms already available in the encryption scheme. Query size drops by orders of magnitude at the cost of additional server work.
Response Overhead and Scheme Composition
The second inefficiency is response expansion. A homomorphic ciphertext is far larger than the plaintext it carries, and a multidimensional scheme multiplies ciphertexts together at each dimension, inflating the returned data further. Later designs attacked this by composing two encryption schemes with complementary properties. OnionPIR, published at the 2021 ACM Conference on Computer and Communications Security, combines the BFV scheme with the GSW scheme so that the dimension-folding steps use an external product that does not grow the ciphertext, cutting the response expansion factor to a small constant. Spiral, presented by Samir Menon and David Wu at the 2022 IEEE Symposium on Security and Privacy, applies a similar Regev-to-GSW composition and further improves throughput.
Plain-LWE Designs and the Client Hint
A distinct line of work abandons ring-based schemes in favor of plain learning-with-errors encryption, trading elegant asymptotics for raw speed. SimplePIR and DoublePIR, presented by Alexandra Henzinger and colleagues at USENIX Security 2023, reduce the server's work to a matrix-vector product over machine-word integers, an operation that modern processors execute at close to memory speed; the authors report server throughput of about ten gigabytes per second per core, which approaches both the memory bandwidth of the machine and the throughput of the fastest two-server schemes. The price is state. The client must first download a hint derived from the database, reusable across an unbounded number of queries but invalid whenever the database changes; for a one-gigabyte database that hint is roughly 120 megabytes, which is a substantial imposition on a mobile client. DoublePIR shrinks the hint to about 16 megabytes and largely decouples its size from the database size, at the cost of somewhat larger queries and a throughput nearer 7.4 gigabytes per second per core. FrodoPIR, published in Proceedings on Privacy Enhancing Technologies in 2023 by researchers at Brave, adopts a similar stateful, preprocessing-heavy structure aimed at browser workloads.
The Linear-Scan Barrier and Preprocessing
Reducing communication was the easier half of the problem. Server computation is bound by a result that follows from the definition itself: if the server skipped any record while answering, the fact that it skipped that record would reveal that the record was not the one requested. Amos Beimel, Yuval Ishai, and Tal Malkin formalized the argument at CRYPTO 2000, showing that sublinear server computation is impossible without preprocessing, and proposed the preprocessing model in response. In the plain model every PIR query therefore costs at least one full pass over the database, and no amount of indexing helps, because an index is exactly the access-pattern leak the protocol exists to prevent.
The way around the barrier is to move work out of the query path. Two forms of preprocessing are used. Server-side preprocessing transforms the database once into an encoded form that answers queries faster, at the cost of storage and of recomputation whenever the data change. Client-side preprocessing has each client download a compact hint during an offline phase and then answer many queries against it with sublinear online work. Piano, presented at the 2024 IEEE Symposium on Security and Privacy, showed that the client-preprocessing model can be built from pseudorandom functions alone, with no homomorphic encryption at all. Its amortized server work, its online communication, and its client storage all grow as roughly the square root of the database size, and its authors report improvements of one to two orders of magnitude over prior single-server schemes. Client storage is the term to watch, because it is precisely what the model trades computation for, and a client that cannot hold the hint cannot use the scheme. How far that trade can be pushed is now understood: a construction presented at EUROCRYPT 2025 matches, to within constant factors, a lower bound requiring the product of client storage and amortized server probes per query to grow with the total size of the database in bits. Subsequent work has concentrated on reducing the cost of the offline phase itself, which in a stateful deployment becomes the dominant expense.
The practical consequence for a system architect is that PIR imposes a hard floor on serving cost that is proportional to database size times query rate, unless the deployment can absorb the statefulness that preprocessing requires. A database of a few gigabytes answering thousands of queries per second is a serious infrastructure commitment. This is why real deployments partition aggressively, keep per-shard databases small, and accept a modest leak of which shard was consulted in exchange for a large reduction in work.
Variants and Extensions
The basic index-lookup formulation is rarely what an application needs, and several standard variants close the gap.
Keyword PIR retrieves by key rather than by position, which is what a telephone-number or identifier lookup actually requires. It is built by layering a hashing or oblivious data structure on top of index PIR, typically cuckoo hashing, so that a key maps to a small set of candidate positions.
Batch PIR answers several queries in one pass over the database, amortizing the unavoidable linear scan across a batch and dramatically improving throughput for clients that need multiple records at once.
Symmetric PIR adds the reciprocal guarantee: the client learns record i and nothing about any other record. Plain PIR makes no such promise, and in several schemes a malicious client can extract more than one record's worth of information per query. Symmetric PIR requires oblivious transfer machinery and is closely related to the protocols described under secure multi-party computation.
Authenticated PIR addresses integrity rather than privacy. A standard PIR server can return a wrong answer undetected, because the client cannot see what it was given until decryption and has no reference to check it against. Authenticated schemes bind responses to a committed digest of the database so that a client detects tampering, and recent work has reduced their preprocessing and communication overheads considerably. Where the digest is published on a transparency log or a ledger, the guarantee extends to consistency across clients, connecting to the material under distributed storage systems.
Hardware Acceleration and System Design
Because the server must scan everything, PIR is an unusually pure hardware problem, and its acceleration strategy depends sharply on which family of scheme is deployed.
The Memory-Bandwidth Roofline
Plain-LWE schemes of the SimplePIR family perform roughly one multiply-accumulate on a small integer for each database element read. That is an arithmetic intensity near the lowest achievable, which places the kernel firmly in the memory-bound region of the roofline. Server throughput is therefore governed by how fast bytes arrive from memory, not by core count or clock frequency, and a PIR server scales by adding memory channels rather than threads. This makes the workload a natural candidate for high-bandwidth memory and, more speculatively, for the in-memory computing architectures that perform arithmetic within the memory array and avoid moving the database at all. The access pattern is a predictable sequential stream, which suits prefetchers well and makes achieved bandwidth close to peak, so published throughput figures for these schemes are unusually honest reflections of the hardware.
Arithmetic Engines for Ring-Based Schemes
Ring-based schemes such as BFV shift the balance toward computation. Their inner loops are number-theoretic transforms for polynomial multiplication, modular reduction over large moduli, and residue-number-system arithmetic that decomposes wide operands into machine-word lanes. These are the same primitives targeted by dedicated homomorphic encryption accelerators, including the application-specific designs funded under the Defense Advanced Research Projects Agency's Data Protection in Virtual Environments program, and by the wider study of arithmetic for cryptography. A PIR server built on such a scheme benefits directly from any improvement in transform throughput, and unlike deep homomorphic workloads it never pays for bootstrapping.
Graphics Processors and Reconfigurable Logic
Both families map well onto graphics processor architectures. The linear scan is embarrassingly parallel across database blocks, the arithmetic is small-integer modular work that vector units handle efficiently, and high-bandwidth memory on modern accelerator cards addresses the bandwidth constraint directly. Reconfigurable logic offers a different advantage. An FPGA can be configured with a datapath whose width matches the scheme's exact modulus, eliminating the wasted bits that arise when a 30-bit or 60-bit modulus is forced into a 64-bit machine word, and can place transform butterflies and modular reducers in deep pipelines that sustain one result per clock. Where a service front-ends a large corpus, the PIR kernel can also be pushed toward storage, in the manner of the near-data processing discussed under database storage engines.
Enclaves as a Competing Approach
Hardware isolation offers a cheaper route to the same application-level goal. A service can place its lookup logic inside a trusted execution environment, attest the code to clients, and answer queries at close to plaintext speed. The catch is that an enclave does not by itself hide access patterns: an operator who observes memory traffic or page faults can often infer which record was touched, so a correct enclave-based design must still scan obliviously or employ oblivious RAM internally, which restores much of the cost. The trust model also differs fundamentally, since the client must trust the processor vendor, the firmware, and the enclave's resistance to the side-channel and fault-injection attacks catalogued under side-channel attack prevention. Cryptographic PIR trusts only a mathematical assumption. Signal's evaluation of private contact discovery is the well-known instance of this trade-off resolved in favor of enclaves, chosen on grounds of scale rather than of security preference.
Deployments
PIR is far commoner in the literature than in the field. Three decades of papers have yielded a small number of production deployments, and those share a common profile: modest database size, high tolerance for latency, and a privacy requirement strong enough to justify the serving cost. Published throughput figures are laboratory results measured on a chosen corpus and parameter set, and an architect should treat them as an upper bound rather than as a budget.
The most visible is Apple's Live Caller ID Lookup, introduced with iOS 18. A handset that receives a call from an unknown number queries a third-party service for caller identification and spam classification, and the query is a keyword PIR lookup built on the BFV scheme so that the service returns an answer without learning which number was asked about. Apple released the supporting implementation as the open-source swift-homomorphic-encryption package under the Apache 2.0 license in 2024, with parameters chosen for 128-bit security against both classical and quantum adversaries, the underlying ring learning-with-errors assumption being believed to resist quantum attack.
The scale of that deployment is easy to overstate. Apple ships the client framework with the operating system, but the framework only mediates: a third party must run the PIR server and supply the data, and the user must enable the service. Truecaller was the first provider to adopt it at scale, requiring iOS 18.2 or later. The framework is therefore present on a very large number of handsets while the number of services actually answering PIR queries through it remains small. The case is still instructive, because it runs on ordinary server hardware: the workload is shallow, heavily batched, and co-designed with its parameter set.
Research systems have demonstrated larger ambitions. Tiptoe, presented at the 2023 ACM Symposium on Operating Systems Principles, built a private web search engine on PIR by combining an embedding-based ranking step with private retrieval of the matching documents, showing that a corpus of hundreds of millions of pages can be searched without the server learning the query, albeit at a cost per search far above conventional search. Other proposed applications recur throughout the literature: certificate revocation and safe-browsing checks, in which the identity of the site being visited is precisely what must not leak; private lookups of breach corpora; and privacy-preserving retrieval of advertisements or content recommendations. Several of these overlap with the network-layer techniques surveyed under privacy and anonymity technologies.
Limitations and Failure Modes
PIR guarantees are narrow and precise, and most disappointments arise from expecting more than the definition offers.
PIR hides the index, not the fact or the timing of a query. A server still observes that a particular client made a request at a particular moment, from a particular address, and at a particular rate. Traffic analysis over these observable features can reveal a great deal, so serious deployments combine PIR with anonymizing transport, fixed query schedules, or cover traffic.
Preprocessing schemes leak through their state. A client hint is derived from a specific database version, so refreshing it after each update signals when the client last synchronized and can partition clients into distinguishable cohorts. Stateful designs must be evaluated for what the hint download itself reveals.
Database updates are expensive. Preprocessed structures and published digests must be rebuilt when data change, and a rapidly changing database can spend more effort on maintenance than on serving. This is the main reason PIR suits reference data, such as identifier directories and revocation lists, better than transactional data.
Multi-server privacy is only as strong as the independence of the operators, which is an organizational property that no protocol can enforce and no client can verify. Finally, plain PIR offers no integrity: without the authenticated variants described above, a server that returns a fabricated record is indistinguishable from an honest one, and a client acting on a forged revocation status or a forged identity record may be worse off than if it had queried in the clear.
Relationship to Neighboring Technologies
PIR is easily confused with several adjacent primitives, and the distinctions are worth stating plainly. Oblivious RAM hides the access pattern of a client reading and writing its own encrypted data held on an untrusted server; PIR hides the access pattern of many clients reading shared data that the server holds in the clear, and generally requires no persistent client state. Searchable encryption allows keyword search over encrypted data but typically leaks access and search patterns by design, trading privacy for the sublinear performance that PIR provably cannot have. Private set intersection lets two parties learn their common elements; it solves the contact-discovery problem from a different direction and belongs to the multi-party computation family. Differential privacy, treated under differential privacy, bounds what a released statistic reveals about individuals in the data, which is orthogonal to hiding which record a client read. The relationships among all of these are surveyed at the level of the category under privacy-preserving technologies.
Conclusion
Private information retrieval solves a specific and under-appreciated problem: the query itself, not merely its contents, is often the sensitive part of a lookup. The theory has been settled for three decades. Multi-server schemes buy information-theoretic privacy with an assumption of non-collusion; single-server schemes buy independence from that assumption with lattice cryptography and a much higher computational bill. Homomorphic encryption made the single-server case practical, preprocessing broke the amortized linear-computation barrier, and the primitive has now reached a consumer operating system. Deployment nonetheless remains the exception, and the distance between the volume of published schemes and the number of running services is the honest measure of the field's maturity.
What remains is an engineering problem with a hard floor. Answering a query still costs a pass over the database, and the preprocessing schemes that avoid that pass online only relocate the work into an offline phase and a stateful client. Improving PIR therefore means improving how fast a machine can stream and transform bytes. That places the field squarely in the domain of memory bandwidth, arithmetic pipelines, and accelerator design rather than of protocol invention alone, and it is why progress in PIR now tracks progress in hardware as closely as it tracks progress in cryptography.