We consider the cryptographic two-party protocol task of extending a given coin toss. The goal is to generate
common random coins from a single use of an ideal functionality which gives
common random coins to the parties. In the framework of Universal Composability we show the impossibility of securely extending a coin toss for statistical and perfect security. On the other hand, for computational security the existence of a protocol for coin toss extension depends on the number
of random coins which can be obtained “for free”.
For the case of stand-alone security, i.e., a simulation based security definition without an environment, we present a novel protocol for unconditionally secure coin toss extension. The new protocol works for superlogarithmic
, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller
Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.