caa a22 4500 475827023 CHVBK 20180406123831.0 cr unu---uuuuu 170329e20000101xx s 000 0 eng 10.1007/s001459910005 doi (NATIONALLICENCE)springer-10.1007/s001459910005 Randomness versus Fault-Tolerance [Elektronische Daten] [Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén] Abstract. : We investigate the relations between two major properties of multiparty protocols: fault tolerance (or resilience ) and randomness . Fault-tolerance is measured in terms of the maximum number of colluding faulty parties, t , that a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honest parties). Randomness is measured in terms of the total number of random bits needed by the parties in order to execute the protocol. Previously, the upper bound on the amount of randomness required by general constructions for securely computing any nontrivial function f was polynomial both in n , the total number of parties, and the circuit-size C(f) . This was the state of knowledge even for the special case t=1 (i.e., when there is at most one faulty party). In this paper we show that for any linear-size circuit, and for any number t < n/3 of faulty International Association for Cryptologic Research, 2000 Key words. Secure multiparty protocols, Randomness, Limited independence, Composition of protocols nationallicence Canetti Ran IBM T. J. Watson Research Center, 30 Saw Mill River Road, NY 10532, Hawthorne, U.S.A. aut Kushilevitz Eyal Department of Computer Science, Technion, Haifa, Israel aut Ostrovsky Rafail Bell Communications Research, MCC-1C365B, NJ 07960-6438, Morristown, U.S.A. aut Rosén Adi Department of Computer Science, University of Toronto, Ontario, Toronto, Canada aut Journal of Cryptology Springer New York 13/1(2000-01-01), 107-142 0933-2790 13:1<107 2000 13 145 https://doi.org/10.1007/s001459910005 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s001459910005 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Canetti Ran IBM T. J. Watson Research Center, 30 Saw Mill River Road, NY 10532, Hawthorne, U.S.A aut NATIONALLICENCE 700 1- Kushilevitz Eyal Department of Computer Science, Technion, Haifa, Israel aut NATIONALLICENCE 700 1- Ostrovsky Rafail Bell Communications Research, MCC-1C365B, NJ 07960-6438, Morristown, U.S.A aut NATIONALLICENCE 700 1- Rosén Adi Department of Computer Science, University of Toronto, Ontario, Toronto, Canada aut NATIONALLICENCE 773 0- Journal of Cryptology Springer New York 13/1(2000-01-01), 107-142 0933-2790 13:1<107 2000 13 145 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer