  We define a variation on the well-known problem of private message
transmission. This new problem called private randomness agreement (PRA) gives
two participants access to a public, authenticated channel alongside the main
channels, and the 'message' is not fixed a priori.
  Instead, the participants aim to agree on a random string completely unknown
to a computationally unbounded adversary.
  We define privacy and reliability, and show that PRA cannot be solved in a
single round. We then show that it can be solved in three rounds, albeit with
exponential cost, and give an efficient four-round protocol based on polynomial
evaluation.
