{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:50:03Z","timestamp":1782971403988,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540374329","type":"print"},{"value":"9783540374336","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11818175_25","type":"book-chapter","created":{"date-parts":[[2006,9,23]],"date-time":"2006-09-23T06:21:52Z","timestamp":1158992512000},"page":"409-426","source":"Crossref","is-referenced-by-count":20,"title":["Random Selection with an Adversarial Majority"],"prefix":"10.1007","author":[{"given":"Ronen","family":"Gradwohl","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Zuckerman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"25_CR1","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/0222030","volume":"22","author":"N. Alon","year":"1993","unstructured":"Alon, N., Naor, M.: Coin-flipping games immune against linear-sized coalitions. SIAM J. Computing\u00a022(2), 403\u2013417 (1993)","journal-title":"SIAM J. Computing"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Antonakopoulos, S.: Fast leader-election protocols with bounded cheaters\u2019 edge. In: Proc. 38th STOC, pp. 187\u2013196 (2006)","DOI":"10.1145\/1132516.1132544"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B.: Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In: 43rd FOCS (2002)","DOI":"10.1109\/SFCS.2002.1181957"},{"key":"25_CR4","unstructured":"Blum, M.: Coin flipping by telephone. In: IEEE Spring COMPCOM (1982)"},{"key":"25_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/0-387-34805-0_51","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"D. Beaver","year":"1990","unstructured":"Beaver, D., Goldwasser, S.: Multiparty computation with faulty majority. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 589\u2013590. Springer, Heidelberg (1990)"},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: 20th STOC, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"key":"25_CR7","series-title":"Randomness and Computation","first-page":"91","volume-title":"Advances in Computing Research","author":"M. Ben-Or","year":"1989","unstructured":"Ben-Or, M., Linial, N.: Collective coin fliping. In: Advances in Computing Research. Randomness and Computation, vol.\u00a05, pp. 91\u2013115. JAI Press, Greenwich, CT (1989)"},{"issue":"4","key":"25_CR8","doi-asserted-by":"publisher","first-page":"1304","DOI":"10.1137\/S0097539796307182","volume":"29","author":"R. Boppana","year":"2000","unstructured":"Boppana, R., Narayanan, B.: Perfect-information leader election with optimal resilience. SIAM J. Computing\u00a029(4), 1304\u20131320 (2000)","journal-title":"SIAM J. Computing"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rompel, J.: Randomness-efficient oblivious sampling. In: 35th FOCS (1994)","DOI":"10.1109\/SFCS.1994.365687"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols. In: 20th STOC, pp. 11\u201319 (1988)","DOI":"10.1145\/62212.62214"},{"key":"25_CR11","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF01299739","volume":"15","author":"J. Cooper","year":"1995","unstructured":"Cooper, J., Linial, N.: Fast perfect-information leader-election protocols with linear immunity. Combinatorica\u00a015, 319\u2013332 (1995)","journal-title":"Combinatorica"},{"key":"25_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/3-540-48329-2_9","volume-title":"Advances in Cryptology - CRYPTO \u201993","author":"I.B. Damg\u00e5rd","year":"1994","unstructured":"Damg\u00e5rd, I.B.: Interactive hashing can simplify zero-knowledge protocol design without computational assumptions (extended abstract). In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol.\u00a0773, pp. 100\u2013109. Springer, Heidelberg (1994)"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Goldreich, O., Wigderson, A.: Hashing functions can simplify zero-knowledge protocol design (too). TR RS-94-39. BRICS (1994)","DOI":"10.7146\/brics.v1i39.21604"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-540-24638-1_25","volume-title":"Theory of Cryptography","author":"Y.Z. Ding","year":"2004","unstructured":"Ding, Y.Z., Harnik, D., Rosen, A., Shaltiel, R.: Constant-round oblivious transfer in the bounded storage model. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 446\u2013472. Springer, Heidelberg (2004)"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Feige, U.: Noncryptographic selection protocols. In: 40th FOCS, pp. 142\u2013152 (1999)","DOI":"10.1109\/SFFCS.1999.814586"},{"key":"25_CR16","unstructured":"Goldreich, O.: A sample of samplers - a computational perspective on sampling (survey). Report 97-020, Electronic Colloquium on Computational Complexity (1997)"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Linial, N.: Fault-tolerant computation in the full information model. SIAM J. Computing\u00a027(2) (1998)","DOI":"10.1137\/S0097539793246689"},{"key":"25_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/3-540-38424-3_6","volume-title":"Advances in Cryptology - CRYPTO \u201990","author":"S. Goldwasser","year":"1991","unstructured":"Goldwasser, S., Levin, L.A.: Fair computation of general functions in presence of immoral majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol.\u00a0537, pp. 77\u201393. Springer, Heidelberg (1991)"},{"key":"25_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3-540-36108-1_2","volume-title":"Distributed Computing","author":"S. Goldwasser","year":"2002","unstructured":"Goldwasser, S., Lindell, Y.: Secure computation without agreement. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol.\u00a02508, pp. 17\u201332. Springer, Heidelberg (2002)"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game. In: 19th STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: 30th STOC (1998)","DOI":"10.1145\/276698.276852"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Gradwohl, R., Vadhan, S., Zuckerman, D.: Random Selection with an Adversarial Majority. Report TR06-26, Electronic Colloquium on Computational Complexity (February 2006)","DOI":"10.1007\/11818175_25"},{"key":"25_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/978-3-540-28628-8_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"J. Katz","year":"2004","unstructured":"Katz, J., Ostrovsky, R.: Round-optimal secure two-party computation. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.\u00a03152, pp. 335\u2013354. Springer, Heidelberg (2004)"},{"key":"25_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1007\/3-540-39200-9_36","volume-title":"Advances in Cryptology \u2013 EUROCRPYT 2003","author":"J. Katz","year":"2003","unstructured":"Katz, J., Ostrovsky, R., Smith, A.: Round efficiency of multi-party computation with a dishonest majority. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol.\u00a02656, pp. 578\u2013595. Springer, Heidelberg (2003)"},{"key":"25_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/3-540-44647-8_10","volume-title":"Advances in Cryptology - CRYPTO 2001","author":"Y. Lindell","year":"2001","unstructured":"Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol.\u00a02139, p. 171. Springer, Heidelberg (2001)"},{"issue":"2","key":"25_CR26","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"M. Pease","year":"1980","unstructured":"Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM\u00a027(2), 228\u2013234 (1980)","journal-title":"J. ACM"},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"Lu, C., Reingold, O., Vadhan, S., Wigderson, A.: Extractors: Optimal up to constant factors. In: 35th STOC (2003)","DOI":"10.1145\/780542.780630"},{"key":"25_CR28","doi-asserted-by":"crossref","unstructured":"Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP can be based on general complexity assumptions. J. Cryptology\u00a011 (1998)","DOI":"10.1007\/s001459900037"},{"issue":"1","key":"25_CR29","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N. Nisan","year":"1996","unstructured":"Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Computer and System Sci.\u00a052(1), 43\u201352 (1996)","journal-title":"J. Computer and System Sci."},{"issue":"1","key":"25_CR30","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jcss.1999.1664","volume":"60","author":"T. Okamoto","year":"2000","unstructured":"Okamoto, T.: On relationships between statistical zero-knowledge proofs. J. Computer and System Sci.\u00a060(1), 47\u2013108 (2000)","journal-title":"J. Computer and System Sci."},{"key":"25_CR31","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rajagopalan, S., Vazirani, U.: Simple and efficient leader election in the full information model. In: Proc. 26th STOC, pp. 234\u2013242 (1994)","DOI":"10.1145\/195058.195141"},{"key":"25_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/3-540-48285-7_23","volume-title":"Advances in Cryptology - EUROCRYPT \u201993","author":"R. Ostrovsky","year":"1994","unstructured":"Ostrovsky, R., Venkatesan, R., Yung, M.: Interactive hashing simplifies zero-knowledge protocol design. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol.\u00a0765, pp. 267\u2013273. Springer, Heidelberg (1994)"},{"issue":"1","key":"25_CR33","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1006\/jcss.2002.1824","volume":"65","author":"R. Raz","year":"2002","unstructured":"Raz, R., Reingold, O., Vadhan, S.: Extracting all the randomness and reducing the error in Trevisan\u2019s extractors. J. Computer and System Sc.\u00a065(1), 97\u2013128 (2002)","journal-title":"J. Computer and System Sc."},{"key":"25_CR34","doi-asserted-by":"crossref","unstructured":"Raz, R., Reingold, O., Vadhan, S.: Error Reduction for Extractors. In: 40th FOCS (1999)","DOI":"10.1109\/SFFCS.1999.814591"},{"key":"25_CR35","doi-asserted-by":"publisher","first-page":"1645","DOI":"10.1137\/S0097539700376007","volume":"31","author":"A. Russell","year":"2002","unstructured":"Russell, A., Saks, M., Zuckerman, D.: Lower bounds for leader election and collective coin- flipping in the perfect information model. SIAM J. Computing\u00a031, 1645\u20131662 (2002)","journal-title":"SIAM J. Computing"},{"issue":"1","key":"25_CR36","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1137\/S0895480197329508","volume":"13","author":"J. Radhakrishnan","year":"2000","unstructured":"Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math.\u00a013(1), 2\u201324 (2000)","journal-title":"SIAM J. Discrete Math."},{"key":"25_CR37","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1006\/jcss.2001.1776","volume":"63","author":"A. Russell","year":"2001","unstructured":"Russell, A., Zuckerman, D.: Perfect-information leader election in log* n\u2009+\u2009O(1) rounds. J. Computer and System Sci.\u00a063, 612\u2013626 (2001)","journal-title":"J. Computer and System Sci."},{"issue":"2","key":"25_CR38","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/0402020","volume":"2","author":"M. Saks","year":"1989","unstructured":"Saks, M.: A robust noncryptographic protocol for collective coin flipping. SIAM J. Discrete Math.\u00a02(2), 240\u2013244 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"25_CR39","doi-asserted-by":"crossref","unstructured":"Sanghvi, S., Vadhan, S.: The round complexity of two-party random selection. In: 37th STOC (2005)","DOI":"10.1145\/1060590.1060641"},{"issue":"1","key":"25_CR40","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00145-003-0237-x","volume":"17","author":"S. Vadhan","year":"2004","unstructured":"Vadhan, S.: Constructing locally computable extractors and cryptosystems in the bounded-storage model. J. Cryptology\u00a017(1), 43\u201377 (2004)","journal-title":"J. Cryptology"},{"issue":"17","key":"25_CR41","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s004930050049","volume":"19","author":"A. Wigderson","year":"1999","unstructured":"Wigderson, A., Zuckerman, D.: Expanders that beat the eigenvalue bound: explicit construction and applications. Combinatorica\u00a019(17), 125\u2013138 (1999)","journal-title":"Combinatorica"},{"key":"25_CR42","doi-asserted-by":"crossref","unstructured":"Yao, A.: How to generate and exchange secrets. In: Proc. 27th FOCS (1986)","DOI":"10.1109\/SFCS.1986.25"},{"issue":"4","key":"25_CR43","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z","volume":"11","author":"D. Zuckerman","year":"1997","unstructured":"Zuckerman, D.: Randomness-optimal oblivious sampling. Random Structures and Algorithms\u00a011(4), 345\u2013367 (1997)","journal-title":"Random Structures and Algorithms"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology - CRYPTO 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11818175_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:16:09Z","timestamp":1605644169000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11818175_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540374329","9783540374336"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/11818175_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}