**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