Paper 2006/177

On the (Im-)Possibility of Extending Coin Toss

Dennis Hofheinz, Joern Mueller-Quade, and Dominique Unruh

Abstract

We consider the cryptographic two-party protocol task of extending a given coin toss. The goal is to generate n common random coins from a single use of an ideal functionality which gives m<n common random coins to the 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 which can be obtained "for free". For the case of stand-alone security, i.e., a simulation based security definition without an environment, we present a novel protocol for unconditionally secure coin toss extension. The new 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.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. This is the full version of the paper presented at Eurocrypt 2006
Keywords
coin tossuniversal composabilityreactive simulatabilitycryptographic protocols
Contact author(s)
unruh @ ira uka de
History
2006-05-26: received
Short URL
https://ia.cr/2006/177
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/177,
      author = {Dennis Hofheinz and Joern Mueller-Quade and Dominique Unruh},
      title = {On the (Im-)Possibility of Extending Coin Toss},
      howpublished = {Cryptology ePrint Archive, Paper 2006/177},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/177}},
      url = {https://eprint.iacr.org/2006/177}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.