Abstract: We consider the task of extending a given coin toss. By this, we mean the two-party task of using a single instance of a given coin toss protocol in order to interactively generate \emph{more} random coins. A bit more formally, our goal is to generate $n$ common random coins from a single use of an ideal functionality that gives $m<n$ common random coins to both 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 $m$ of random coins that can be obtained "for free".
For the case of standalone security, i.e., a simulation based security definition without an environment, we present a protocol for statistically secure coin toss extension. Our protocol works for superlogarithmic $m$, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller $m$.
Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.
Short version is Hofheinz, Müller-Quade, Unruh, On the (Im-)Possibility of Extending Coin Toss, 2006.
Permalink: http://www.ut.ee/~unruh/publications/cointoss-joc.html