Document Open Access Logo

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

Authors Yael Tauman Kalai, Ilan Komargodski, Ran Raz

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.34.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Yael Tauman Kalai
  • Microsoft Research, 1 Memorial Dr, Cambridge, MA 02142, USA
Ilan Komargodski
  • Cornell Tech, 2 W Loop Rd, New York, NY 10044, USA
Ran Raz
  • Department of Computer Science, Princeton University, Princeton, NJ 08544, USA

Funding

  • Komargodski, Ilan: Supported in part by a Packard Foundation Fellowship and by an AFOSR grant FA9550-15-1-0262.
  • Raz, Ran: Research supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation grants No. CCF-1714779 and CCF-1412958.

Cite As Get BibTex

Yael Tauman Kalai, Ilan Komargodski, and Ran Raz. A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.DISC.2018.34

Abstract

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 in the course of the protocol as a function of the messages seen so far. They showed that the majority protocol, in which each player sends a random bit and the output is the majority value, tolerates O(sqrt n) adaptive corruptions. They conjectured that this is optimal for such adversaries.
We prove that the majority protocol is optimal (up to a poly-logarithmic factor) among all protocols in which each party sends a single, possibly long, message.
Previously, such a lower bound was known for protocols in which parties are allowed to send only a single bit (Lichtenstein, Linial, and Saks, Combinatorica '89), or for symmetric protocols (Goldwasser, Kalai, and Park, ICALP '15).

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
Keywords
  • Coin flipping
  • adaptive corruptions
  • byzantine faults
  • lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Miklós Ajtai and Nathan Linial. The influence of large coalitions. Combinatorica, 13(2):129-145, 1993. Google Scholar
  2. Bar Alon and Eran Omri. Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious. In Theory of Cryptography - 14th International Conference, TCC 2016-B, pages 307-335, 2016. Google Scholar
  3. Noga Alon and Moni Naor. Coin-flipping games immune against linear-sized coalitions. SIAM J. Comput., 22(2):403-417, 1993. Google Scholar
  4. Noga Alon and Joel Spencer. The Probabilistic Method. John Wiley, third edition, 2008. Google Scholar
  5. Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, and Eran Omri. Tighter bounds on multi-party coin flipping, via augmented weak martingales and di erentially private sampling. Electronic Colloquium on Computational Complexity (ECCC), 24:168, 2017. Google Scholar
  6. Amos Beimel, Eran Omri, and Ilan Orlov. Protocols for multiparty coin toss with a dishonest majority. J. Cryptology, 28(3):551-600, 2015. Google Scholar
  7. Michael Ben-Or and Nathan Linial. Collective coin flipping. Advances in Computing Research, 5:91-115, 1989. Google Scholar
  8. Ravi B. Boppana and Babu O. Narayanan. The biased coin problem. SIAM J. Discrete Math., 9(1):29-36, 1996. Google Scholar
  9. Niv Buchbinder, Iftach Haitner, Nissan Levi, and Eliad Tsfadia. Fair coin flipping: Tighter analysis and the many-party case. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2580-2600. SIAM, 2017. Google Scholar
  10. Richard Cleve. Limits on the security of coin flips when half the processors are faulty (extended abstract). In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 364-369. ACM, 1986. Google Scholar
  11. Richard Cleve and Russell Impagliazzo. Martingales, collective coin flipping and discrete control processes (extended abstract), 1993. Unpublished manuscript. Google Scholar
  12. Yevgeniy Dodis. Impossibility of black-box reduction from non-adaptively to adaptively secure coin-flipping. Electronic Colloquium on Computational Complexity (ECCC), 7(39), 2000. Google Scholar
  13. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. URL: http://dx.doi.org/10.1017/CBO9780511581274.
  14. Uriel Feige. Noncryptographic selection protocols. In 40th Annual Symposium on Foundations of Computer Science, FOCS, pages 142-153, 1999. Google Scholar
  15. Shafi Goldwasser, Yael Tauman Kalai, and Sunoo Park. Adaptively secure coin-flipping, revisited. In 42nd International Colloquium on Automata, Languages and Programming,, ICALP, pages 663-674, 2015. Google Scholar
  16. Iftach Haitner and Eliad Tsfadia. An almost-optimally fair three-party coin-flipping protocol. SIAM J. Comput., 46(2):479-542, 2017. Google Scholar
  17. Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, FOCS, pages 68-80, 1988. Google Scholar
  18. Yael Tauman Kalai and Ilan Komargodski. Compressing communication in distributed protocols. In Distributed Computing - 29th International Symposium, DISC, pages 467-479, 2015. Google Scholar
  19. David Lichtenstein, Nathan Linial, and Michael E. Saks. Some extremal problems arising form discrete control processes. Combinatorica, 9(3):269-287, 1989. Google Scholar
  20. Tal Moran, Moni Naor, and Gil Segev. An optimally fair coin toss. J. Cryptology, 29(3):491-513, 2016. Google Scholar
  21. Alexander Russell, Michael E. Saks, and David Zuckerman. Lower bounds for leader election and collective coin-flipping in the perfect information model. SIAM J. Comput., 31(6):1645-1662, 2002. Google Scholar
  22. Michael E. Saks. A robust noncryptographic protocol for collective coin flipping. SIAM J. Discrete Math., 2(2):240-244, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact