show/hide this revision's text 3 added 114 characters in body

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

    Post Undeleted by Aaron
show/hide this revision's text 2 added 155 characters in body; deleted 123 characters in body

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 envelopesan envelope and you believe in one-way functions, you can have everyone encrypt their bit, release the encrypted use a bit , and later reveal the key.commitment scheme: http://en.wikipedia.org/wiki/Commitment_scheme

    Post Deleted by Aaron
show/hide this revision's text 1