{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:58:31Z","timestamp":1778065111185,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642195709","type":"print"},{"value":"9783642195716","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19571-6_27","type":"book-chapter","created":{"date-parts":[[2011,3,22]],"date-time":"2011-03-22T12:04:42Z","timestamp":1300795482000},"page":"450-467","source":"Crossref","is-referenced-by-count":35,"title":["On the Black-Box Complexity of Optimally-Fair Coin Tossing"],"prefix":"10.1007","author":[{"given":"Dana","family":"Dachman-Soled","sequence":"first","affiliation":[]},{"given":"Yehuda","family":"Lindell","sequence":"additional","affiliation":[]},{"given":"Mohammad","family":"Mahmoody","sequence":"additional","affiliation":[]},{"given":"Tal","family":"Malkin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","unstructured":"Blum, M.: Coin flipping by telephone - a protocol for solving impossible problems. In: COMPCON, pp. 133\u2013137 (1982)"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Barak, B., Mahmoody, M.: Lower bounds on signatures from symmetric primitives. In: FOCS: IEEE Symposium on Foundations of Computer Science (FOCS) (2007)","DOI":"10.1109\/FOCS.2007.4389536"},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-03356-8_22","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B. Barak","year":"2009","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Merkle puzzles are optimal \u2014 ano(n\n                  2)-query attack on any key exchange from a random oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 374\u2013390. Springer, Heidelberg (2009)"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: STOC, pp. 364\u2013369 (1986)","DOI":"10.1145\/12130.12168"},{"key":"27_CR5","unstructured":"Cleve, R., Impagliazzo, R.: Martingales, collective coin flipping and discrete control processes (1993) (unpublished)"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SICOMP: SIAM Journal on Computing\u00a035 (2005)","DOI":"10.1137\/S0097539704443276"},{"issue":"4","key":"27_CR7","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM\u00a033(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"27_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-642-14623-7_10","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"V. Goyal","year":"2010","unstructured":"Goyal, V., Ishai, Y., Mahmoody, M., Sahai, A.: Interactive locking, zero-knowledge pCPs, and unconditional cryptography. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 173\u2013190. Springer, Heidelberg (2010)"},{"issue":"2","key":"27_CR9","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci.\u00a028(2), 270\u2013299 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - a tight lower bound on the round complexity of statistically-hiding commitments. In: FOCS, pp. 669\u2013679 (2007)","DOI":"10.1109\/FOCS.2007.7"},{"issue":"4","key":"27_CR11","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput.\u00a028(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"27_CR12","doi-asserted-by":"publisher","first-page":"1153","DOI":"10.1137\/080725404","volume":"39","author":"I. Haitner","year":"2009","unstructured":"Haitner, I., Nguyen, M.-H., Ong, S.J., Reingold, O., Vadhan, S.: Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM Journal on Computing\u00a039(3), 1153\u20131218 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Haitner, I., Reingold, O.: A new interactive hashing theorem. In: IEEE Conference on Computational Complexity (CCC) (2007)","DOI":"10.1109\/CCC.2007.3"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: FOCS, pp. 230\u2013235 (1989)","DOI":"10.1109\/SFCS.1989.63483"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: STOC, pp. 44\u201361 (1989)","DOI":"10.1145\/73007.73012"},{"issue":"2","key":"27_CR16","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1137\/0405021","volume":"5","author":"E. Kushilevitz","year":"1992","unstructured":"Kushilevitz, E.: Privacy and communication complexity. SIAM J. Discrete Math\u00a05(2), 273\u2013284 (1992)","journal-title":"SIAM J. Discrete Math"},{"issue":"2","key":"27_CR17","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0217022","volume":"17","author":"M. Luby","year":"1988","unstructured":"Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput.\u00a017(2), 373\u2013386 (1988)","journal-title":"SIAM J. Comput."},{"key":"27_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-00457-5_1","volume-title":"Theory of Cryptography","author":"T. Moran","year":"2009","unstructured":"Moran, T., Naor, M., Segev, G.: An optimally fair coin toss. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 1\u201318. Springer, Heidelberg (2009)"},{"key":"27_CR19","unstructured":"Maji, H., Prabhakaran, M.: Personal communication (2010)"},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-642-00457-5_16","volume-title":"Theory of Cryptography","author":"H.K. Maji","year":"2009","unstructured":"Maji, H.K., Prabhakaran, M., Rosulek, M.: Complexity of multi-party computation problems: The case of 2-party symmetric secure function evaluation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 256\u2013273. Springer, Heidelberg (2009)"},{"issue":"2","key":"27_CR21","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M. Naor","year":"1991","unstructured":"Naor, M.: Bit commitment using pseudorandomness. J. Cryptology\u00a04(2), 151\u2013158 (1991)","journal-title":"J. Cryptology"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way permutation. JCRYPTOL: Journal of Cryptology 11 (1998)","DOI":"10.1007\/s001459900037"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: STOC, pp. 33\u201343 (1989)","DOI":"10.1145\/73007.73011"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: STOC, pp. 387\u2013394 (1990)","DOI":"10.1145\/100216.100269"},{"key":"27_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24638-1_1","volume-title":"Theory of Cryptography","author":"O. Reingold","year":"2004","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 1\u201320. Springer, Heidelberg (2004)"},{"key":"27_CR26","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Theory and applications of trapdoor functions. In: FOCS, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19571-6_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:25Z","timestamp":1606186105000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19571-6_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642195709","9783642195716"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19571-6_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}