2 ms·
Agreeing a coin toss remotely
I've just had reason to use this, so I thought I'd share it here. You can find similar stuff, and generalisations, all over the web, but I've put it here so you can read and discard, or read and research, as you choose.
Suppose you and I need to toss a coin, but we're separated physically and can only communicate by phone or email. How can we do that?
Obviously I can toss, you can call, and I can tell you whether you win or lose, but you might not trust me. How can we add some verification?
Simple. I toss the coin and write the sentence "HEADwibblewibblerandomrandomXX$&*HmmWhat?" into a file, where the random stuff is actually random. I then compute a hash such as sha-256 or similar, and send that to you.
Now you call heads or tails, and tell me. If you win then there's unlikely to be an argument, but if you lose I can "prove" it by sending you the original sentence for you to hash and compare.
So there you are, remote coin tossing. Sadly, I can't tell you why I needed it, but it was rather useful.
- evgen 17y agoBit commitment is a core concept in crypto -- this is also a piss-poor commitment protocol. After I flip the coin and say tails you can claim to have "won" and when I dispute the result you just pull out a sentence that has TAIL at the front and claim that this is what you sent to me. How can either party prove the claim? If you build a good bit commitment scheme you can get by with a very small number of message exchanges and still have both parties accept the results. Start with the wikipedia entry for bit commitment, read Blum's coin flipping over the telephone paper and work your way up to zero knowledge protocols...
- RiderOfGiraffes 17y agoI appreciate you taking the time to reply, but I'm not sure I understand you. You seem to be claiming that what I've outlined has a flaw, but I don't understand your objection. I don't just pull out any sentence with (for example) "tail" at the front, I have to find one that has the hash I sent you. Could you expand a little further as to why the scheme I've described doesn't work? Thanks.
- devicenull 17y agoHow does that verify anything? You still flipped the coin, then wrote the sentence. The two do not have to be related (say you flip the coin and get heads, then write tails, what happens then?).
- RiderOfGiraffes 17y agoEr, yes, but they call. It doesn't matter if I choose whatever I like, then send the hash. The other person then has a free choice, and they are right or wrong. The coin is effectively irrelevant. Imagine we're together and I pretend to toss the coin. I decide what I want it to be, place it as that, and then hold it in my hand. Provided I'm not allowed to change my mind, this is just as fair as actually tossing the coin because you are free to call and are right or wrong with equal probability. The point about the real coin is that it prevents me from changing my mind. The point about the hash is it prevents me from changing my mind. In effect, the hash is the coin. I am free to decide heads or tails as I wish - I just need to be prevented from changing my mind after you call.
- dgreensp 17y agoSounds like it works to me, except that the lack of the actual coin flip introduces an interesting psychological element -- it's kind of like rock-paper-scissors. Two people say "heads" or "tails", and person A wins if they are the same, else B. You can be thinking things like "he usually says 'heads', but maybe he'll try to psyche me out..."
- RiderOfGiraffes 17y agoThat's why person A should actually flip the coin. People are really bad at choosing "randomly."
- evgen 17y agoI think we have a difference in threat models. It sounds like you are dealing with a non-adversarial model in which neither party has much of an incentive to cheat. If this is the case then your system works fine. If either party gains much by cheating then your system is insufficient to solve the problem.
- qbunny 17y agoAs said above, this is well known in crypto circles. There's even a quantum coin flipping protocol to address the possible future case where these sorts of factoring-based bit commitment schemes are insecure. (see the seminal BB84 quantum cryptography paper or a recent experimental demonstration of a "fair" quantum coin flipping protocol by F. Bussieres.)
- RiderOfGiraffes 17y agoTwo observations: evgen above seems to think it's wrong, and yet you seem to be saying it's right (implicitly, because it's "well known in crypto circles.") So, is it right or wrong? Obviously I believe it to be right ... Secondly, I know that it's well known in crypto circles. I read about it, refined it (I hope without breaking it as evgen suggests but does not prove) and reproduce it here because it does not seem to be well known outside of them. I find that this is about the most accessible non-obvious result, and yet it rarely seems to be described in simple, clear terms. I've tried to do so here, but if you know of a better, clearer explanation I'd genuinely appreciate the pointer. Thanks. (small edits for clarity)
- stephen_cagle 17y agoNear as I can tell (no expert mind you) it seems right. Given that SHA is secure (cannot calculate a plaintext that will result in the same SHA result) then only the original text could have reasonably generated it. Sending the SHA result to your friend does not help him in determining your original plaintext. Only with random text can he determine the plaintext that generated the SHA result. Seems good enough.