3 ms·
Basic protocol: 1) Put signatures of your elements into a bloom filter, rather than the elements themselves. 2) Send the client the entire bloom filter. 3) A
by moxie 13y ago
Basic protocol:
1) Put signatures of your elements into a bloom filter, rather than the elements themselves.
2) Send the client the entire bloom filter.
3) Allow clients to request blind signatures for the elements they'd like to query locally.
So unfortunately, like most solutions in the "private information retrieval" domain, step one is "send the client your entire data set." They've explained that cryptographically secure bloom filters are superior to secure set intersection protocols (which are also largely unusable, although for different reasons) for cases where the data set is so large that the server would like to avail itself of the space savings that a bloom filter provides.
So at set sizes that large (say, 7 billion elements), step one is unfortunately to send the client a 700MB file. Not to mention that step zero was for the server to have calculated 7 billion digital signatures. It's otherwise a pretty neat idea, though.
- zaroth 13y agoLOL, too true! And even 700MB may be a bit stingy for a 7b element bloom filter. Are there any options out there for privately testing set membership on a central server where client-server message size is constant? I can see how any type of private querying would necessarily involve putting the data somewhere the client can access it, where the server can't observe the access patterns. (EDIT) Or making the server look at all the data to service a single request. So one option is handing the client an access-controlled data set, so you know WHO is accessing the data, but not WHAT they are accessing. I guess the other option is trying to hide who the client is, perhaps via onion routing, so you know WHAT data is being accessed, but not necessarily WHO is accessing it. Maybe a third way would be to use leaky selectors -- queries that return the desired data, plus a bunch more, so the server doesn't know exactly what piece of data was being targeted. They reference a "Keyword Search and Oblivious Pseudorandom Functions" paper (http://www.cs.princeton.edu/~mfreed/docs/FIPR05-ks.pdf http://www.cs.princeton.edu/~mfreed/docs/FIPR05-ks.pdf) which looks like their inspiration, which is a privacy maintaining Key-Value store "with a communication overhead of O(polylog n) and a computation overhead of O(log n) public-key operations for the client and O(n) for the server." I'll have to read some more about that one.
- zaroth 13y agoSo I was reading this (http://crypto.stanford.edu/~dabo/courses/cs355_fall07/pir.pdf http://crypto.stanford.edu/~dabo/courses/cs355_fall07/pir.pd...) survey on PIR - private information retrieval - and I saw this gem: "To limit the survey the following topics are omitted ... 4. Attempts to make PIR practical [4, 45] in the real-real world." Oh well... but then I found this, which looks like it will be HIGHLY informative: http://uwspace.uwaterloo.ca/bitstream/10012/6142/1/Olumofin_Femi.pdf http://uwspace.uwaterloo.ca/bitstream/10012/6142/1/Olumofin_...