Flipping a coin across the internet

Question

Suppose you wish to "flip a coin across the internet". ie. You want to show other people that you've flipped just ONE coin, and show them the result.

I'm currently trying to think of the simplest solution to this and can't come up with/find anything.

---

The actual problem I'd be applying this to would be generating tournament pairings (which I'm a part of). I'd want everyone to be convinced that the pairings are random and I haven't fixed them in any way.

---

Clarification/Formalization of problem:

1. There are N people who are in different parts of the world. They are able to communicate with each other and they wish to observe the result of a fair coin toss, but none of them can trust any of the others.
   
   Is there a method which can be used so that everyone can be satisfied that the toss was fair?
   
   
2. Consider the same problem, but instead of a coin toss, they wish to select a permutation from 1 to N randomly (with an equal chance for each permutation).
   
   

In both problems, consider the possibility of collusion (even extreme cases like N-1 people collude against one).

Answer 1

A couple of possibilities come to mind:

1: A trusted third party. Have someone else toss the coin.

2: "Geohashing" type approach: toss the coin by unpredictable means that everyone can independently observe, even over the internet.

3: Crowd-seeded pseudorandom number generator: have each participant send you a number. Add them up, and seed a PRNG with the result. The results are reproducible, and therefore checkable. You don't get to add your own seed, because the point of the procedure is that you have no control over the seeding. This scheme isn't safe from collusion though (you could, in theory, bribe someone to add a specific seed after seeing all the other seeds), so this isn't very secure in that aspect.

4: Cryptographic commitment (the coolest one, in my opinion):

Have the tournament bracket prepared, but with placeholders ("Player 1" to "Player N") instead of names. Also, make a list of the N participants.

Then, each participant secretly writes down a permutation of numbers 1 to N. (eg. "3,6,1,5,2,4"), and publishes a secure hash of it.

(Creating a secure hash of a known format, low entropy message can get a bit tricky, and will probably involve everyone adding a nonce to avoid brute force attacks, and it's probably a good idea to add a checksum too, to avoid collision attacks. But these are all implementation details.)

Then, once everyone has published their hashes, reveal each permutation, check that all hashes match, and apply all permutations, one after another, to the list of player names. Use the resulting list to fill the tournament bracket.

This way, there can be no collusion at all, since every player gets to make a decision that could change any pairing to any other pairing, and no-one had access to all the other players' information before they committed to their choice.

Answer 2

Agree on a future public event that all parties can observe, and a means to generate a bitstream from it. Perhaps the parity of the last digit of the Dow Jones Industrial Average at a predetermined set of times? (I was going to suggest daily high temperatures from a given source for a list of N cities, but you'd probably end up with much higher correlation with that set.)

Answer 3

Someone could just make an online coin flipping website where you flip coins live with an opponent.

Answer 4

This is known as "mental poker". https://en.wikipedia.org/wiki/Mental_poker . If you have an encryption algorithm that commutes with permutations (the permutation of an encryption is equal to the encryption of the permutation), then you can simply have the first player choose a permutation, apply their decryption key it, send it to the next player, that player permutes the result and applies their decryption key it, and so on. Then all of the players' encryption keys are applied (with public key encryption, the encryption keys can be declared before the permutation is chosen). You'll probably have to add salt to avoid brute force attacks.

Another way is for everyone to choose a permutation, apply their decryption key (again, probably with some salt), and then publish the result. Then everyone says what their permutation and salt was, the players can apply the encryption keys to check that this gives the result that was published earlier. Once the permutations are verified, they can be combined into one permutation.

Answer 5

There is a video on the Numberphile YouTube channel called "Dealing Cards with Cryptography" which I believe may have similar concept to what you're asking, with reduced variables.

Answer 6

You get them to contribute.

Rules:

1. Everyone that wants to be included privately emails you a 64 character long string.
2. You take the MD5 hash of each string.
3. Append the MD5 hashes in alphanumeric order.
4. Take the resulting MD5 hash of that result.
5. If the first digit appearing in that final output is even, we picked "Heads". Otherwise, we picked "Tails".
6. Publish all submitted strings, submitter and timestamp at the end to prove there was no foul play.