3 ms·
LOL, 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 cent
by zaroth 13y ago
LOL, 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.