Q:

Shared distrustful random number generation

Alice and Bob are stingy, honorable, but also distrustful. They live far away from each other. They both know that they are the only two people who wants to buy an item in an upcoming auction. If only one of them places a qualifying bid, that person will get the item at the minimum price. They agree in a chat that if they can figure out a fair and simple way for them to decide which of them gets to place the bid, they will both honor the result. However, they are distrustful enough so that it is not good enough to decide this by having one of them flip a coin.
TL;DR, how can two people in a chat generate a random bit and be sure that the outcome is not affected by their individual preferences?

A:

One standard trick is to work with two distinct primes $p,q$ of length $N$ where $N$ is chosen so that computers can work well with numbers of length $N$ but not with numbers of length $2N$.  To clarify:  $N$ needs to be small enough so that $A$ can readily produce primes of length $N$ and can extract square roots of quadratic residues modulo such primes, but it should be large enough so that $B$ can not factor general numbers of length $2N$. (thanks to @TonyK for correctly suggesting that clarification was needed here).
If $A$ has two such primes she can hand their product, $n=pq$, to $B$ who can not then recover $p,q$.  $B$ then takes $m\pmod n$ and computes $m^2\pmod n$, which he then hands to $A$ (to be clear, he hands the residue class of $m^2$, not $m$).  
Now, since $A$ knows $p,q$ she can find the square root of $m^2$ modulo both $p,q$.  Alas, that gives rise to four possible values, let's call them $\pm m, \pm k$.  She guesses which one $B$ started with and hands that back.  If she is right, she wins.  If she is wrong, $B$ can now factor $n$ and thereby prove that $A$ was wrong, and then $B$ wins.
It's a minor exercise to prove that $B$ can factor $n$ given the four square roots (note that $\gcd(n,m+k)=p$ or $q$ and $B$ can now use the Euclidean Algorithm to find one of the primes).
Note: one drawback to this method is that $B$ can "cheat" in that he can pretend to lose.  That is, he can say that $A$ guessed right even if she didn't.  This flaw doesn't appear to signify much in your instance (usually it is safe to assume that both parties are actually trying to win).

