I found this question on the game programming site and was intrigued. I came up with an answer off the top of my head but I'm no cryptanalyst so it is probably not water-tight.
This is how my idea goes:
- each of the two peers generates a random number.
- each peer creates a salted hash of its number and sends it to the other peer.
- once both peers confirm reception of each other's hashes, each then sends the other its actual random number.
- each peer verifies that the hash sent by the other is actually a hash of the random number.
the result of the coin flip is the XOR of the least significant bit of each number, i.e.
(a & 1) ^ (b & 1)
So would it work? If not, how could it be made secure? Is there some conventional method for solving problems like this one?
The rules are, there are two untrusted parties with no intermediary. Assume the channel of communication is secure. Neither party must be able to unfairly win or lose.