ZipPIR in Motion: Setup, Hint, Query, Response, Extract

ZipPIR becomes a system rather than a compression idea when its state and transitions are made explicit. This chapter traces the five routines that connect a client’s private index to a server’s answer, identifies which party owns each piece of material, and follows the offline work through a database update. That lifecycle explains the practical meaning of a small client state: the client still participates in every query, but the server can prepare database-dependent work without asking the client to carry a giant hint.

Enrollment creates two kinds of state

The protocol starts with SETUP, performed by the client. The client generates a Paillier key pair and samples random Paillier ciphertext material. The private part of the Paillier key remains with the client. The setup also produces a pointer-like value that lets the client relate its later query material to the sampled ciphertexts. In the basic construction, the server receives the public modulus and the sampled ciphertext material as a request for preparation; the client keeps the secret key and the corresponding private state.

This division is already different from a client-held database hint. The client receives or generates cryptographic material whose size is tied to the security parameters and the query arrangement, not to the full database. The server, by contrast, is the side that can see the database and has the resources to prepare state derived from it. The two sides are linked by encrypted key material, not by the client revealing its private LWE key.

The paper also describes an optimization for reducing offline communication. Instead of sending every random ciphertext that will be needed for future preparation, the client and server can agree on a pseudorandom-generator seed. The seed can generate the random encrypted components in a coordinated way. The client can retain the seed with the Paillier private key, while the server uses the agreed setup material to prepare future hints. Under the construction’s computational assumptions, this makes the continuing offline phase nearly silent after the initial public key and seed exchange.

That word “nearly” is important. A seed replaces repeated transmission; it does not replace the state and work that the seed expands. The server still has to generate and retain the appropriate client-specific preparation. The client still needs the private key and seed to form and decode future requests. If either side loses the material needed to derive the same state, the protocol cannot be expected to complete the intended exchange. Constant-size client state is a persistence property, not a claim that state can be discarded without consequence.

The next routine is HINT, performed by the server. The server has a database-dependent matrix produced by the LWE-based PIR arrangement. It combines that matrix with the client’s setup material using Paillier’s additive operations and produces a client-specific hint. In the simplified construction, the hint is the server’s prepared encrypted contribution to the eventual phase calculation. The server stores it until the client issues the query it supports.

There are two kinds of reuse here.