Honest Majority unconditional coinflipping without private channels

Question

All communication is assumed to be by the parties
taking turns making authenticated broadcasts.

Is there a way for $n$ parties, each with access to ideal local randomness, to jointly
choose a member of {0,1} randomly with a distribution that is close to uniform
even when a small subset of the parties are controlled by a computationally
unbounded adversary who wants to make that distribution far from uniform?

Regardless of what $n$ is or what "a small subset" means,
the best I've been able to come up with is:

k = parameter
for i in range(k):
 each party outputs a random bit
 if number_of_zeros_outputted < number_of_ones_outputted:
  return 1
 if number_of_ones_outputted < number_of_zeros_outputted:
  return 0
return 0

Answer 1

What you are describing is called the common coin problem and has been introduced in [1]. One way to do this is to elect a leader and then let that leader flip a coin, for example, by using the lightest bin protocol[2].

Intuitively speaking, this works as follows:
We have $n$ processes (=parties) and choose $m=n/\log n$ bins.

1. In every round, every participating process chooses one of these $m$ bins uniformly at random and broadcasts this choice.
2. The bad processes get to choose after observing the choices of the good processes.
3. So at the end of a round every process knows exactly which process chose which bin. All processes that chose the lightest bin (i.e. the one with the fewest members) continue to the next round, while all others stop participating.

The trick is to keep the initial ratio of good processes to bad processes. How can the adversary try to prevent this? Clearly, the adversary's strategy is to make many bad processes survive until the next round, i.e., many bad processes are in the lightest bin. But since the good processes will be distributed almost uniformly among the bins, the adversary cannot place too many bad processes into the lightest bin, otherwise it will no longer be the lightest! (Once you have reached a constant number of participants you switch to $m=2$ bins.)

This protocol elects a good process as the leader with constant probability as long as a majority of processes is good, i.e., you will get an unbiased common coin with constant probability.

[1]: M. Ben-Or and N. Linial. “Collective coin flipping”. In Advances in Computing Research, S. Micali, ed., vol. 5: Randomness and Computation, JAI Press, Greenwich, CT, 1989, 91–115.

[2] Uriel Feige: Noncryptographic Selection Protocols. FOCS 1999: 142-153