%0 Book Section
%B Theory of Cryptography
%D 2014
%T Can Optimally-Fair Coin Tossing Be Based on One-Way Functions?
%A Dana Dachman-Soled
%A Mahmoody, Mohammad
%A Malkin, Tal
%E Lindell, Yehuda
%K Algorithm Analysis and Problem Complexity
%K black-box separations
%K Coin-Tossing
%K Computation by Abstract Devices
%K Data Encryption
%K Discrete Mathematics in Computer Science
%K One-Way Functions
%K Systems and Data Security
%X 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.
%B Theory of Cryptography
%S Lecture Notes in Computer Science
%I Springer Berlin Heidelberg
%P 217 - 239
%8 2014/01/01/
%@ 978-3-642-54241-1, 978-3-642-54242-8
%G eng
%U http://link.springer.com/chapter/10.1007/978-3-642-54242-8_10