tag:blogger.com,1999:blog-6555947.post113859839386560719..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: PIR and turning the tables on the NSASuresh Venkatasubramaniannoreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6555947.post-1138762697536170032006-01-31T19:58:00.000-07:002006-01-31T19:58:00.000-07:00This is true. The right choice of problem is cruci...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. <BR/><BR/>I 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. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshSureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1138757851403083092006-01-31T18:37:00.000-07:002006-01-31T18:37:00.000-07:00I have not seen the W-stream model. Thanks for the...I have not seen the W-stream model. Thanks for the pointer! I'll take a look and let you know what I think.<BR/><BR/>One 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? <BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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. :) <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>David MolnarDavid Molnarnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1138626877341979132006-01-30T06:14:00.000-07:002006-01-30T06:14:00.000-07:00If it involves some new technique, I'd say it's ve...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 <A HREF="http://www.dis.uniroma1.it/%7Eae/?file=paper-abstract&type=conference&id=202" REL="nofollow">so-called W-stream model</A>  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. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshSureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1138613148165904352006-01-30T02:25:00.000-07:002006-01-30T02:25:00.000-07:00Thanks for the link. Incidentally, it looks like y...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... <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>David MolnarDavid Molnarnoreply@blogger.com