KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
§
Verlagsausgabe
DOI: 10.5445/IR/1000086550
Veröffentlicht am 06.11.2018

On the (Im-)Possibility of Extending Coin Toss

Hofheinz, Dennis; Müller-Quade, Jörn; Unruh, Dominique

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 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 i ... mehr


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Jahr 2018
Sprache Englisch
Identifikator ISSN: 0933-2790, 1432-1378
URN: urn:nbn:de:swb:90-865502
KITopen ID: 1000086550
Erschienen in Journal of cryptology
Band 31
Heft 4
Seiten 1120–1163
Vorab online veröffentlicht am 26.04.2018
Schlagworte Coin toss, Universal composability, Reactive simulatability, Cryptographic protocols
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page