[JacobEdelman]

Bonus points: What if only one of them gets a coin to flip and then they must both come to an agreement on what the result was. They can talk but the NSA overhears everything they say and can crack every cipher they use. Can you maximize the chance that the NSA can't guess who got that coin AND Alice and Bob agree on the correct result?

Note: An open problem. You can look up cryptogenography for current results.