BitcoinPIR
Contents 05 OnionPIR QueryPack, one ciphertext

OnionPIR — one packed ciphertext

We have the hypercube and the two ciphertext flavors. The last problem: if the client ships N0 + d − 1 selectors — 512 BFV ciphertexts for the initial dimension plus one RGSW per binary dim — at the standard parameters that's several megabytes per query. Too much.

QueryPack solves it. The client writes every selection bit — i0 for the initial dim and every bj for the remaining dims — into specific polynomial coefficients of a single BFV ciphertext, then sends that one ciphertext plus a short pseudorandom seed. The server runs QueryUnpack locally, applying a tree of substitution and RGSW-gadget operations, and recovers:

  • A length-N0 vector of BFV ciphertexts, one per initial-dim slot, with Enc(1) at position i0 and Enc(0) elsewhere.
  • One RGSW ciphertext per binary dimension, encrypting bj.

Net request size: about 16 KB at the standard parameters, regardless of database size. All the expansion work happens server-side where it costs nothing to ship.

Client QueryPack 1 BFV ct Server: QueryUnpack BFV vector — initial-dim selectors Enc(0) Enc(0) Enc(1) Enc(0) RGSW bits — one per remaining dim RGSW(b1) RGSW(b2) Database as 4 × 2 × 2 hypercube (flattened) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ① BFV dot product collapses dim 0 → 1 column ② External product RGSW(b₁): pick half ③ External product RGSW(b₂): pick half ④ ModSwitch, send Enc(entry 6) shrunk, → client
The single packed ciphertext unpacks into a BFV selector vector (initial dim) and RGSW bits. The hypercube then collapses one axis per ciphertext.

The protocol in one read-through

  1. Client: express idx as (i0, b1, …, bd−1), QueryPack into one BFV ciphertext, send (~16 KB).
  2. Server — QueryUnpack: derive N0 BFV selectors plus d − 1 RGSW ciphertexts.
  3. Server — initial dim: dot-product the BFV vector with the N0-wide slab of the database. Collapses dim 0.
  4. Server — remaining dims: one external product per binary dim, x + RGSW(bj)·(y − x). Each step halves the remaining hypercube.
  5. Server — finish: one BFV ciphertext remains. Modulus-switch it from 60-bit to 27-bit coefficients to shrink the response, send (~13–57 KB depending on parameters).
  6. Client: decrypt, read the row.

Numbers from the paper

From the OnionPIR paper (ePrint 2025/1142), measured on a single core of an AWS c5n.9xlarge (Xeon 8124M @ 3.0 GHz), for a 1 GB database:

  • Request: ~16 KB (standard parameters).
  • Response: 13.5–57 KB, giving a response blowup of ~2.5× the raw row size — vs ~100× for older compression-less PIR.
  • Throughput: 1100–1600 MB/s server-side, close to memory bandwidth.
  • Server storage: 0.63–2.9 MB of per-client key material (or send it with each request if the server prefers to be stateless).

In BitcoinPIR, OnionPIR is one of three interchangeable backends. The rows it fetches are cuckoo bins, not raw records — the batch-code layer sits above whichever PIR backend is plugged in, so the same protocol shape works for DPF-PIR, OnionPIR, or HarmonyPIR.