Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious. (English) Zbl 1518.94038
Summary: An \(\alpha\)-fair coin-tossing protocol allows a set of mutually distrustful parties to generate a uniform bit, such that no efficient adversary can bias the output bit by more than \(\alpha\). R. Cleve [in: Proceedings of the eighteenth annual ACM symposium on theory of computing, STOC ’86, Berkeley, CA, USA, May 28–30, 1986. New York, NY: Association for Computing Machinery (ACM). 364–369 (1986; doi.org/10.1145/12130.12168)] has shown that if half of the parties can be corrupted, then no \(r\)-round coin-tossing protocol is \(o(1/r)\)-fair. For over two decades, the best-known \(m\)-party protocols, tolerating up to \(t\geq m/2\) corrupted parties, were only \(O\left( t/\sqrt{r} \right)\)-fair. In a surprising result, T. Moran et al. [Lect. Notes Comput. Sci. 5444, 1–18 (2009; Zbl 1213.94123)] constructed an \(r\)-round two-party \(O(1/r)\)-fair coin-tossing protocol, i.e., an optimally fair protocol. A. Beimel et al. [ibid. 6223, 538–557 (2010; Zbl 1283.94049)] extended the result of Moran et al. to the multiparty setting where strictly fewer than 2/3 of the parties are corrupted. They constructed a \(2^{2^k}/r\)-fair \(r\)-round \(m\)-party protocol, tolerating up to \(t=\frac{m+k}{2}\) corrupted parties. In a breakthrough result, I. Haitner and E. Tsfadia [in: 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). 408–416 (2014; Zbl 1315.94078)] constructed an \(O\Big( \log^3 (r)/r \Big)\)-fair (almost optimal) three-party coin-tossing protocol. Their work brought forth a combination of novel techniques for coping with the difficulties of constructing fair coin-tossing protocols. Still, the best coin-tossing protocols for the case where more than 2/3 of the parties may be corrupted (and even when \(t=2m/3\), where \(m>3)\) were \(\theta (1/\sqrt{r})\)-fair. We construct an \(O\Big( \log^3 (r)/r \Big)\)-fair \(m\)-party coin-tossing protocol, tolerating up to \(t\) corrupted parties, whenever \(m\) is constant and \(t<3m/4\).
MSC:
| 94A60 | Cryptography |
| 94A62 | Authentication, digital signatures and secret sharing |
| 68P25 | Data encryption (aspects in computer science) |
Keywords:
secure multyparty computation (MPC); fair coin tossing; fair computation; dishonest majorityReferences:
| [1] | S. Agrawal, M. Prabhakaran, On fair exchange, fair coins and fair sampling, in Advances in Cryptology—CRYPTO 2013 (Springer, 2013), pp. 259-276 · Zbl 1310.94121 |
| [2] | B. Alon, E. Omri, Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious, in Theory of Cryptography Conference (Springer, 2016), pp. 307-335 · Zbl 1406.94019 |
| [3] | G. Asharov, Towards characterizing complete fairness in secure two-party computation, in Proceedings of the Eleventh Theory of Cryptography Conference—TCC 2014, vol. 8349 (Springer, 2014), pp. 291-316 · Zbl 1326.94070 |
| [4] | G. Asharov, Y. Lindell, T. Rabin, A full characterization of functions that imply fair coin tossing and ramifications to fairness, in Proceedings of the Tenth Theory of Cryptography Conference—TCC 2013, volume 7785 of Lecture Notes in Computer Science (Springer, 2013), pp. 243-262 · Zbl 1315.94051 |
| [5] | G. Asharov, A. Beimel, N. Makriyannis, E. Omri, Complete characterization of fairness in secure two-party computation of boolean functions, in Theory of Cryptography Conference (Springer, 2015), pp. 199-228 · Zbl 1354.94020 |
| [6] | Y. Aumann, Y. Lindell, Security against covert adversaries: Efficient protocols for realistic adversaries, in Theory of Cryptography (Springer, 2007), pp. 137-156 · Zbl 1129.94010 |
| [7] | B. Averbuch, M. Blum, B. Chor, S. Goldwasser, S. Micali, How to implement Bracha’s \({O}(\log n)\) Byzantine agreement algorithm, 1985. Unpublished manuscript |
| [8] | A. Beimel, Y. Lindell, E. Omri, I. Orlov, 1/p-secure multiparty computation without honest majority and the best of both worlds, in P. Rogaway, editor, Advances in Cryptology—CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science (Springer, 2011), pp. 277-296 · Zbl 1287.94051 |
| [9] | A. Beimel, E. Omri, I. Orlov, Protocols for multiparty coin toss with dishonest majority. J. Cryptology, 28(3), 551-600, 2015. Conference version, in T. Rabin, editor, Advances in Cryptology—CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science (Springer-Verlag, 2010), pp. 538-557 · Zbl 1283.94049 |
| [10] | A. Beimel, I. Haitner, N. Makriyannis, E. Omri, Tighter bounds on multi-party coin flipping via augmented weak martingales and differentially private sampling, in M. Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 (IEEE Computer Society, 2018), pp. 838-849 · Zbl 1495.94042 |
| [11] | M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS) (1988), pp. 1-10 |
| [12] | Berman, I. Haitner, A. Tentes, Coin flipping of any constant bias implies one-way functions, in Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31-June 03, 2014 (2014), pp. 398-407 · Zbl 1315.94055 |
| [13] | M. Blum, Coin flipping by telephone, in Advances in Cryptology—CRYPTO ’81 (1981), pp. 11-15 |
| [14] | Blum, M., Coin flipping by telephone a protocol for solving impossible problems, SIGACT News, 15, 1, 23-27 (1983) · Zbl 0501.68011 · doi:10.1145/1008908.1008911 |
| [15] | N. Buchbinder, I. Haitner, N. Levi, E. Tsfadia, Fair coin flipping: Tighter analysis and the many-party case, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2017), pp. 2580-2600 · Zbl 1414.94909 |
| [16] | Canetti, R., Security and composition of multiparty cryptographic protocols, Journal of CRYPTOLOGY, 13, 1, 143-202 (2000) · Zbl 0957.68040 · doi:10.1007/s001459910006 |
| [17] | 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) (1986), pp. 364-369 |
| [18] | R. Cleve, R. Impagliazzo, Martingales, collective coin flipping and discrete control processes. Manuscript (1993) |
| [19] | D. Dachman-Soled, Y. Lindell, M. Mahmoody, T. Malkin, On the black-box complexity of optimally-fair coin tossing, in Theory of Cryptography, Eighth Theory of Cryptography Conference, TCC 2011, vol. 6597 (2011), pp. 450-467 · Zbl 1295.94044 |
| [20] | D. Dachman-Soled, M. Mahmoody, T. Malkin, Can optimally-fair coin tossing be based on one-way functions? in Theory of Cryptography—11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings (2014), pp. 217-239 · Zbl 1323.94108 |
| [21] | Even, S.; Goldreich, O.; Lempel, A., A randomized protocol for signing contracts, Communications of the ACM, 28, 6, 637-647 (1985) · doi:10.1145/3812.3818 |
| [22] | O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications. (Cambridge University Press, 2009) · Zbl 1179.94063 |
| [23] | O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in stoc19 (1987), pp. 218-229 |
| [24] | S. Goldwasser, Y. Lindell, Secure computation without agreement, in Distributed Computing (Springer, 2002), pp. 17-32 · Zbl 1029.68511 |
| [25] | S. D. Gordon, J. Katz, Partial fairness in secure two-party computation, in H. Gilbert, editor, Advances in Cryptology—EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science (Springer, 2010), pp. 157-176 · Zbl 1279.94078 |
| [26] | Gordon, SD; Katz, J., Partial fairness in secure two-party computation, Journal of Cryptology, 25, 1, 14-40 (2012) · Zbl 1272.94032 · doi:10.1007/s00145-010-9079-5 |
| [27] | S. D. Gordon, C. Hazay, J. Katz, Y. Lindell, Complete fairness in secure two-party computation, in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC) (2008), pp. 413-422 · Zbl 1231.94062 |
| [28] | I. Haitner, Implementing oblivious transfer using collection of dense trapdoor permutations, in Theory of Cryptography Conference (Springer, 2004), pp. 394-409 · Zbl 1197.94189 |
| [29] | I. Haitner, E. Omri, Coin Flipping with Constant Bias Implies One-Way Functions, in Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS) (2011), pp. 110-119 · Zbl 1292.94071 |
| [30] | I. Haitner, E. Tsfadia, An almost-optimally fair three-party coin-flipping protocol, in Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31-June 03, 2014 (2014), pp. 408-416. http://www.cs.tau.ac.il/ iftachh/papers/3PartyCF/QuasiOptimalCF_Full.pdf · Zbl 1315.94078 |
| [31] | Haitner, I.; Nguyen, M.; Ong, SJ; Reingold, O.; Vadhan, S., Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function, SIAM Journal on Computing, 39, 3, 1153-1218 (2009) · Zbl 1195.94057 · doi:10.1137/080725404 |
| [32] | I. Haitner, N. Makriyannis, E. Omri, On the complexity of fair coin flipping, in A. Beimel and S. Dziembowski, editors, Theory of Cryptography—16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part I, volume 11239 of Lecture Notes in Computer Science (Springer, 2018), pp. 539-562 · Zbl 1443.94059 |
| [33] | W. Hoeffding, Probability inequalities for sums of bounded random variables, in The Collected Works of Wassily Hoeffding (Springer, 1994), pp. 409-426 · Zbl 0807.01034 |
| [34] | Y. Ishai, R. Ostrovsky, V. Zikas, Secure multi-party computation with identifiable abort, in Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II (2014), pp. 369-386 · Zbl 1335.94053 |
| [35] | Y. T. Kalai, Smooth projective hashing and two-message oblivious transfer, in Annual International Conference on the Theory and Applications of Cryptographic Techniques (Springer, 2005), pp. 78-95 · Zbl 1137.94348 |
| [36] | J. Katz, On achieving the “best of both worlds” in secure multiparty computation, in STOC07 (2007), pp. 11-20 · Zbl 1232.68045 |
| [37] | Maji, HK; Wang, M., Black-box use of one-way functions is useless for optimal fair coin-tossing, IACR Cryptol. ePrint Arch., 2020, 253 (2020) |
| [38] | H. K. Maji, M. Prabhakaran, A. Sahai, On the Computational Complexity of Coin Flipping, in Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS) (2010), pp. 613-622 |
| [39] | N. Makriyannis, On the classification of finite boolean functions up to fairness, in Security and Cryptography for Networks—9th International Conference, SCN 2014, volume 8642 of Lecture Notes in Computer Science (Springer, 2014a), pp. 135-154 · Zbl 1302.94055 |
| [40] | N. Makriyannis, On the classification of finite boolean functions up to fairness, in International Conference on Security and Cryptography for Networks (Springer, 2014b), pp. 135-154 · Zbl 1302.94055 |
| [41] | T. Moran, M. Naor, G. Segev, An optimally fair coin toss, in Theory of Cryptography, Sixth Theory of Cryptography Conference, TCC 2009 (2009), pp. 1-18 · Zbl 1213.94123 |
| [42] | M. Naor, Bit commitment using pseudorandomness. J. Cryptol.4(2), 151-158 (1991). Preliminary version in CRYPTO’89. · Zbl 0731.68033 |
| [43] | M. Naor, B. Pinkas, Efficient oblivious transfer protocols, in Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms (Society for Industrial and Applied Mathematics, 2001), pp. 448-457 · Zbl 0991.94045 |
| [44] | R. Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, in Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC) (2004), pp. 232-241 · Zbl 1192.68077 |
| [45] | M. O. Rabin, How to exchange secrets with oblivious transfer, 2005. URL http://eprint.iacr.org/2005/187. Harvard University Technical Report 81 talr@watson.ibm.com 12955 received 21 Jun 2005 |
| [46] | Shamir, A., How to share a secret, Communications of the ACM, 22, 11, 612-613 (1979) · Zbl 0414.94021 · doi:10.1145/359168.359176 |
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.
