Previously, the upper bound on the amount of randomness required by general constructions for securely computing any non-trivial 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 parties, O(poly(t) * log n) randomness is sufficient. More generally, we show that for any function 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. Furthermore, in our protocol only t+1 parties flip coins and the rest of the parties are deterministic. Our results generalize to the case of adaptive adversaries as well.
Category / Keywords: Secure multiparty protocols, Randomness, Limited independence, Composition of protocols. Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. Date: received Apr 30th, 1998. Contact author: canetti at watson ibm com Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Discussion forum: Show discussion | Start new discussion