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