TY - CHAP
T1 - On the Black-Box Complexity of Optimally-Fair Coin Tossing
T2 - Theory of Cryptography
Y1 - 2011
A1 - Dana Dachman-Soled
A1 - Lindell, Yehuda
A1 - Mahmoody, Mohammad
A1 - Malkin, Tal
ED - Ishai, Yuval
KW - Algorithm Analysis and Problem Complexity
KW - black-box separations
KW - Coding and Information Theory
KW - coin tossing
KW - Computer Communication Networks
KW - Data Encryption
KW - lower-bound
KW - Math Applications in Computer Science
KW - optimally-fair coin tossing
KW - round-complexity
KW - Systems and Data Security
AB - A fair two-party coin tossing protocol is one in which both parties output the same bit that is almost uniformly distributed (i.e., it equals 0 and 1 with probability that is at most negligibly far from one half). It is well known that it is impossible to achieve fair coin tossing even in the presence of fail-stop adversaries (Cleve, FOCS 1986). In fact, Cleve showed that for every coin tossing protocol running for r rounds, an efficient fail-stop adversary can bias the output by Ω(1/r). Since this is the best possible, a protocol that limits the bias of any adversary to O(1/r) is called optimally-fair. The only optimally-fair protocol that is known to exist relies on the existence of oblivious transfer, because it uses general secure computation (Moran, Naor and Segev, TCC 2009). However, it is possible to achieve a bias of O(1/r√)O(1/\sqrt{r}) in r rounds relying only on the assumption that there exist one-way functions. In this paper we show that it is impossible to achieve optimally-fair coin tossing via a black-box construction from one-way functions for r that is less than O(n/logn), where n is the input/output length of the one-way function used. An important corollary of this is that it is impossible to construct an optimally-fair coin tossing protocol via a black-box construction from one-way functions whose round complexity is independent of the security parameter n determining the security of the one-way function being used. Informally speaking, the main ingredient of our proof is to eliminate the random-oracle from “secure” protocols with “low round-complexity” and simulate the protocol securely against semi-honest adversaries in the plain model. We believe our simulation lemma to be of broader interest.
JA - Theory of Cryptography
T3 - Lecture Notes in Computer Science
PB - Springer Berlin Heidelberg
SN - 978-3-642-19570-9, 978-3-642-19571-6
UR - http://link.springer.com/chapter/10.1007/978-3-642-19571-6_27
ER -