On the (Im-)Possibility of Extending Coin Toss

On the (Im-)Possibility of Extending Coin TossD. Hofheinz, J. Müller-Quade, and D. Unruh (Eurocrypt 2006).  [publisher's version | eprint]

Abstract: We consider the cryptographic two-party protocol task of extending a given coin toss. The protocol goal is thus to generate n common random coins that are uniformly and independently distributed even if one party is corrupted. Since we are dealing with the extension of a given coin toss, we assume that a coin toss of m<n bits is already given "for free" to the parties.

Both protocol task and initial assumption can be formulated conveniently as ideal functionalities in the setting of simulatable security (depending on the used framework commonly referred to as Universal Composability or Reactive Simulatability). In this setting, we show the impossibility of extending coin toss for perfect and statistical security (for statistical security, we restrict to polynomial-round protocols). On the other hand, for computational security and suitable n,m, we show how to modify and use a known protocol construction for our purposes.

We also consider not universally composable security definitions (i.e., security definitions without an environment). We show exactly when such a coin-toss extension is possible and when not. In particular, we give an unconditionally secure protocol for extending coin-toss.

Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.

Permalink: