[messaging] PIR (in Pynchon Gate)

[Robert Ransom]

On 3/24/14, Tom Ritter <tom at ritter.vg> wrote:
> On 24 March 2014 02:48, Brian Warner <warner at lothar.com> wrote:
>
>> A recipient figures out which slots they're interested in for a given
>> day's dataset (both H(nym+date) and a handful following it), then for
>> each slot, they compute some number of million-bit vectors, one for each
>> distributor they're going to use. (you must use at least two, and the
>> unlinkability holds if at least one of the distributors you use does not
>> collude with the rest). All but the last vector is randomly generated.
>> The final vector is created by XORing all the other strings together,
>> and then flipping the bit of the one slot you're interested in. The
>> recipient sends one vector to each distributor.
>>
>> The distributor computes the XOR of all slots that have a 1-bit in the
>> vector, and returns the result (equal in size to a single slot, e.g.
>> 1kB). The recipient XORs together all of the results to get just the
>> desired slot contents, since everything else XORs into zeros.
>>
>> I'm confused on these parts - I'm not able to connect it in my head in a
> way that doesn't send something the size of the whole database down.  Let's
> say there's 10 slots of 1KB each, and 5 distributors.
>
> I generate 5 * 10 = 50 vectors of 1KB each? 40 are randomly generated, but
> the last 10 are chosen such that the slots I care about are 1's?  That's
> not right...
>
> I generate 5 vectors of 10 bits each? And if vector #1 is 1001000000 the
> distributor XORs slots 1 and 4 together and sends me the result? That can't
> be right either, because while the slots I don't care about will XOR out,
> I'd only have the XOR of the slots I do care about - not the actual
> slots....

For each slot that you care about: Generate 4 vectors of 10 bits each
uniformly at random, then compute the fifth as the XOR of all the
random vectors *and* a vector whose only 1 bit is in the position of
the slot you care about.  Send each vector to a different distributor;
if they all reply honestly, the XOR of all the replies will be the
slot you care about.


Robert Ransom