An almost-optimally fair three-party coin-flipping protocol. (English) Zbl 1315.94078
Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 408-416 (2014).
MSC:
| 94A60 | Cryptography |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Software:
SuLQReferences:
| [1] | D. Aharonov, A. Ta-Shma, U. Vazirani, and A. C. Yao. Quantum bit escrow. In STOC: ACM Symposium on Theory of Computing (STOC), 2000. 10.1145/335305.335404 · Zbl 1296.94074 |
| [2] | W. Aiello, Y. Ishai, and O. Reingold. Priced oblivious transfer: How to sell digital goods. In Advances in Cryptology – EUROCRYPT 2001, 2001. |
| [3] | N. Alon and M. Naor. Coin-flipping games immune against linear-sized coalitions. SIAM Journal on Computing, pages 46-54, 1993. 10.1137/0222030 |
| [4] | A. Ambainis. A new protocol and lower bounds for quantum coin flipping. J. Comput. Syst. Sci., 68(2): 398-416, 2004. 10.1016/j.jcss.2003.07.010 · Zbl 1091.68046 |
| [5] | A. Ambainis, H. Buhrman, Y. Dodis, and H. Röhrig. Multiparty quantum coin flipping. In Proceedings of the 18th Annual IEEE Conference on Computational Complexity, pages 250-259, 2004. 10.1109/CCC.2004.19 |
| [6] | 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. · Zbl 1283.94049 |
| [7] | A. Beimel, Y. Lindell, E. Omri, and I. Orlov. 1/p-secure multiparty computation without honest majority and the best of both worlds. pages 277-296, 2011. · Zbl 1287.94051 |
| [8] | M. Ben-Or and N. Linial. Collective coin flipping. ADVCR: Advances in Computing Research, 5, 1989. |
| [9] | M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), 1988. 10.1145/62212.62213 |
| [10] | I. Berman, I. Haitner, and A. Tentes. Coin flipping of any constant bias implies one-way functions. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC). 10.1145/2591796.2591845 · Zbl 1315.94055 |
| [11] | M. Blum. How to exchange (secret) keys. ACM Transactions on Computer Systems, 1983. 10.1145/357360.357368 |
| [12] | R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1): 143-202, 2000. · Zbl 0957.68040 |
| [13] | R. Cleve. Limits on the security of coin flips when half the processors are faulty. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pages 364-369, 1986. 10.1145/12130.12168 |
| [14] | R. Cleve and R. Impagliazzo. Martingales, collective coin flipping and discrete control processes. Manuscript, 1993. |
| [15] | D. Dachman-Soled, Y. Lindell, M. Mahmoody, and T. Malkin. On the black-box complexity of optimally fair coin tossing. In tcc11, pages 450-467, 2011. · Zbl 1295.94044 |
| [16] | S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Communications of the ACM, 28(6):637-647, 1985. 10.1145/3812.3818 |
| [17] | U. Feige. Noncryptographic selection protocols. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), 1999. |
| [18] | C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 197-206, 2008. 10.1145/1374376.1374407 · Zbl 1231.68124 |
| [19] | O. Goldreich. Foundations of Cryptography – VOLUME 2: Basic Applications. Cambridge University Press, 2004. · Zbl 1068.94011 |
| [20] | O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, pages 691-729, 1991. Preliminary version in FOCS’86. 10.1145/116825.116852 · Zbl 0799.68101 |
| [21] | S. D. Gordon and J. Katz. Partial fairness in secure two-party computation. pages 157-176, 2010. 10.1007/978-3-642-13190-5_8 · Zbl 1279.94078 |
| [22] | S. D. Gordon, C. Hazay, J. Katz, and Y. Lindell. Complete fairness in secure two-party computation. pages 413-422, 2008. 10.1145/1374376.1374436 · Zbl 1231.94062 |
| [23] | S. D. Gordon, C. Hazay, J. Katz, and Y. Lindell. Complete fairness in secure two-party computation. Journal of the ACM, 58(6):24, 2011. 10.1145/2049697.2049698 · Zbl 1281.94081 |
| [24] | I. Haitner. Implementing oblivious transfer using collection of dense trapdoor permutations. In Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, pages 394-409, 2004. · Zbl 1197.94189 |
| [25] | I. Haitner and E. Omri. Coin Flipping with Constant Bias Implies One-Way Functions. pages 110-119, 2011. 10.1109/FOCS.2011.29 · Zbl 1292.94071 |
| [26] | I. Haitner and E. Tsfadia. An almostoptimally fair three-party coin-flipping protocol. www.cs.tau.ac.il/ iftachh/papers/3PartyCF/QuasiOptimalCF_Full.pdf, 2014. Manuscript. |
| [27] | 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, pages 1153-1218, 2009. 10.1137/080725404 · Zbl 1195.94057 |
| [28] | 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. 10.1109/SFCS.1989.63483 |
| [29] | Y. Kalai. Smooth projective hashing and two-message oblivious transfer. In Advances in Cryptology – EUROCRYPT 2005, 2005. 10.1007/11426639_5 · Zbl 1137.94348 |
| [30] | J. Katz. On achieving the “best of both worlds” in secure multiparty computation. pages 11-20, 2007. 10.1145/1250790.1250793 · Zbl 1232.68045 |
| [31] | H. K. Maji, M. Prabhakaran, and A. Sahai. On the Computational Complexity of Coin Flipping. In Proceedings of the 51th Annual Symposium on Foundations of Computer Science (FOCS), pages 613-622, 2010. 10.1109/FOCS.2010.64 |
| [32] | T. Moran and M. Naor. Basing cryptographic protocols on tamper-evident seals. In ICALP: Annual International Colloquium on Automata, Languages and Programming, 2005. 10.1007/11523468_24 |
| [33] | T. Moran, M. Naor, and G. Segev. An optimally fair coin toss. In Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2009, pages 1-18, 2009. 10.1007/978-3-642-00457-5_1 · Zbl 1213.94123 |
| [34] | M. Naor. Bit commitment using pseudorandomness. Journal of Cryptology, pages 151-158, 1991. · Zbl 0731.68033 |
| [35] | M. Naor and B. Pinkas. Efficient oblivious transfer protocols. In SODA, pages 448-457, 2001. · Zbl 0991.94045 |
| [36] | A. Russell and D. Zuckerman. Perfect information leader election in log* n + 0 (1) rounds. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), 1999. |
| [37] | M. Saks. A robust noncryptographic protocol for collective coin flipping. SIJDM: SIAM Journal on Discrete Mathematics, 2, 1989. 10.1137/0402020 · Zbl 0671.90109 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
