KIT | KIT-Bibliothek | Impressum | Datenschutz

On the (Im-)Possibility of Extending Coin Toss

Hofheinz, Dennis 1; Müller-Quade, Jörn 1; Unruh, Dominique
1 Karlsruher Institut für Technologie (KIT)


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 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 stand-alone 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.

Verlagsausgabe §
DOI: 10.5445/IR/1000086550
Veröffentlicht am 06.11.2018
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 10.2018
Sprache Englisch
Identifikator ISSN: 0933-2790, 1432-1378
KITopen-ID: 1000086550
Erschienen in Journal of cryptology
Verlag Springer
Band 31
Heft 4
Seiten 1120–1163
Vorab online veröffentlicht am 26.04.2018
Schlagwörter Coin toss, Universal composability, Reactive simulatability, Cryptographic protocols
Nachgewiesen in Scopus
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page