Itay Berman
ABSTRACT
We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., .499) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias [EQUATION] -- o(1) ≈ .207. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.
Supplemental Material
- B. Averbuch, M. Blum, B. Chor, S. Goldwasser, and S. Micali. How to implement Bracha's O(log n) Byzantine agreement algorithm, 1985. Unpublished manuscript.Google Scholar
- A. Beimel, E. Omri, and I. Orlov. Protocols for multiparty coin toss with dishonest majority. In Advances in Cryptology -- CRYPTO 2010, pages 538--557, 2010. Google ScholarDigital Library
- I. Berman, I. Haitner, and A. Tentes. Coin flipping of any constant bias implies one-way functions. www.cs.tau.ac.il/~iftachh/papers/TightCF/TCoingFlip_F.pdf, 2014. Manuscript.Google Scholar
- M. Blum. Coin flipping by telephone. In Advances in Cryptology -- CRYPTO '81, pages 11--15, 1981.Google Scholar
- A. Chailloux and I. Kerenidis. Optimal quantum strong coin flipping. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), pages 527--533, 2009. Google ScholarDigital Library
- R. Cleve. Limits on the security of coin flips when half the processors are faulty. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), pages 364--369, 1986. Google ScholarDigital Library
- R. Cleve and R. Impagliazzo. Martingales, collective coin flipping and discrete control processes (extended abstract). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1797, 1993.Google Scholar
- D. Dachman-Soled, Y. Lindell, M. Mahmoody, and T. Malkin. On the black-box complexity of optimally-fair coin tossing. In Theory of Cryptography, 8th Theory of Cryptography Conference, TCC 2011, volume 6597, pages 450--467, 2011. Google ScholarDigital Library
- O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pages 25--32, 1989. Google ScholarDigital Library
- O. Goldreich, S. Goldwasser, and S. Micali. On the cryptographic applications of random functions. In Advances in Cryptology -- CRYPTO '84, pages 276--288, 1984. Google ScholarDigital Library
- O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM, pages 792--807, 1986. Google ScholarDigital Library
- I. Haitner and E. Omri. Coin Flipping with Constant Bias Implies One-Way Functions. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 110--119, 2011. Google ScholarDigital Library
- I. Haitner, M. Nguyen, S. J. Ong, O. Reingold, and S. Vadhan. Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM Journal on Computing, 39(3):1153--1218, 2009. Google ScholarDigital Library
- J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, pages 1364--1396, 1999. Google ScholarDigital Library
- R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 230--235, 1989. Google ScholarDigital Library
- A. Y. Kitaev. Quantum coin-flipping. Presentation at the 6th workshop on quantum information processing (qip 2003), 2003.Google Scholar
- H. K. Maji, M. Prabhakaran, and A. Sahai. On the Computational Complexity of Coin Flipping. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 613--622, 2010. Google ScholarDigital Library
- C. Mochon. Quantum weak coin flipping with arbitrarily small bias. arXiv:0711.4114, 2007.Google Scholar
- T. Moran, M. Naor, and G. Segev. An optimally fair coin toss. In Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, pages 1--18, 2009. Google ScholarDigital Library
- M. Naor. Bit commitment using pseudorandomness. Journal of Cryptology, pages 151--158, 1991.Google ScholarDigital Library
- M. Naor and M. Yung. Universal one-way hash functions and their cryptographic applications. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pages 33--43, 1989. Google ScholarDigital Library
- J. Rompel. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 387--394, 1990. Google ScholarDigital Library
- S. Zachos. Probabilistic Quantifiers, Adversaries, and Complexity Classes: An Overview. In Proceedings of the First Annual IEEE Conference on Computational Complexity, pages 383--400, 1986. Google ScholarDigital Library
Index Terms
- Coin flipping of any constant bias implies one-way functions
Recommendations
An almost-optimally fair three-party coin-flipping protocol
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computingIn a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [STOC 1986] has shown that in the case of dishonest majority (i.e., at least half of the ...
Coin Flipping with Constant Bias Implies One-Way Functions
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer ScienceIt is well known (cf., Impagliazzo and Luby [FOCS '89]) that the existence of almost all ``interesting" cryptographic applications, i.e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above ...
Coin Flipping of Any Constant Bias Implies One-Way Functions
We show that the existence of a coin-flipping protocol safe against any nontrivial constant bias (e.g., .499) implies the existence of one-way functions. This improves upon a result of Haitner and Omri (FOCS’11), who proved this implication for ...
Comments