[messaging] PIR (in Pynchon Gate)

[Tom Ritter]

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....

Do I generate 5 vectors of 10 bits, each with 3 1's, and then 3 vectors of
1KB? And if distributor #1 gets 1001001000, it XORs slot #1 with vector #1?
 That doesn't seem like what you described...

Sorry - I really want to 'get' the PIR in Pynchon Gate, but I haven't quite
found the lightbulb.  I feel like I'm close though.

-tom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140324/7ff653c7/attachment.html>