HarmonyPIR is a single-server stateful PIR scheme. There is one honest-but-curious server holding the database, and no non-collusion assumption. The scheme's leverage comes from a different direction: the client is willing to do work once, up front, to make every later query cheap.

The protocol splits into two phases. In the offline phase, the client streams the whole database from the server once and condenses it into a short list of hints that it keeps locally. In the online phase, each query is small in both directions — roughly √N entries in the request, √N entries in the response — and the client recovers the target row by combining the response with one of its hints. After about √N queries the hints are used up and the offline phase has to run again.

One subtlety worth flagging up front: the online-phase request is not an encrypted version of the query index q. It's a batch of √N plain database indices — a slice of the client's private hint table — with one of them swapped for a freshly sampled random index so the server can't pick out which slot the client actually cares about. The server just looks up those indices and sends back their values. All of the privacy comes from how the client chose the batch, not from any cryptography on the wire. The rest of this section is about that choice.