On the (Im-)Possibility of Extending Coin Toss

On the (Im-)Possibility of Extending Coin Toss (Journal of Cryptology, 2018)
Dennis Hofheinz, Jörn Müller-Quade, Dominique Unruh
[ eprint | official ]

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 [CITE hofheinz06possibility].