24 ms·

Just to make this technique a bit clearer, since "subtract 50 and double" was a bit vague to me: you ask 100 people the question about illegal activity, and ass

Just to make this technique a bit clearer, since "subtract 50 and double" was a bit vague to me: you ask 100 people the question about illegal activity, and assume they're going to toss the coin and follow the protocol. That gives you 100 "yes" and "no" answers, of which ~50 "yes" answers are due to following the protocol and can just be ignored. The remaining yes/no answers are from the tails results and that's the data you use to get a final answer. As an illegal opiate producer in Afghanistan who answers "yes", you have plausible deniability by just saying "I got heads." The fairness of the coin toss means the researcher asking the question doesn't need to know who got which coin result so it can be kept secret.

SpikeGronim 15y ago
This is a cool concept that is formalized in the "Dining Cryptographers" paper: http://en.wikipedia.org/wiki/Dining_cryptographers_problem http://en.wikipedia.org/wiki/Dining_cryptographers_problem . You can use this basic idea to create a completely anonymous broadcast channel.
noja 15y ago
Isn't the very key to this that the researcher doesn't see the coin result?
- joeyo 15y ago
  That's correct. The researcher doesn't know the outcome of any particular coin toss but knows the outcome, in expectation, for a large number of coin tosses.
- Terretta 15y ago
  The explanation was missing a crucial point: http://news.ycombinator.com/item?id=3810854 http://news.ycombinator.com/item?id=3810854
grabastic 15y ago
Thanks for the explanation... I didnt quite get the trick as it was described in the parent.
tagawa 15y ago
Thanks for the further explanation. I love it when HN throws up gems like this.
Terretta 15y ago
You explained the subtract 50, but not really the and double. Revised: "You ask 100 people the question about illegal activity, and explain they're going to toss the coin and follow the protocol. That gives you 100 "yes" and "no" answers, of which ~50 "yes" answers are yes due to the coin being heads, regardless of whether true yes or false positive, so subtract those yesses out. The remaining yes answers are from the tails results and are not false positives. Because heads/tails is 50% chance, half of your true yesses were on tails, and half on heads. To get back the "hidden" half of yesses you tossed out with the 50 heads results, you double the yesses that came up with tails. That's the data you use to get a final answer."
- aprescott 15y ago
  I figured it would be obvious enough from what I outlined that the yes/no answers from the tails results gives you a proportion of "yes" answers, such as, say, 20/50, which is the proportion you want. The doubling is just 20/50 = 20*2/100. But I can appreciate that maybe someone else doesn't quite see it! :)

SpikeGronim 15y ago

This is a cool concept that is formalized in the "Dining Cryptographers" paper: http://en.wikipedia.org/wiki/Dining_cryptographers_problem http://en.wikipedia.org/wiki/Dining_cryptographers_problem . You can use this basic idea to create a completely anonymous broadcast channel.

noja 15y ago

Isn't the very key to this that the researcher doesn't see the coin result?

joeyo 15y ago
That's correct. The researcher doesn't know the outcome of any particular coin toss but knows the outcome, in expectation, for a large number of coin tosses.
Terretta 15y ago
The explanation was missing a crucial point: http://news.ycombinator.com/item?id=3810854 http://news.ycombinator.com/item?id=3810854

grabastic 15y ago

Thanks for the explanation... I didnt quite get the trick as it was described in the parent.

tagawa 15y ago

Thanks for the further explanation. I love it when HN throws up gems like this.

Terretta 15y ago

You explained the subtract 50, but not really the and double. Revised: "You ask 100 people the question about illegal activity, and explain they're going to toss the coin and follow the protocol. That gives you 100 "yes" and "no" answers, of which ~50 "yes" answers are yes due to the coin being heads, regardless of whether true yes or false positive, so subtract those yesses out. The remaining yes answers are from the tails results and are not false positives. Because heads/tails is 50% chance, half of your true yesses were on tails, and half on heads. To get back the "hidden" half of yesses you tossed out with the 50 heads results, you double the yesses that came up with tails. That's the data you use to get a final answer."

aprescott 15y ago
I figured it would be obvious enough from what I outlined that the yes/no answers from the tails results gives you a proportion of "yes" answers, such as, say, 20/50, which is the proportion you want. The doubling is just 20/50 = 20*2/100. But I can appreciate that maybe someone else doesn't quite see it! :)