How to Solve any Protocol Problem

: This extended abstract present a general theorem in the field of fault tolerant distributed computing. Following is a simplified description of a special case of this theorem. Loosely speaking, a protocol problem is a multi-argument function f and its solution is a multi-party fault-tolerant protocol having the following two properties: (1) Correctness: The protocol allows each party to obtain the value of the function on arguments scattered among all the parties. Namely, the local input of party P i is x i , and his local output (obtained by execution of the protocol) is f(x 1 ; x 2 ; :::; x n ). (2) Privacy: Whatever a party (P i ) can efficiently compute after participating in the protocol, he can also efficiently compute from his local input (x i ) and his local output (i.e. f(x 1 ; x 2 ; :::; x n )). In other words, participating in the protocol is equivalent to getting f(x 1 ; x 2 ; :::; x n ) from a trusted oracle. For example, if f(x 1 ; x 2 ; :::; x n ) = P n i=1 x i then ..