2021/05/03 by Amos Beimel, Beimel, Amos, Iftach Haitner +5
Computer Science · Engineering · #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2105.00743
openalex publication_date 2021/05/03 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
In his seminal work, Cleve [STOC '86] has proved that any r-round coin-flipping protocol can be efficiently biased by Θ(1/r). This 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 and Tsfadi [SICOMP '17], and was approached for n-party protocols when n< loglog r by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For n> loglog r, however, the best bias for n-party coin-flipping protocols remains O(n/√(r)) achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ε>0, an rε-party r-round coin-flipping protocol can be efficiently biased by \widetildeΩ(1/√(r)). As far as we know, this is the first improvement of Cleve's bound, and is only n=rε (multiplicative) far from the aforementioned upper bound of Awerbuch et al.