BitcoinPIR
Contents 05 OnionPIR BFV, RGSW, external product

OnionPIR — two ciphertext flavors

We have a hypercube to walk. Each axis is a choice the client already knows but the server must not learn. OnionPIR mixes two Ring-LWE ciphertext types, picking each where it's cheapest.

BFV — for the initial dimension

BFV is a standard leveled FHE scheme. A BFV ciphertext encrypts a polynomial, and it supports cheap plaintext-ciphertext multiplications — the plaintext stays in the clear, the ciphertext stays encrypted, and noise grows only a little. For the initial dimension, the server has an N0-long vector of BFV selectors (all Enc(0)s except one Enc(1) at position i0) and computes a dot product against each N0-wide slab of the plaintext database. That's just one plaintext-ciphertext multiply per database entry — the bottleneck, but cheap per row.

RGSW — for every remaining dimension

RGSW is a bulkier ciphertext type. It stores multiple rows of Ring-LWE encryptions of the same bit, arranged so that a special product operator becomes available: the external product. The external product multiplies a BFV ciphertext by an RGSW ciphertext and returns a BFV ciphertext. Crucially, its noise grows additively, not multiplicatively: 

noise(BFV × RGSW) ≈ noise(BFV) + small_constant

Compare that to a naive ciphertext-ciphertext multiplication, where noise roughly multiplies. After three or four multiplicative growth steps the ciphertext would decode to garbage. With additive growth, the server can chain ~20 external products in a row and the result still decrypts cleanly. That's what makes many-dimensional hypercube traversal practical at all.

One fold step: x + RGSW(b) · ( y − x ) BFV(x) top half BFV(y) bottom half BFV(y − x) subtract, cheap RGSW(b) 0 or 1, encrypted ExternalProduct BFV × RGSW → BFV BFV(x + b(y−x)) = x if b=0, y if b=1 Noise budget across many folds external product (additive growth) ~20 folds use a small fraction of the budget — still decrypts cleanly. naive ct × ct (multiplicative growth) Noise blows past the budget after only a few folds — decryption fails. That's the whole reason OnionPIR can afford many-dimensional hypercubes.
For each binary dimension, fold two halves x, y using a single RGSW(b). Every fold adds only a small constant to the noise budget.

So the protocol shape is now: initial dimension collapses with plaintext-ciphertext multiplies against a BFV selector vector; every subsequent dimension collapses with one external product against a single RGSW ciphertext. What we haven't dealt with yet is how the client ships all those selectors without sending megabytes of ciphertext. That's the next page.