tag:blogger.com,1999:blog-3722233.post289797176366667074..comments2021-04-20T09:52:56.297-05:00Comments on Computational Complexity: Crypto problem inspired by politnessLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-15696273480815056572007-12-05T19:18:00.000-06:002007-12-05T19:18:00.000-06:00Andy makes a good point that the output of the pro...Andy makes a good point that the output of the proposed mechanism will by definition reveal statistical information about the input. This sort of thing comes up when studying privacy-preserving data release -- there are some functions that by definition, if you wish to 'usefully' release, you cannot insist on indistinguishability in the typical cryptographic sense. <BR/><BR/>This question is one of the things that distinguishes recent work on privacy preserving data release from classical crypto -- the question not only of how to compute the value of some function without revealing anything other than the output of the function (something like k-anonymity), but also which functions can be computed while preserving privacy, and which cannot. For example, using standard techniques, we could all compute our average salaries without revealing anything other than our average salaries -- but when you leave the room, and we run the computation again, we have all learned <I>your</I> salary.<BR/><BR/>In this case, it seems that 'usefulness' and 'privacy' conflict . Using Andy's formulation, if we hold (x=1, y=1), the event A pays occurs with probability > 0.9, and if (x=0, y=0) it occurs with probability < 0.1. So consider the set of inputs (x=1,y=1), (x=1,y=0), (x=0,y=0). The probability of A paying must jump by at least 0.4 between one of these profiles, and so there will necessarily be a significant 'privacy violation' somewhere.Aaronhttps://www.blogger.com/profile/09952936358739421126noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54178371699493943992007-12-05T16:04:00.000-06:002007-12-05T16:04:00.000-06:00I guess I should note, two RVs *can* be statistica...I guess I should note, two RVs *can* be statistically distant yet computationally indistinguishable; but not if they're 0/1-valued.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52080744503865162892007-12-05T15:59:00.000-06:002007-12-05T15:59:00.000-06:00Here's one view of the limits faced by such a prot...Here's one view of the limits faced by such a protocol. Fix any protocol P(x, y) which respects the consensus with probability, say, .9. <BR/><BR/>Let p be the probability that the protocol outputs 1 when (x, y) = (1, 0). Say p is at most 1/2 (the other case is similar).<BR/><BR/>Suppose I'm A, holding x = 1. Then the two random variables <BR/><BR/>P(1, 0), P(1, 1)<BR/><BR/>have statistical distance at least .4. This means that, e.g., if A is a Bayesian and believes that B is equally likely to hold 0 or 1, then after seeing the protocol output, A can expect to guess B's bit correctly with probability at least .7. This holds regardless of complexity-theoretic assumptions.<BR/><BR/>If anyone's interested, I did a blog tutorial awhile back about the various equivalent notions of statistical distance, used in inferences of the type above:<BR/><BR/>http://andysresearch.blogspot.com/2007/08/another-public-service-announcement.htmlAndy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8208557072957885192007-12-05T15:42:00.000-06:002007-12-05T15:42:00.000-06:00Here's how I would formalize.Let bit x be the even...Here's how I would formalize.<BR/><BR/>Let bit x be the event<BR/><BR/>[A wants to pay full].<BR/><BR/>Let y be the event<BR/><BR/>[B wants A to pay full].<BR/><BR/>A holds x and B holds y. Then they hold a protocol which, as I understand it, is desired to (w.h.p.) output the result 'A pays' (call this '1') when x = 1 and y = 1; <BR/><BR/>to output the result 'split the bill' (call this '0') when x = 0, y = 0;<BR/><BR/>and to behave arbitrarily otherwise.<BR/><BR/>So it seems as though 'zero-knowledge distributed consensus' would be the term of art for this problem.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68039621506009324982007-12-05T15:31:00.000-06:002007-12-05T15:31:00.000-06:00your mother-in-law can't factor or take discrete l...your mother-in-law can't factor or take discrete log? clearly, you must upgrade to a quantum mother-in-lawAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27385974046999279642007-12-05T14:37:00.000-06:002007-12-05T14:37:00.000-06:00if both want the same thing all the time (say spli...if both want the same thing all the time (say split), a protocol has to choose that thing *often*. If on the other hand they want different things the protocol can serve one person not more than half of the time. Therefore no protocol can really work.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45564135111213288722007-12-05T13:45:00.000-06:002007-12-05T13:45:00.000-06:00Better defined:Posy flips: will offer topay the wh...Better defined:<BR/><BR/>Posy flips: will offer to<BR/>pay the whole thing or not<BR/><BR/>IF she offers to pay<BR/>then Margie flips and will<BR/>offer to pay half or not.<BR/><BR/>If Posy does not offer<BR/>then Margie does not<BR/>flip, and they each pay<BR/>half.<BR/><BR/>If Posy offers and Margie<BR/>does not, then Posy pays<BR/>for it all.<BR/><BR/>If Posy offers and Margie<BR/>offers, they split.<BR/><BR/>(With this my estimate<BR/>of 1/8 may be wrong).<BR/><BR/>MANY variants are possible- and some may<BR/>be interesting.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72248358207183226112007-12-05T13:30:00.000-06:002007-12-05T13:30:00.000-06:00The question does not seem well defined. If Posy o...The question does not seem well defined. If Posy offers and Margie accepts, them Posy pays for everything. If Margie offers and Posy accepts then they each pay half. But what is supposed to happen if they both offer? What is supposed to happen if they both accept (and neither offers)?Anonymousnoreply@blogger.com