Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with coin flipping:
TR06-096 | 10th August 2006
Iftach Haitner, Omer Reingold

A New Interactive Hashing Theorem

Interactive hashing, introduced by Naor et al. [NOVY98], plays
an important role in many cryptographic protocols. In particular, it
is a major component in all known constructions of
statistically-hiding commitment schemes and of zero-knowledge
arguments based on general one-way permutations and on one-way
functions. Interactive hashing with respect to a ... more >>>

TR17-168 | 5th November 2017
Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri

Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Di erentially Private Sampling

Revisions: 6

In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner ... more >>>

TR18-084 | 24th April 2018
Iftach Haitner, Nikolaos Makriyannis, Eran Omri

On the Complexity of Fair Coin Flipping

A two-party coin-flipping protocol is $\varepsilon$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\varepsilon$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript '85] ... more >>>

TR18-140 | 11th August 2018
Ilan Komargodski, Ran Raz, Yael Tauman Kalai

A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols

Revisions: 1

In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where $n$ parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party ... more >>>

ISSN 1433-8092 | Imprint