# Technical Report CS0682

 TR#: CS0682 Class: CS Title: FAULT-TOLERANT COMPUTATION IN THE FULL INFORMATION MODEL (Preliminary Version) Authors: O. Goldreich, S. Goldwasser, N. Linial PDF CS0682.pdf Abstract: We initiate an investigation of general fault-tolerant distributed computation in the {\em full-information} model. In the full information model no restrictions are made on the computational power of the faulty parties or the information available to them. (Namely, the faulty players may be infinitely powerful and there are no private channels connecting pairs of honest players). Previous works, in this model, have concentrated on the particular problem of simulating a single bounded-bias global coin flip (e.g., Ben-Or and Linial [4] and Alon and Naor [1]). We widen the scope of investigation to the general question of how well can arbitrary fault-tolerant computations be performed in this model. The results we obtain should be considered as first steps in this direction. We present efficient two-party protocols for fault-tolerant computation of any two-argument function. We prove that the influence of dishonest players in these protocols is the minimum one possible (up to polylogarithmic factors). We also present efficient $m$-party fault-tolerant protocols for sampling a general distribution $(m \geq 2)$.We present efficient $m$-party protocols for computation of any $m$-argument function, and prove for these protocols that for most'' functions, the influence of any $t$ dishonest players on the outcome of the protocol is the minimum one possible (up to polylogarithmic factors). Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0682), rather than to the URL of the PDF files directly. The latter URLs may change without notice.