The Contract Behind a Private Query
For ZipPIR, the important starting point is not a particular encryption scheme but the contract a private query must satisfy. This chapter separates indexed retrieval from private set operations, then examines why ZipPIR chooses a single server and which costs a practical PIR system must account for. The result is a set of criteria for judging whether a small client state represents a real systems improvement or merely moves an unseen burden elsewhere.
PIR is an indexed lookup, not a private set operation
A database can be viewed as a collection of labeled values: a password record, a certificate timestamp, a blocklist result, or some other item identified by an index. In ordinary retrieval, the request exposes the label or index the client wants. In Private Information Retrieval, the server still answers with the value associated with one index, but the server should not learn which index the client selected. The desired result is therefore not “the server reveals nothing”; it is more precise: the server performs an indexed lookup without learning the target of that lookup.
That precision distinguishes PIR from another important privacy-enhancing functionality: Private Set Intersection, or PSI. Suppose two organizations each hold a private list of identifiers and want to know which identifiers appear in both lists. PSI produces a common-set result while keeping the non-common elements from the other party. Neither organization is asking a server to retrieve one position from a shared key-value database. Each party contributes a set, and the protected relationship is the overlap between those sets.
The difference can be made concrete. A password-breach check can be modeled as a client asking about one database entry: “What is associated with the item represented by my private query?” That is the indexed-retrieval shape addressed by PIR. A private contact-discovery exchange instead compares two address books and returns their common entries. That is the set-operation shape addressed by PSI. The applications may both involve sensitive identifiers, but their inputs, outputs, and privacy obligations are different.
NIST places both functionalities within privacy-enhancing cryptography, a broad area concerned with enabling useful interaction without exposing private information that the application does not need. Its informal descriptions make the distinction explicit: PIR concerns querying a key-value database while concealing which element was queried; PSI concerns finding common elements without revealing the non-intersecting components. The shared setting explains why the terms often appear together, but it does not make their protocols interchangeable.
PSI also has variants that change what the parties learn. A set operation may give the result to only one party, apply a function to each element, or return an aggregate such as a count rather than the elements themselves. Those choices are part of the functionality being protected. In PIR, the central question is instead which indexed value the server was asked to help retrieve. A protocol can be excellent at one task and irrelevant to the other even when both are described informally as “private data matching.”
This distinction helps locate ZipPIR. ZipPIR is not a general-purpose private computation framework and is not a PSI construction. It is a single-server PIR protocol designed around a particular engineering tension: high-throughput retrieval often becomes practical only after a database-dependent hint has been prepared, while a resource-constrained client may not be able to store or repeatedly refresh that hint. ZipPIR’s contribution must therefore be evaluated against the PIR contract and the cost of satisfying it, not against every possible privacy goal.
The same contract sets the boundary of the privacy claim. Hiding an index does not automatically hide the fact that a client connected, the timing of a request, the amount of data exchanged, or the client’s entitlement to use the service. Nor does it make the returned value harmless. Access control still determines whether a client should be allowed to query a database, and application policy still determines how the answer may be used. PIR protects a sensitive choice inside an authorized interaction; it does not replace the authorization layer around that interaction.
The diagram is deliberately about ideal functionality, not implementation. PIR begins with an index and returns a database value while concealing the index from the database holder. PSI begins with private sets and computes a relationship between them. Both can be useful in privacy-sensitive applications, but the shape of the protected information determines which design problem is being solved.
The single-server choice is an operational decision
A PIR deployment can distribute the database across multiple servers, asking each server to contribute a partial answer. That model can improve efficiency, but it relies on two conditions that are not merely technical details: the servers must hold identical database copies, and they must not collude. If servers combine their observations, the privacy argument may fail. If their copies diverge, the client may receive an answer about different database states rather than one consistent state.
Those conditions become more difficult when the database changes. A password-breach list, certificate record set, or blocklist is not necessarily static. Several servers need a coordinated view of each update, and the operator needs confidence that the non-collusion assumption continues to hold across organizations, administrators, and operational incidents. The authors of ZipPIR therefore focus on single-server PIR. One server is a compelling deployment target precisely because it avoids the need to arrange and maintain a trustworthy group of non-colluding replicas.
The single-server choice does not remove the privacy problem; it concentrates it. The server owns the database and performs the response computation, so the query must be formed in a way that reveals enough structure to answer but not enough to expose the selected index. The design also has to decide where the preparation needed to make that computation fast will live.
This is why a preprocessed hint is more than an optimization sitting beside the protocol. A hint is database-dependent knowledge or state prepared for later retrieval. It can make an online query simple, but it creates an owner and a maintenance path. If the client stores it, the client pays memory and receives a new version when the database changes. If the server stores it, the operator pays storage and preparation work for each client or supported query. If neither side stores it, the protocol may have to perform more public-key computation when a query arrives or communicate more during setup.
The hint also has a lifecycle that is easy to miss when attention stays on one request. At the beginning, a client or server creates preparation for a particular database state. During normal operation, the query relies on that preparation to avoid repeating expensive work. When the database changes, the system must either refresh the artifact, tolerate an explicitly defined transition, or fall back to a slower path. A client-held hint makes that refresh a distribution problem: many devices need the new state and must know which version is current. A server-held hint makes it an orchestration problem: the operator must allocate storage and recomputation capacity for the clients it supports. The privacy goal has not changed, but the failure surface has. A stale client artifact can make an otherwise valid query unusable; insufficient server preparation can turn a fast online path into a queue of pending work.
That is the systems meaning of “database-dependent.” It describes not just the size of an object, but its coupling to a particular version of the database and to the party responsible for keeping it usable. The design that best fits an application is the one whose state lifetime and refresh path match the application’s update rate and resource ownership.
The paper’s comparison of PIR designs makes these choices visible. Protocols using client-specific keys can avoid a large client-side hint, but their online work may include many public-key operations, limiting throughput. LWE-based systems such as SimplePIR make the online computation efficient by relying on a high-throughput hint, but that hint can be large and must track database changes. Sublinear-online systems may reduce the work associated with a query while requiring a demanding preprocessing phase, including in some cases streaming the database to the client. Other designs retain auxiliary state on the server. They all satisfy related PIR goals, but they do not have the same deployment shape.
A useful comparison has at least five dimensions.
Client state. How much persistent, database-dependent information must the client store? This is a hard constraint for a phone, browser, or embedded device, not just a line item in a benchmark. A large hint also creates a privacy and reliability dependency on the client retaining the right version.
Offline communication. What must cross the network before a query can be answered efficiently? A one-time setup exchange is different from sending a database-sized artifact, and both are different from redistributing fresh state after every update.
Online work. What happens after the client has chosen the item it wants? High throughput is valuable when requests are frequent or the database is large, but it describes only this phase. A fast online path can be purchased with expensive preparation elsewhere.
State ownership. Which party retains the information that makes future queries efficient, and does that state serve all clients or only one? Shared server preprocessing and client-specific preparation have different storage and scaling consequences.
Update coordination. What happens when the database changes? A protocol that is excellent for a static database may be awkward for a rapidly changing one if clients must download and install new hints. A design that avoids client contact may still require substantial server computation and storage.
These dimensions are coupled rather than independent switches. Reducing client state can increase server state; reducing online computation can increase offline work; reducing response size can increase query material or cryptographic preparation. The paper’s 1 GB comparison illustrates the scale of the choice by placing client storage, offline communication, and throughput on the same table, including alternatives with no client-side storage, large client hints, and very different offline costs. Some entries are extrapolated, so the table is best read as evidence of distinct burden patterns rather than as a universal ranking.
The dimensions also describe different failure conditions. A client-memory limit is reached before a query starts. An offline-bandwidth limit appears during enrollment or refresh. An online-computation limit appears as latency or reduced throughput under load. A server-state limit appears as storage growth across clients or supported queries. An update-coordination limit appears when a database changes faster than preparation can be regenerated or distributed. Treating all of these as one “performance” number would hide the reason a protocol succeeds or fails in a particular deployment.
For ZipPIR, the target is a particular combination: retain the simple, high-throughput style of an LWE-based online path, avoid a large database-dependent hint on the client, and let the server prepare and refresh the relevant state. The USENIX description characterizes the proposed protocol as reaching more than 2 GB/s without a large client-stored hint and using less than 200 KB of server-side storage per client in the described setting. Those statements identify the intended bargain, not an unconditional result. The server still has work to do, and the measurements must be read with their database size, payload, hardware, and implementation conditions.
The central comparison is therefore about burden placement. A client-specific-key design spends more computation to save client memory. A hint-based design spends memory and update bandwidth to save online computation. A server-state design saves the client at the cost of server persistence and preparation. ZipPIR proposes that ciphertext compression and an offline/online split can make the third arrangement efficient enough to preserve the fast path.
That proposal gives the single-server contract a sharper systems meaning. Privacy is not satisfied by an abstract statement that the index is hidden; the service must also be able to maintain the preparation needed to answer queries as the database evolves. The client must be able to participate without carrying a database-sized object. The server must be able to absorb the work without turning every request into a public-key bottleneck. Whether ZipPIR meets that combination depends on the mechanism that compresses the encrypted retrieval material and on the lifecycle that uses it.