<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On 24 March 2014 02:48, Brian Warner <span dir="ltr"><<a href="mailto:warner@lothar.com" target="_blank">warner@lothar.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


A recipient figures out which slots they're interested in for a given<br>
day's dataset (both H(nym+date) and a handful following it), then for<br>
each slot, they compute some number of million-bit vectors, one for each<br>
distributor they're going to use. (you must use at least two, and the<br>
unlinkability holds if at least one of the distributors you use does not<br>
collude with the rest). All but the last vector is randomly generated.<br>
The final vector is created by XORing all the other strings together,<br>
and then flipping the bit of the one slot you're interested in. The<br>
recipient sends one vector to each distributor.<br>
<br>
The distributor computes the XOR of all slots that have a 1-bit in the<br>
vector, and returns the result (equal in size to a single slot, e.g.<br>
1kB). The recipient XORs together all of the results to get just the<br>
desired slot contents, since everything else XORs into zeros.<br><br></blockquote><div>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. </div>


<div><br></div><div>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...</div><div><br></div><div>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....</div>


<div><br></div><div>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...</div>


<div><br></div><div>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.</div><div><br></div><div>-tom</div></div><br></div></div>