Untrustworthy people picking a random number

Inspired by the party game Mafia, in particular those situations where nobody is clearly innocent or guilty and the group wants to decide on someone random to eliminate.

Suppose n people each have their own personal random number generator (a machine which generates a 0 or 1 at the push of a button, each with equal likelihood), that these random number generators (henceforth RNGs) operate independently from each other, and, most critically, that each RNG can only be read by its owner. They would like to, as a group, decide on one of two courses of action, and they'd like to do so randomly with 50% probability for each choice.

But, a complication: some members of this group are secretly saboteurs, and they have their own preferences for which of the two options to pick. They'll do anything in their power to sway the decision in a particular direction. On the other hand, the non-saboteurs all have one goal in mind: to make this decision process truly unbiased, to wrench the control from those saboteurs. Nobody knows who the saboteurs are (but let's say there aren't very many of them), and nobody knows which of the two options they're trying to sway things towards.

Is there a strategy the group can employ to remove all bias from the selection process? All anyone can do is talk, push the button on his or her own RNG, and tell the results to the others (though they might not believe it).

EDIT: As a further clarification, the players can't all talk at once. So it's not enough to for everyone to pick a number and sum them mod 2, since the last person to give the number might be a saboteur.

-
Clearly it doesn't matter that I made the RNGs binary and had two options for the decision; if your answer is easier to explain with some different number of choices, by all means change it up. – Jonah Ostroff Aug 12 '10 at 18:58
If you want a uniform random integer in [0,K), ask everyone to provide an integer. Add them up and take modulus K. This result will be uniformly random as long as one of the inputs is uniformly random. – Tom Sirgedas Aug 12 '10 at 19:06
I think this (everyone chooses an interger and mod K) does not work, since the last person to tell the number could be the saboteur... – Daniel Krenn Aug 12 '10 at 19:10
See Bruce Schneier's Applied Cryptography, which discusses this very problem, and describes the solution mentioned by others below. – Nate Eldredge Aug 12 '10 at 19:32
One thing I find interesting is that the traditional "I flip a coin, you call it in the air" implements this solution for 2 players: if I use a fair coin, you can't cheat me with your choice of call; and if you choose your call randomly, I can't cheat you by using a biased coin. Interestingly, the NFL's coin flip procedure fails in this regard, because the visiting captain calls as the referee flips; the home captain has no way to ensure that the others are not colluding to cheat him. – Nate Eldredge Aug 12 '10 at 19:54

The group agrees on a strong hash function H. Each person in sequence generates a number x and reveals H(x). Then each person in sequence reveals x. If all hashes can be verified, then the first bit of sum(x) mod 1 is used.

-
You beat me to posting this. Note that this implements Aaron Roth's "sealed envelope", and it also addresses Charles' objection: the last player to reveal $H(x)$ certainly determines the outcome by doing so. However, she doesn't know which way she is determining it! – Nate Eldredge Aug 12 '10 at 19:29
I'm still concerned because asking them to agree on H may be just as hard as asking them to choose a random bit. – Dan Brumleve Aug 12 '10 at 19:32
Since there are a small number of saboteurs, perhaps they can put it to a majority vote? – Dan Brumleve Aug 12 '10 at 19:34
Seems like some of the answers here were really about different questions, but I like this one best. – Jonah Ostroff Aug 12 '10 at 20:25
Aw shoot, you guys! The last player to reveal x has heard all the other values of x and knows if the hashes for them can be verified. If he doesn't like the resulting answer that would result if he were to reveal his x, he can just give a bad value of x and make them start the process over (since it won't match his H(x)). Sure, they'll know he's a saboteur and exclude him the second time around, but it still gives the last player a one-time-only veto power over the decision, which is enough bias to invalidate this strategy. So, now what? – Jonah Ostroff Aug 14 '10 at 17:41

What Tom said. Have everyone place their bit into a sealed envelope, open them all up, and take the parity of the bits. (Determine if the sum of the bits is even or odd). So long as at least one of the bits was random, the resulting parity will be random. To see this, imagine it is known that person 1 is honest, but it is unknown whether everyone else is. Imagine that everyone else flips their bits first. This fixes a parity on the other bits, and person 1's bit now (at random) uniquely determines the parity of their sum.

Note: Its important that everyone first place their bits into sealed envelopes before any of them are read, to prevent a dishonest party from specifically choosing their bit at the end to manipulate the sum.

