Randomness versus fault-tolerance

We investigate the relations between two major properties of multiparty pro tocols: fault tolerance (or resilience) and randomness. Fault-tolerance is measured in terms of the maximum number of colluding faulty parties, t, tha t a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honest parties). Randomness is meas ured in terms of the total number of random bits needed by the parties in o rder 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 polynom ial both in n, the total number of parties, and the circuit-size C (f). Thi s was the state of knowledge even for the special case t = 1 (i.e., when th ere is at most one faulty party). In this pa per we show that for any linea r-size circuit, and for any number t < n/3 of faulty parties, O (poly(t).lo g n) randomness is sufficient. More generally, we show that, for any functi on f with circuit-size C(f), we need only O (poly(t).log n + poly(t).(C(f)/ n)) randomness in order to withstand any coalition of size at most t. Furth ermore, in our protocol only t + 1 parties flip coins and the rest of the p arties are deterministic. Our results generalize to the case of adaptive ad versaries as well.