BitcoinPIR
Contents 04 DPF-PIR

DPF-PIR — two servers, one XOR

A Distributed Point Function is a pair of short keys k0, k1 with a special property. You can evaluate either key at any index i and get a pseudorandom bit. But for one specific index α — the "point" the two keys were built around — the two outputs are rigged so that: 

Eval(k0, i) XOR Eval(k1, i)  =  1 if i = α,  0 otherwise

Here's the trick that makes DPF feel magical. Take a single key and evaluate it at all 8 indices — you get something that looks like a coin-flip sequence. Take the other key and do the same — another coin-flip sequence. Neither row, on its own, tells you anything about α. Only when you XOR the two rows does a single 1 bit pop out at α, with everything else cancelling to 0.

Server A k₀ Server B k₁ 000001010011100101110111 α Eval(k₀, i): ← looks random 1 0 1 0 0 1 1 0 Eval(k₁, i): ← also random 1 0 1 0 0 0 1 0 k₀ ⊕ k₁: ← a single 1 at α — the indicator 0 0 0 0 0 1 0 0
Each server's evaluation looks random on its own. Only the XOR of both rows reveals α.

The two servers never learn α on their own — each sees only a pseudorandom-looking bit pattern like the ones above. Both would have to collude and XOR their keys to recover α; that's the trust assumption DPF-PIR is built on.

To turn this into a PIR query, the servers don't just output their evaluation bits — they use them as a mask. Each server computes ∑i Eval(k, i) · DB[i] (XOR each row where its bit is 1 into an accumulator) and returns the single accumulated value. The client XORs the two accumulators; every row except row α is XORed an even number of times and cancels. Only the target row survives.