7
$\begingroup$

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).

|improve this question
$\endgroup$

migrated from puzzling.meta.stackexchange.com Sep 9 '18 at 18:59

This question came from our discussion, support, and feature requests site for those who create, solve, and study puzzles.

  • $\begingroup$ Wasn't sure where to ask this question - apologies if off topic $\endgroup$ – Shuri2060 Sep 9 '18 at 13:28
  • 1
    $\begingroup$ this is not puzzle, though you can stream your screen and random.org/coins $\endgroup$ – Oray Sep 9 '18 at 13:30
  • $\begingroup$ I'm not too keen on streaming solutions - they can be faked. I could claim some connection error occurred and redo tosses if I relied on the timestamp feature, too. I'm thinking about this problem in terms of information exchange, which is why I thought it might be a puzzle. Like is there no way to completely convince someone else I've done a fair coin toss through non-time reliant means? $\endgroup$ – Shuri2060 Sep 9 '18 at 13:38
  • 5
    $\begingroup$ Whoever voted to put this on meta - this is definitely a puzzle, not a question about the site. So that is wrong. Whoever VTC'd as unclear what you're asking - the question is pretty clear. $\endgroup$ – Quintec Sep 9 '18 at 14:34
  • $\begingroup$ Edited to the question, hope it makes things clearer $\endgroup$ – Shuri2060 Sep 10 '18 at 11:45
10
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Thanks - that's a great answer! I haven't mentioned it in the question, but there is a possibility of players colluding (in the extreme case, let's say they all do so against me). I see 1/2 works around this, but can 3/4 be adjusted to work around this? $\endgroup$ – Shuri2060 Sep 9 '18 at 21:28
  • 1
    $\begingroup$ @Shuri2060 If you want to avoid collusions, please state so in your question, not to one specific answerer. It would be nice to also give details on the kind of collusion you are fearing: scenarios 3/4 would need adjustment if all players collude (against you then) but in that case you are probably doomed, whatever the initial toss (what outcome do you expect when all players in your tournament are colluding? -- This might make a good puzzle, though). $\endgroup$ – xhienne Sep 9 '18 at 22:38
  • $\begingroup$ Method 3 is no more secure than trusting a third party to flip a coin but adds lots of complication. If the person collecting the numbers from the crowd (controlling the sever collecting the numbers) can add one or more faked entries that they control after seeing all the other entries that were submitted; they can try several variations of the final entry, see the seeds and PRNG stream with that seed, and choose the one most advantageous to them. Methods 2 (e.g., based on hash of date + observable data like tomorrow's Dow close) and 4 are solid though. $\endgroup$ – dr jimbob Sep 9 '18 at 23:12
  • $\begingroup$ @drjimbob, agreed, 3 isn't safe from collusion. The person collecting the seeds doesn't get to add his own, so it's safe from straightforward cheating though, which is what the question asks for. $\endgroup$ – Bass Sep 10 '18 at 9:33
  • $\begingroup$ @Shuri2060, even if everyone else is colluding against you, 4 is safe, because you (as one of the players) get to add your permutation too. I don't think 3 can be salvaged if there is any chance of collusion; looks like you'd have to add a commitment scheme there, which essentially turns it into option 4. $\endgroup$ – Bass Sep 10 '18 at 9:35
6
$\begingroup$

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.)

|improve this answer
$\endgroup$
2
$\begingroup$

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

|improve this answer
$\endgroup$
1
$\begingroup$

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.

|improve this answer
$\endgroup$
1
$\begingroup$

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.

|improve this answer
$\endgroup$
0
$\begingroup$

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.
|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.