TY - CHAP
T1 - Can Optimally-Fair Coin Tossing Be Based on One-Way Functions?
T2 - Theory of Cryptography
Y1 - 2014
A1 - Dana Dachman-Soled
A1 - Mahmoody, Mohammad
A1 - Malkin, Tal
ED - Lindell, Yehuda
KW - Algorithm Analysis and Problem Complexity
KW - black-box separations
KW - Coin-Tossing
KW - Computation by Abstract Devices
KW - Data Encryption
KW - Discrete Mathematics in Computer Science
KW - One-Way Functions
KW - Systems and Data Security
AB - Coin tossing is a basic cryptographic task that allows two distrustful parties to obtain an unbiased random bit in a way that neither party can bias the output by deviating from the protocol or halting the execution. Cleve [STOC’86] showed that in any r round coin tossing protocol one of the parties can bias the output by Ω(1/r) through a “fail-stop” attack; namely, they simply execute the protocol honestly and halt at some chosen point. In addition, relying on an earlier work of Blum [COMPCON’82], Cleve presented an r-round protocol based on one-way functions that was resilient to bias at most O(1/r√)O(1/\sqrt r) . Cleve’s work left open whether ”‘optimally-fair’” coin tossing (i.e. achieving bias O(1/r) in r rounds) is possible. Recently Moran, Naor, and Segev [TCC’09] showed how to construct optimally-fair coin tossing based on oblivious transfer, however, it was left open to find the minimal assumptions necessary for optimally-fair coin tossing. The work of Dachman-Soled et al. [TCC’11] took a step toward answering this question by showing that any black-box construction of optimally-fair coin tossing based on a one-way functions with n-bit input and output needs Ω(n/logn) rounds. In this work we take another step towards understanding the complexity of optimally-fair coin-tossing by showing that this task (with an arbitrary number of rounds) cannot be based on one-way functions in a black-box way, as long as the protocol is ”‘oblivious’” to the implementation of the one-way function. Namely, we consider a natural class of black-box constructions based on one-way functions, called function oblivious, in which the output of the protocol does not depend on the specific implementation of the one-way function and only depends on the randomness of the parties. Other than being a natural notion on its own, the known coin tossing protocols of Blum and Cleve (both based on one-way functions) are indeed function oblivious. Thus, we believe our lower bound for function-oblivious constructions is a meaningful step towards resolving the fundamental open question of the complexity of optimally-fair coin tossing.
JA - Theory of Cryptography
T3 - Lecture Notes in Computer Science
PB - Springer Berlin Heidelberg
SN - 978-3-642-54241-1, 978-3-642-54242-8
UR - http://link.springer.com/chapter/10.1007/978-3-642-54242-8_10
ER -