If you don't have an envelope and you believe in one-way functions, you can use a bit commitment scheme: http://en.wikipedia.org/wiki/Commitment_scheme

Edit: Check out this classic paper, "Coin Flipping by Telephone" http://portal.acm.org/citation.cfm?id=1008911

-
Fine, but I never gave you an envelope. – Jonah Ostroff Aug 12 '10 at 19:13
And how do they reveal their keys, if not in turn? Again the last person can be sneaky. – Jonah Ostroff Aug 12 '10 at 19:16
Edit: What is needed is a "bit commitment" mechanism, which exist contingent on one-way permutations existing – Aaron Aug 12 '10 at 19:22
I don't have enough reputation points to comment on other answers, but a key distinction to make is whether the parties participating in the protocol can perform unbounded computations or not. If they can only perform polynomial time computations, then bit commitment mechanisms exist (probably), and you can do what you want. If they can perform arbitrary computations, then it shouldn't be possible, as observed below. – Aaron Aug 12 '10 at 19:35

If the final outcome doesn't need to be perfectly unbiased, but instead may have a bias of up to say 10 percent, then there are good algorithms, even if the people have unlimited computational power (which renders cryptographic methods ineffective). For example, the following baton-passing algorithm works well. At the start, give the baton to an arbitrary person (say the first person). At each step, the current baton-holder gives the baton to a random person who has not yet held the baton. Whoever receives the baton last gets to make the collective coin flip.

If the number of saboteurs is fewer than $n / \log n$, then this algorithm is known to produce a low-biased coin. Mike Saks proposed and analyzed this algorithm, and Miki Ajtai and Nati Linial refined the analysis. Here are the references:

M. Saks (1989), A robust non-cryptographic protocol for collective coin flipping, SIAM Journal on Discrete Mathematics 2, pages 240-244.

M. Ajtai and N. Linial (1993), The influence of large coalitions, Combinatorica 13, pages 129-145.

You can find a scanned copy of the Ajtai-Linial paper at Linial's homepage: http://www.cs.huji.ac.il/~nati/.

Babu Narayanan and I showed that there exists an algorithm that can handle up to 49 percent of the players being saboteurs and yet still produces a low-biased coin. Here is the reference:

R. Boppana and B. Narayanan (2000), Perfect-Information Leader Election with Optimal Resilience, SIAM Journal on Computing 29:4, pages 1304-1320.

-

Suppose that there is a process for solving the problem that involves each of $k$ players (possibly including repetition) showing a number, these numbers being combined in a predetermined deterministic fashion. Either the last player can modify the outcome, or the last player can't. In the latter case, look at player $k-1$ and so on; either you eventually get to a player who can alter the outcome or there is no such player. If there is no such player, the outcome is constant. If there is such a player, and that player is a saboteur, then the outcome can be rigged.

So unless the players can determine who are saboteurs, there is no such process.

-
I like where this proof is headed. Not sure it's there yet, though: what if the number of players who show a number depends on what those numbers are, e.g. the process stops after some particular pattern is revealed. Then the last player can only "modify the outcome" in that he gives more players (who perhaps aren't saboteurs) the opportunity to do so. – Jonah Ostroff Aug 12 '10 at 19:28
Ah, but that's not such a big deal: even if a saboteur can't certainly change the outcome in that case, he or she still gets to veto an undesired outcome, so the bias is there. Great. – Jonah Ostroff Aug 12 '10 at 19:30
(Someone else back me up on this before I give the check, huh? I'm shaky on these sorts of proofs.) – Jonah Ostroff Aug 12 '10 at 19:30
Of course this only shows the boundaries of what's possible in terms of information-theoretic security. If the parties have only limited computational power and one-way functions exist then there is a solution, as shown by jdb19937; if players can reveal information to each other and there are enough truthful players there's also probably a solution. – Charles Aug 13 '10 at 3:39

In this article it is shown how to select a bit string of length $n$ with entropy close to $n$ by two parties. One party could be adversary. More precisely, it is possible to design a protocol that produces a string of entropy $n - O(1)$ in $4 \log^* n$ rounds.

-

Go to each player in turn and learn what their number is. It is OK if the other players hear. Use your own RNG to decide whether you 'AND' or 'OR' the players bit with the 'group bit' you have thus far. Because no player knows how their bit will be interpreted, they lose any power over the outcome.

-
What if the person collecting all these bits is the saboteur? – Jonah Ostroff Aug 15 '10 at 20:13