On the (Im-)Possibility of Extending Coin Toss

On the (Im-)Possibility of Extending Coin TossD. Hofheinz, J. Müller-Quade, and D. Unruh (Journal of Cryptology, 2018). To appear.  [eprint]

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: