On 3/24/14, Tom Ritter <[email protected]> wrote: > On 24 March 2014 02:48, Brian Warner <[email protected]> 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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
