My previous post on PIR generated some interesting comments on the practicality of such schemes and why Google isn't already doing it. An angle to this that I should have mentioned earlier is the way that PIR-like methods can actually help government snoopers.
David Molnar had pointed to this a while back: it's a paper by Ostrovsky and Skeith from CRYPTO 2005 titled 'Private Searching on Streaming Data'. The premise is that you are the NSA or some other intelligence organization, and you want to run searches on various data streams without any adversary being able to detect what your searches are about (presumably so that they can't game the system to avoid detection). This of course is the same as the PIR paradigm, except with the "good guys" and "bad guys" flipped around.
Thanks for the link. Incidentally, it looks like you could combine the Ostrovsky-Skeith result with streaming reductions to obtain private versions of a number of other streaming problems. It's not clear to me if this is useful or not or known or not, so I've had trouble setting aside time to hack on it...
ReplyDeletePosted by David Molnar
If it involves some new technique, I'd say it's very interesting. If the reductions are standard stream reductions, then it would still be interesting methinks. Have you seen the so-called W-stream model from this year's SODA ? it's a different way of looking at multipass streaming and might be of use to build a "network" of private stream operators.
ReplyDeletePosted by Suresh
I have not seen the W-stream model. Thanks for the pointer! I'll take a look and let you know what I think.
ReplyDeleteOne of the key questions, I suppose, in both the standard streaming reductions case and the W-stream model is whether "reduction preserves privacy." That is, if I take a streaming reduction from problem A to streaming keyword search, then I plug in the Ostrovsky-Skeith contruction for streaming search, do I automatically get a private protocol for problem A?
My gut feeling is that the answer should be yes. We should be able to incorporate the streaming reduction into a new security reduction showing that if there exists an adversary that breaks the privacy of the "reduction+private keyword search" protocol for problem A, then we can create a new adversary that breaks the privacy of the Ostrovksy-Skeith protocol. That, of course, yields a contradiction. The devil is always in the details, especially when dealing with cryptographic definitions.
Still, suppose that one could prove such a theorem. Because the result is what we "expect" with no new techniques, the theorem itself is not of so much interest on its own. It only becomes interesting if it gives us either a) efficient new constructions for problems that didn't previously have private streaming algorithms. Note this is one of the motivations for the paper that introduced streaming reductions - they use them to create a new algorithm for counting triangles in graphs.
Then b) if we can find some interesting problems that _don't_ have streaming reductions to keyword search and so will require some new techniques. I guess there's also c) comparing direct private algorithms for a problem to reduction+keyword search algorithms. Without a better feel for what problems might fall into these classes, it's hard for me to have a feel for the impact of doing the work. Still, sounds like it might be worth a second look. :)
Posted by David Molnar
This is true. The right choice of problem is crucial here. I think what would make a general reduction interesting is also if maybe some privacy problem can be solved on stream data MORE efficiently than before: again, it's tricky to define these notions as you point out.
ReplyDeleteI guess the only way is to explore it and see :) At least I can say that I'd be interested in reading such a paper.
Posted by Suresh