OnionPIR is a single-server PIR scheme built on lattice-based homomorphic encryption. The textbook construction of homomorphic PIR — encrypt a one-hot selector vector (Enc(0), …, Enc(1), …) and let the server compute the inner product against the database — works in principle, but doesn't scale: the request grows linearly with the database. OnionPIR takes a different route, built around three ideas explored over the next three pages: reshape the database as a hypercube, mix two ciphertext flavors to walk it efficiently, and pack the whole query into a single ciphertext.

Reshape the database as a hypercube of shape N0 × 2 × 2 × … × 2. The paper's standard setup uses N0 = 512 for the initial dimension, then log2(N/N0) binary dimensions (~11 of them for a 1 M-entry database). An index idx becomes a tuple (i0, b1, …, bd−1): the initial dimension picks one of N0 columns, and each binary dimension is a single bit choosing top or bottom half of the remaining cube.

That's the whole data-structuring move. The server walks the hypercube one axis at a time, collapsing it by one dimension at each step. The animation below shows the traversal as pure index arithmetic — no cryptography yet. The next page introduces the two ciphertext flavors that let the server do exactly this walk under encryption, without learning which column or which half was chosen.