Where the Cost Goes
ZipPIR enters a design space in which the same privacy goal can be purchased with very different resources. This chapter compares the main burden allocations described in the ZipPIR paper—client-specific keys, client-held hints, sublinear preprocessing, and server-held state—and uses client storage, offline communication, online work, and database updates as consistent criteria. The point is to identify the exact combination ZipPIR must achieve before its compression technique is more than an elegant cryptographic shortcut.
The same privacy goal can demand different kinds of work
A client-specific-key approach starts by giving the server cryptographic material associated with that client. The client does not need to carry a large, database-dependent hint, which is attractive for a browser or phone. The saving appears in persistent storage: the client keeps a key rather than a copy of database preparation. But the server must process the query in a way that uses public-key operations tied to the requested database. The ZipPIR paper says that these operations are usually linear in database size and that the resulting throughput reaches only up to hundreds of megabytes per second in the cited line of work.
That is not a contradiction. Public-key cryptography can provide the privacy interface while being a poor fit for scanning a large database at high speed. If every database element contributes to a response through an expensive operation, the server pays for that cost when a query arrives. The client has a small state, but the online path becomes the bottleneck. For an occasional request, that may be acceptable. For a service that answers many checks or must keep latency low, the savings in client memory can be outweighed by server computation.
A second approach prepares a database-dependent hint that makes the online work much simpler. SimplePIR, FrodoPIR, and DoublePIR are described as LWE-based examples in which the online phase approaches memory-bandwidth behavior through simple matrix–vector multiplication. This is a powerful change in the shape of the work: instead of performing many expensive public-key operations after the query arrives, the system does substantial preparation in advance and makes the live request comparatively regular.
The price is the hint itself. The paper uses 128 MB for SimplePIR over a 1 GB database as a motivating example. A large hint is not just a large download. It is persistent state tied to the database, so a client needs enough storage to retain it and a way to obtain a new version when the database changes. If a service has many users, every update can become a distribution event. A design can therefore have excellent query-time behavior and still be hard to deploy on the devices and networks that need it.
The update problem is especially important because the hint is coupled to a database state. A static benchmark can make the hint look like a one-time cost, but a changing database turns it into a recurring obligation. The operator must determine when a new hint is valid, deliver it to clients, and deal with clients that are offline, slow to update, or holding an older version. The issue is not that the protocol necessarily fails when a database changes; the issue is that high-throughput preparation has to be regenerated and redistributed if the hint lives on the client.
Sublinear-online approaches move the trade-off again. Their attraction is that the server can do less work that grows with the database when the query arrives. But “sublinear online” does not mean “lightweight overall.” The paper notes that Piano, for example, requires streaming the entire database to the client during preprocessing, while other approaches demand substantial client-side storage and computation. A client may therefore avoid a large persistent hint only by receiving a very large offline transfer or performing work that is unrealistic for a constrained device.
This is why an asymptotic label is not enough to choose a PIR protocol. A client experiences the full path: enrollment, preprocessing, query generation, waiting for an answer, receiving the response, and handling database updates. A service operator experiences a different path: preparing shared state, retaining per-client material, serving concurrent requests, and regenerating state as the database evolves. Two protocols with similar online complexity can impose entirely different operational costs.
The paper also describes a category in which auxiliary information is kept per client on the server. This avoids asking each client to store a large hint, but it changes the operator’s responsibility. HintlessPIR and YPIR remove client-specific storage in a different way by keeping a large, database-dependent hint at the server for all client queries. The categories overlap in their goals, but they do not have the same scaling behavior: a shared server hint, a per-client server state, and a client-held hint grow with different populations and update events.
The comparison can be summarized without treating any one column as decisive:
- Client-specific keys: little or no database-dependent client state, but more public-key work in the online path.
- Client-held high-throughput hints: fast and regular online computation, but substantial client storage and hint redistribution after changes.
- Sublinear-online preprocessing: reduced online work, but potentially heavy client-side transfer, storage, or computation before the query.
- Server-held auxiliary state: less client burden, but more server persistence and preparation, often with costs that depend on clients or supported queries.
These are not four versions of the same implementation. They are four answers to the question, “Who pays to make the private query fast?”
The diagram is a map of burden placement, not a claim that the categories are mutually exclusive in every protocol. It makes the design challenge visible: ZipPIR wants the server to absorb the preparation and state that a constrained client cannot conveniently carry, while preserving an online path closer to the high-throughput LWE-based designs.
The target is a combination, not a missing feature
To understand ZipPIR’s target, it helps to treat the main costs as coupled dimensions rather than a checklist of independent features.
Client storage is the most visible constraint in the title. The relevant question is not only how many bytes a client stores at setup, but whether those bytes depend on database size and whether they must be replaced as the database changes. A small, reusable key and seed have a different operational meaning from a hint that grows with the database. The former can fit a broad range of clients; the latter can make deployment dependent on device capacity, application storage policy, and update reliability.
Offline communication determines whether the system can enroll a client and refresh preparation without making the client absorb the database. A one-time public key exchange is not equivalent to a database-sized preprocessing stream. Nor is a one-time exchange equivalent to repeated hint redistribution. The timing of the bytes matters: setup traffic can be amortized across many queries, while a refresh requirement can recur whenever the source database changes.
Online throughput measures how quickly the live query is answered, but it is useful only after the client has successfully completed the offline path. A public-key-heavy protocol may save storage but limit the rate at which requests can be served. A matrix-based protocol may be extremely fast once its hint exists. A sublinear protocol may have a favorable online curve but impose an offline transfer that makes the overall service unattractive. The metric must be tied to the phase it measures.
Server state determines what the operator must retain and how that state scales. A single global hint can serve many clients but may be large. A client-specific state can be much smaller while multiplying storage and preparation work by the number of clients or supported queries. A design that is excellent for one registered client may have a different resource profile at a million clients. “No client-side storage” is therefore not the same as “no state”; it is a statement about which side owns the state.
Update coordination links all four dimensions. If the database changes, a client-held hint may have to be sent again. A server-held hint may be regenerated without contacting clients, but the server must have enough idle capacity, storage, and scheduling discipline to do the work before it is needed. An online computation that can tolerate a stale or partially refreshed state is a different design from one that requires an exact current hint. The paper’s point is not that updates become free, but that their network path can be changed.
These dimensions also expose why a universal winner is unlikely. Imagine two services using the same database. One has a small number of powerful, consistently connected clients and very expensive server compute; it may prefer client-held preparation. The other serves many phones, expects frequent database changes, and can dedicate server resources during idle periods; it may prefer server-managed preparation. The cryptographic privacy goal is similar, but the acceptable location of the cost is not.
For ZipPIR, the missing combination is clear. Client-specific keys show that small client state is possible, but the online public-key work limits throughput. High-throughput LWE-based schemes show that simple online computation is possible, but their hints can be too large and too tightly coupled to database updates. Sublinear approaches show that online work can be reduced further, but their preprocessing can burden the client. ZipPIR must keep the client light, keep the online path fast, and make server-managed preparation practical enough to handle changes.
The USENIX description states that ZipPIR compresses LWE ciphertexts into smaller Paillier ciphertexts, reaches more than 2 GB/s in the described evaluation, and requires less than 200 KB of server-side storage per client. Those claims describe the intended point in the design space. They do not mean that the server performs no preparation, that every response is smaller on every network, or that the protocol dominates under every workload. The paper’s detailed measurements and conditions are needed to understand how the combination was obtained.
The distinction between shared and client-specific state is also important. ZipPIR reuses a global database-derived component across clients, while the client-specific portion depends on the client’s public-key material. That arrangement can avoid sending an updated hint to every client after a database change, but it does not make client-specific preparation disappear. The server must still retain the relevant state and refresh it. The benefit is a different update topology: server work can replace a fleet-wide client communication event.
This is the gap that the next technical question must answer. If the server is going to hold and manipulate preparation material, it cannot simply run an expensive additive-encryption computation for every item and every query. That would reproduce the public-key bottleneck in a new location. The construction needs a smaller representation of the encrypted retrieval work, and it needs to separate expensive operations that do not depend on the current query from the operations that do.
ZipPIR’s design is therefore best understood as a resource-allocation proposal with a cryptographic enabler. Its success condition is not “the client stores nothing.” The stronger, more useful condition is: the client avoids a large database-dependent hint; the server can prepare and refresh the necessary state; the live request remains high-throughput; and the resulting communication and storage profile fits the application. The compression mechanism is what makes that combination plausible, but it must be examined on its own terms—what structure it uses, what it compresses, and where its assumptions stop.